Carnegie Mellon University
Browse

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

Download (260.56 kB)
journal contribution
posted on 2013-05-01, 00:00 authored by Umut A. Acar, Guy E. Blelloch, Robert Harper, Jorge L. Vittes, Shan Leung Maverick Woo

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.

History

Date

2013-05-01

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC