Computer Science Department
School of Computer Science, Carnegie Mellon University
Distributed Construction of a Fault-Tolerant Network
from a Tree
Michael K. Reiter*, Asad Samar**, Chenxi Wang**
Keywords: Fault-tolerant networks, expander graphs, random walks,
self-stabilization, 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 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.
*Department of Computer Science and Department of Electrical and
Computer Engineering, Carnegie Mellon University
**Department of Electrical and Computer Engineering, Carnegie Mellon University