We present a distributed algorithm which constructs a fixed node-degree
overlay network for efficient fault-tolerant multi-hop communication in large
distributed systems: Given a fully connected weighted graph, where the
weight of an edge represents the cost of a connection, the algorithm builds
and maintains a Delta-regular subgraph that is Delta-node connected,
ensures failure locality, and has low total weight. The algorithm
automatically adapts to a dynamically changing environment,
is guaranteed to stabilize, and exhibits good average case performance
as well. It is hence well suited for both establishing
fault-tolerant communication topologies in CDMA-based wireless ad hoc
networks and for constructing robust overlay graphs in peer-to-peer networks.

Keywords: FT Communication, FT Mobile Computing/Networking,
Distributed Algorithms, Redundant Paths, Overlay Networks