James Aspnes and Yinghua Wu. O(log n)-time overlay network construction from graphs with out-degree 1. Principles of Distributed Systems; 11th International Conference, OPODIS 2007, Gaudaloupe, French West Indies, December 17–20, 2007, Proceedings. Lecture Notes in Computer Science 4878. Springer-Verlag, December 2007, pp. 286–300.
A fast self-stabilizing algorithm is described to rapidly construct a balanced overlay network from a directed graph initially with out-degree 1, a natural starting case that arises in peer-to-peer systems where each node attempts to join by contacting some single other node. This algorithm constructs a balanced search tree in time O(W+log n), improving by a factor of log n on the previous bound starting from a general graph, while retaining the properties of low contention and short messages. Our construction includes an improved version of the distributed Patricia tree structure of (Angluin et al., 2005) that we call a double-headed radix tree. This data structure responds gracefully to node failures and supports search, predecessor, and successor operations in O(W) time with smoothly distributed load for predecessor and successor operations. Though the resulting tree data structure is highly vulnerable to disconnection due to failures, the fast predecessor and successor operations (as shown in previous work) can be used to quickly construct standard overlay networks with more redundancy.
@inproceedings{AspnesW2007,
author = {James Aspnes and Yinghua Wu},
title = {{$O(\log n)$}-time overlay network construction from graphs with out-degree {$1$}},
month = dec,
year = 2007,
booktitle = {Principles of Distributed Systems;
11th International Conference, OPODIS 2007,
Gaudaloupe, French West Indies, December 17--20, 2007. Proceedings},
publisher = {Springer-Verlag},
series = {Lecture Notes in Computer Science},
volume = 4878,
pages={286--300}}