We present an algorithm by which nodes arranged in a tree, with each node initially knowing only its parent and children, can construct a fault-tolerant communication structure (an expander graph) among themselves in a distributed and scalable way. Tree structures arise naturally in many distributed applications, in which a node "joins" the system by contacting a node already present in the system: the joining node then becomes a child of the node it contacts for entry. Our algorithm enables nodes to construct an expander graph incrementally without propagating membership information globally. At the core of our construction is a novel distributed mechanism that samples nodes uniformly at random from the tree. In the event of node joins, node departures or crash failures, our graph self-stabilizes to a state where it still achieves the required fault tolerant properties. We present simulation results to quantify the convergence of our algorithm to a fault tolerant network having both good vertex connectivity and expansion properties.

16 pages

*Department of Computer Science and Department of Electrical and Computer Engineering, Carnegie Mellon University
**Department of Electrical and Computer Engineering, Carnegie Mellon University

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by reports@cs.cmu.edu