# O(log n)-time overlay network construction from graphs with out-degree 1

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.

## Abstract

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.

- OPODIS 2007 proceedings version: PDF.
- Full version:
**PDF**.

## BibTeX

Download@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}}

Consolidated BibTeX file

Return to James Aspnes's publications

Return to James Aspnes's home page