
CMUCS05114
Computer Science Department
School of Computer Science, Carnegie Mellon University
CMUCS05114
Distributed Construction of a FaultTolerant Network
from a Tree
Michael K. Reiter*, Asad Samar**, Chenxi Wang**
February 2005
CMUCS05114.ps
CMUCS05114.pdf
Keywords: Faulttolerant networks, expander graphs, random walks,
selfstabilization, distributed algorithms
We present an algorithm by which nodes arranged in a tree, with each
node initially knowing only its parent and children, can construct
a faulttolerant 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
selfstabilizes 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
