Tiara: a self-stabilizing deterministic skip list and skip graph (Q418743)

The authors present Tiara, a deterministic self-stabilizing peer-to-peer network maintenance algorithm. First they describe a novel distributed sparse skip list that is self-stabilizing. Robustness is achieved by connecting nodes in alternative lists at different levels of the skip list. To increase performance, a skip graph is generated based on a collection of those skip lists rooted in every node. The skip graph is defined in such a way that certain expansion properties can be proven. This ensures that searching for items as well as performing topology updates is fast. At the same time this improves the robustness to node failures significantly. To be more specific, the expansion of the skip graph is \(\Omega(1/|N|^{\frac{1}{\log 3}})\). Searching an element takes \(O(\log |N|)\) time. The time required to add (or remove) a node to the skip graph is \(O(\log^2 |N|)\).