Search

This paper is a position paper on the nature of dynamic systems. While there is an agreement on the definition of what a static distributed system is, there is no agreed definition on what a dynamic distributed system is. This paper is a first step in that direction. To that end, it emphasizes two orthogonal dimensions that are present in any dynamic distributed system, namely the varying and possibly very large number of entities that currently define the system, and the fact that each of these entities knows only a few other entities (its neighbors) and possibly will never be able to know the whole system it is a member of. To illustrate the kind of issues one has to cope with in dynamic systems, the paper considers, as a "canonical" problem, a simple data aggregation problem. It shows the type of dynamic systems in which that problem can be solved and the ones in which it cannot be solved. The aim of the paper is to give the reader an idea of the subtleties and difficulties encountered when one wants to understand the nature of dynamic distributed systems. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Partitioning is one of the main problems in p2p group membership. This problem rises when failures and dynamics of peer participation, or churn, occur in the overlay topology created by a group membership protocol connecting the group of peers. Solutions based on Gossip-based Group Membership (GGM) cope well with the failures while suffer from network dynamics. This paper shows a performance evaluation of SCAMP, one of the most interesting GGM protocol. The analysis points out that the probability of partitioning of the overlay topology created by SCAMP increases with the churn rate. We also compare SCAMP with DET - another membership protocol that deterministically avoids partitions of the overlay. The comparison points out an interesting trade-off between (i) reliability, in terms of guaranteeing overlay connectivity at any churn rate, and (ii) scalability in terms of creating scalable overlay topologies where latencies experienced by a peer during join and leave operations do not increase linearly with the number of peers in the group. [ABSTRACT FROM AUTHOR]

Emerging distributed systems have a dynamic structure that is self-defined at any time by entities that autonomously decide to locally run the same distributed application. As extreme, a distributed system might thus also cease its existence when no entity is currently active while at some later moment new entities arrive and connect to each other to form again the system. Therefore the set of entities that over time might form the system is potentially infinite. This infinite arrival model is the key distinguishing factor between dynamic systems and traditional distributed systems where, on the contrary, the set of system entities is fixed since the deployment of application components is controlled and managed. In this model not only the set of correct processes is not known in advance, but no finite set containing the set of correct processes is known in advance. This actually is a higher level of uncertainty to be mastered in dynamic systems. This makes the study of possible implementations of failure detectors, as Ώ, of paramount importance and at the same time makes the problem of realizing such failure detector far from being trivial. The uncertainty posed by infinite arrival models brings to two different issues (1) discovering the finite set of processes currently running and (2) dealing with a possible infinite set of non-correct processes that may wake up at any time, covering with their up times the whole computation. [ABSTRACT FROM AUTHOR]