Tiara: A self-stabilizing deterministic skip list and skip graph

We present Tiara—a self-stabilizing peer-to-peer network maintenance algorithm. Tiara is truly deterministic which allows it to achieve exact performance bounds. Tiara allows logarithmic searches and topology updates. It is based on a novel sparse 0–1 skip list. We then describe its extension to a ringed structure and to a skip-graph.