Connectivity in Eventually Quiescent Dynamic Distributed Systems

A distributed dynamic system is a fully distributed system subject to a continual arrival/departure of the entities defining the system. Another characterizing dimension of these systems is their, possibly, arbitrary large size (number of entities) and the possible arbitrary small part of the system a single entity directly interacts with. This interaction occurs through data exchange over logical links, and the constantly changing graph, formed by all links connecting entities, represents the overlay network of the dynamic distributed system. The connectivity of such overlay is of fundamental importance to make the whole system working. This paper gives a precise definition of the connectivity problem in dynamic distributed systems while formally defining assumptions on arrival/departure of entities and on the evolution of the system size along the time. The paper shows the impossibility of achieving connectivity when an arbitrary large number of entities may arrive/depart concurrently at any time, doing so for an arbitrarily long time. A solution is presented achieving overlay connectivity during quiescent periods of the system: periods in which no more arrivals and departures take place. The paper conveys the fact that the finite but not known duration of the perturbed period before quiescence makes the solution of the problem far from being trivial. The paper also provides a simulation study showing that the solution not only achieves connectivity in quiescent periods but it rearranges entities in an overlay that shows good scalability properties. © Springer-Verlag Berlin Heidelberg 2007.