Dynamizing Static Algorithms, with Applications to Dynamic Trees and History Independence

We describe a machine model for automatically dynamizing static algorithms and apply it to history-independent data structures. Static programs expressed in this model are dynamized automatically by keeping track of dependences between code and data in the form of a dynamic dependence graph. To study the performance of such automatically dynamized algorithms we present an analysis technique based on trace stability. As an example of the use of the model, we dynamize the Parallel Tree Contraction Algorithm of Miller and Reif to obtain a history-independent data structure for the dynamic trees problem of Sleator and Tarjan.