| 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 that provide perpetual system connectivity, either (1) the topology has large worst-case degree and/or diameter or (2) a process may experience high worst-case delay when leaving the system.;In this work, 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 irrespective of how many processes are leaving along with it concurrently. 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 O(log N) or worst-case degree of O(1), the departure of a process may be delayed by O(log logN) time in the worst-case.;Key Words: dynamic distributed systems, scalable topology maintenance, perpetual connectivity, fast departures... |
