A scalable algorithm for maintaining perpetual system connectivity in dynamic distributed systems

We investigate the problem of maintaining a topology with small degree as well as small diameter in a dynamic distributed system such that the system always stays connected and processes that wish to leave the system can do so quickly. Perpetual system connectivity is necessary to solve many important problems in dynamic distributed systems, including atomic broadcast and stable property detection, that need strict (deterministic) guarantees about system connectivity to be solvable. To our knowledge, in all existing topology maintenance algorithms for asynchronous distributed systems that provide perpetual system connectivity, either: (i) the topology has large worst-case degree and/or diameter (ii) a process may experience high worst-case delay when leaving the system, or (iii) processes cannot join and/or leave concurrently. In this paper, we present a spanning tree maintenance algorithm that satisfies the following desirable properties. First, the spanning tree has small maximum degree of O(1) and small maximum diameter of O(log N), where N denotes the maximum size of the system. Second, any process can leave the system within O(log N) time even in the presence of concurrent arrivals and departures. Third, the system always stays connected. We show using a simple knowledge-based argument that, in any algorithm that maintains perpetual connectivity such that the topology has either worst-case diameter of ¿(log N) or worst-case degree of O(1), the departure of a process may be delayed by ¿(log log N) time in the worst-case.