We consider a population of @math agents which communicate with each other in a decentralized manner, through random pairwise interactions. One or more agents in the population may act as authoritative sources of information, and the objective of the remaining agents is to obtain information from or about these source agents. We study two basic tasks: broadcasting, in which the agents are to learn the bit-state of an authoritative source which is present in the population, and source detection, in which the agents are required to decide if at least one source agent is present in the population or not.We focus on designing protocols which meet two natural conditions: (1) universality, i.e., independence of population size, and (2) rapid convergence to a correct global state after a reconfiguration, such as a change in the state of a source agent. Our main positive result is to show that both of these constraints can be met. For both the broadcasting problem and the source detection problem, we obtain solutions with a convergence time of @math rounds, w.h.p., from any starting configuration. The solution to broadcasting is exact, which means that all agents reach the state broadcast by the source, while the solution to source detection admits one-sided error on a @math -fraction of the population (which is unavoidable for this problem). Both protocols are easy to implement in practice and have a compact formulation.Our protocols exploit the properties of self-organizing oscillatory dynamics. On the hardness side, our main structural insight is to prove that any protocol which meets the constraints of universality and of rapid convergence after reconfiguration must display a form of non-stationary behavior (of which oscillatory dynamics are an example). We also observe that the periodicity of the oscillatory behavior of the protocol, when present, must necessarily depend on the number @math of source agents present in the population. For instance, our protocols inherently rely on the emergence of a signal passing through the population, whose period is @math rounds for most starting configurations. The design of clocks with tunable frequency may be of independent interest, notably in modeling biological networks.
@cite_2: Clock synchronization is one of the most basic building blocks for many applications in computer science and engineering. The purpose of clock synchronization is to provide the constituent parts of a distributed system with a common notion of time. While the problem of synchronizing clocks in distributed systems has already received considerable attention from researchers and practitioners alike, we believe that there are many fascinating problems that remain unsolved. In this paper, we give a brief overview of previous work in this area, followed by a discussion of open clock synchronization problems in theory and practice.
@cite_42: We present a distributed clock synchronization algorithm that guarantees an exponentially improved bound of O(log D) on the clock skew between neighboring nodes in any graph G of diameter D. In light of the lower bound of Omega(log D log log D), this result is almost tight. Moreover, the global clock skew between any two nodes, particularly nodes that are not directly connected, is bounded by O(D), which is optimal up to a constant factor. Our algorithm further ensures that the clock values are always within a linear envelope of real time. A better bound on the accuracy with respect to real time cannot be achieved in the absence of an external timer. These results all hold in a general model where both the clock drifts and the message delays may vary arbitrarily within pre-specified bounds.
@cite_1: Cyclic dominance of species has been identified as a potential mechanism to maintain biodiversity, see, e.g., B. Kerr, M. A. Riley, M. W. Feldman and B. J. M. Bohannan Nature 418, 171 (2002)] and B. Kirkup and M. A. Riley Nature 428, 412 (2004)]. Through analytical methods supported by numerical simulations, we address this issue by studying the properties of a paradigmatic non-spatial three-species stochastic system, namely, the "rock-paper-scissors" or cyclic Lotka-Volterra model. While the deterministic approach (rate equations) predicts the coexistence of the species resulting in regular (yet neutrally stable) oscillations of the population densities, we demonstrate that fluctuations arising in the system with a finite number of agents drastically alter this picture and are responsible for extinction: After long enough time, two of the three species die out. As main findings we provide analytic estimates and numerical computation of the extinction probability at a given time. We also discuss the implications of our results for a broad class of competing population systems.
@cite_11: Abstract We describe a new fault-tolerant algorithm for solving a variant of Lamport's clock synchronization problem. The algorithm is designed for a system of distributed processes that communicate by sending messages. Each process has its own read-only physical clock whose drift rate from real time is very small. By adding a value to its physical clock time, the process obtaines its local time. The algorithm solves the problem of maintaining closely synchronized local times, assuming that processes' local times are closely synchronized initially. The algorithm is able to tolerate the failure of just under one-third of the participating processes. It maintains synchronization to within a small constant, whose magnitude depends upon the rate of clock drift, the message delivery time and its uncertainty, and the initial closeness of synchronization. We also give a characterization of how far the clocks drift from real time. Reintegration of a repaired process can be accomplished using a slight modification of the basic alborithm. A similar style algorithm can also be used to achieve synchronization initially.
Our work fits into the line of research on rumor spreading, population protocols, and related interaction models. Our work also touches on the issue of how distributed systems may spontaneously achieve some form of coordination with minimum agent capabilities. The basic work in this direction, starting with the seminal paper @cite_1 , focuses on synchronizing timers through asynchronous interprocess communication to allow processes to construct a total ordering of events. A separate interesting question concerns local clocks which, on their own, have some drift, and which need to synchronize in a network environment (cf. e.g. @cite_11 @cite_42 , or @cite_2 for a survey of open problems).