Abstract We consider the standard population protocol model, where ( a priori ) indistinguishable and anonymous agents interact in pairs according to uniformly random scheduling. The self-stabilizing leader election problem requires the protocol to converge on a single leader agent from any possible initial configuration. We initiate the study of time complexity of population protocols solving this problem in its original setting: with probability 1, in a complete communication graph. The only previously known protocol by Cai, Izumi, and Wada [Theor. Comput. Syst. 50] runs in expected parallel time $$\Theta (n^2)$$ Θ ( n 2 ) and has the optimal number of n states in a population of n agents. The existing protocol has the additional property that it becomes silent, i.e., the agents’ states eventually stop changing. Observing that any silent protocol solving self-stabilizing leader election requires $$\Omega (n)$$ Ω ( n ) expected parallel time, we introduce a silent protocol that uses optimal O ( n ) parallel time and states. Without any silence constraints, we show that it is possible to solve self-stabilizing leader election in asymptotically optimal expected parallel time of $$O(\log n)$$ O ( log n ) , but using at least exponential states (a quasipolynomial number of bits). All of our protocols (and also that of Cai et al.) work by solving the more difficult ranking problem: assigning agents the ranks $$1,\ldots ,n$$ 1 , … , n .

Abstract We study distributed agreement in microbial distributed systems under stochastic population dynamics and competitive interactions. Motivated by recent applications in synthetic biology, we examine how the presence and absence of direct competition among microbial species influences their ability to reach majority consensus . In this problem, two species are designated as input species, and the goal is to guarantee that eventually only the input species which had the highest initial count prevails. We show that direct competition dynamics reach majority consensus with high probability even when the initial gap between the species is small, i.e., $$\Omega (\sqrt{n\log n})$$ , where n is the initial population size. In contrast, we show that absence of direct competition is not robust: solving majority consensus with constant probability requires a large initial gap of $$\Omega (n)$$ . To corroborate our analytical results, we use simulations to show that these consensus dynamics occur within practical biological time scales.

In the treasure hunt problem, a team of mobile agents need to locate a single treasure that is hidden in their environment. We consider the problem in the discrete setting of an oriented infinite rectangular grid, where agents are modeled as synchronous identical deterministic time-limited finite-state automata, originating at a rate of one agent per round from the origin. Agents perish τ rounds after their creation, where τ ≥ 1 is a parameter of the model. An algorithm solves the treasure hunt problem if every grid position at distance τ or less from the origin is visited by at least one agent. Agents may communicate only by leaving indistinguishable traces (pheromone) on the nodes of the grid, which can be sensed by agents in adjacent nodes and thus modify their behavior. The novelty of our approach is that, in contrast to existing literature that uses permanent pheromone markers, we assume that pheromone traces evaporate over µ rounds from the moment they were placed on a node, where µ ≥ 1 is another parameter of the model. We look for uniform algorithms that solve the problem without knowledge of the parameter values, and we investigate the implications of this very weak communication mechanism to the treasure hunt problem. We show that, if pheromone persists for at least two rounds (µ ≥ 2), then there exists a treasure hunt algorithm for all values of agent lifetime. We also develop a more sophisticated algorithm that works for all values of µ, hence also for the fastest possible pheromone evaporation of µ = 1, but only if agent lifetime is at least 16.

We consider the standard population protocol model, where (a priori) indistinguishable and anonymous agents interact in pairs according to uniformly random scheduling. The self-stabilizing leader election problem requires the protocol to converge on a single leader agent from any possible initial configuration. We initiate the study of time complexity of population protocols solving this problem in its original setting: with probability 1, in a complete communication graph. The only previously known protocol by Cai, Izumi, and Wada [Theor. Comput. Syst. 50] runs in expected parallel time Θ(n2) and has the optimal number of n states in a population of n agents. The existing protocol has the additional property that it becomes silent, i.e., the agents' states eventually stop changing.

The beeping model is an extremely restrictive communication model. Nodes communicate in discrete rounds using beeps---simple bursts of energy---and carrier sensing. Simultaneous beeps produce (nondestructive) collisions, resulting in information loss. Such communication differs greatly from the traditional communication mechanisms in distributed systems, like message-passing or shared memory. Indeed, a beep is a unary signal that communicates no information (e.g., no message content, nor sender information) beyond its own presence. As a result, in a round of beeping communication, hearing a beep means only that some (unknown) neighboring node is communicating in this very round, whereas silence (i.e., hearing no beeps) means only that no neighboring node is communicating.

The distributed naming problem, assigning unique names to the nodes in a distributed system, is a fundamental task. This problem is nontrivial, especially when the amount of memory available for the task is low, and when requirements for fault-tolerance are added. The considered distributed communication model is population protocols. In this model, a priori anonymous and indistinguishable mobile nodes (called agents), communicate in pairs and in an asynchronous manner (according to a fairness condition). Fault-tolerance is addressed through self-stabilization, in terms of arbitrary initialization of agents. This work comprises a comprehensive study of the necessary and sufficient state space conditions for naming. The problem is studied under various combinations of model assumptions: weak or global fairness, arbitrary or uniform initialization of agents, existence or absence of a distinguishable agent (arbitrarily initialized or not), possibility of breaking symmetry in pair-wise interactions (symmetric or asymmetric transitions). For each possible combination of these assumptions, either an impossibility is proven or the necessary exact number of states (per mobile agent) is determined and an appropriate space-optimal naming protocol is presented.

The beeping model is an extremely restrictive broadcast communication model that relies only on carrier sensing. We consider two problems in this model: (Δ+1)-vertex coloring and maximal independent set (MIS), for a network of unknown size n and unknown maximum degree Δ. Solving these problems allows to overcome communication interferences, and to break symmetry, a core component of many distributed protocols. The presented results apply to general graphs, but are efficient in graphs with low edge density (sparse graphs), such as bounded degree graphs, planar graphs and graphs of bounded arboricity. We present O(Δ2log n + Δ3) time deterministic uniform MIS and coloring protocols, which are asymptotically time optimal for bounded degree graphs. Furthermore, we devise O(a2log2n+a3log n) time MIS and coloring protocols, as well as O(a2Δ2log2n + a3Δ3log n) time 2-hop MIS and 2-hop coloring protocols, where a is the arboricity of the communication graph. Building upon the 2-hop coloring protocols, we show how the strong CONGEST model can be simulated and by using this simulation we obtain an O ( a) -coloring protocol. No results about coloring with less than Δ + 1 colors were known up to now in the beeping model.

The beeping model is an extremely restrictive broadcast communication model that relies only on carrier sensing. In this model, we solve the leader election problem with an asymptotically optimal round complexity of O(D + log n), for a network of unknown size n and unknown diameter D (but with unique identifiers). Contrary to the best previously known algorithms in the same setting, the proposed one is deterministic. The techniques we introduce give a new insight as to how local constraints on the exchangeable messages can result in efficient algorithms, when dealing with the beeping model. Using this deterministic leader election algorithm, we obtain a randomized leader election algorithm for anonymous networks with an asymptotically optimal round complexity of O(D + log n) w.h.p. In previous works this complexity was obtained in expectation only. Moreover, using deterministic leader election, we obtain efficient algorithms for symmetry-breaking and communication procedures: O(log n) time MIS and 5-coloring for tree networks (which is time-optimal), as well as k-source multi-broadcast for general graphs in O(min(k,log n) * D + k log{(n M)/k}) rounds (for messages in {1,..., M}). This latter result improves on previous solutions when the number of sources k is sublogarithmic (k = o(log n)).

In this paper, we propose a formal energy model which allows an analytical study of energy consumption, for the first time in the context of population protocols (PP). In PP, anonymous and bounded memory agents move unpredictably and communicate in pairs. In order to illustrate the power and the usefulness of the proposed energy model, we develop a new power-aware protocol (EB-TTFM) for the task of data collection. The analytical results show that, in terms of energy consumption, EB-TTFM outperforms a known data collection protocol under certain conditions. Finally, we present a lower bound concerning energy consumption of any possible data collection protocol in PP, which also justifies the efficiency of EB-TTFM.

Population protocols are a popular model of distributed computing, in which randomly-interacting agents with little computational power cooperate to jointly perform computational tasks. Inspired by developments in molecular computation, and in particular DNA computing, recent algorithmic work has focused on the complexity of solving simple yet fundamental tasks in the population model, such as leader election (which requires stabilization to a single agent in a special "leader" state), and majority (in which agents must stabilize to a decision as to which of two possible initial states had higher initial count). Known results point towards an inherent trade-off between the time complexity of such algorithms, and the space complexity, i.e. size of the memory available to each agent. In this paper, we explore this trade-off and provide new upper and lower bounds for majority and leader election. First, we prove a unified lower bound, which relates the space available per node with the time complexity achievable by a protocol: for instance, our result implies that any protocol solving either of these tasks for $n$ agents using $O( \log \log n )$ states must take $Ω( n / \rm{polylog} n )$ expected time. This is the first result to characterize time complexity for protocols which employ super-constant number of states per node, and proves that fast, poly-logarithmic running times require protocols to have relatively large space costs. On the positive side, we give algorithms showing that fast, poly-logarithmic stabilization time can be achieved using $O( \log^2 n )$ space per node, in the case of both tasks. Overall, our results highlight a time complexity separation between $O(\log \log n)$ and $Θ( \log^2 n )$ state space size for both majority and leader election in population protocols, and introduce new techniques, which should be applicable more broadly.

A distributed computing system can be viewed as the result of the interplay between a distributed algorithm specifying the effects of a local event (e.g. reception of a message), and an adversary choosing the interleaving (schedule) of these events in the execution. In the context of large networks of mobile pairwise interacting agents (population protocols), the adversary models the mobility of the agents by choosing the successive pairs of interacting agents. For some problems, assuming that the adversary selects the schedule according to some probability distribution greatly helps to devise (almost) correct solutions. But how much randomness is really necessary? To what extent does a problem admit implementations that are robust against a "not so random" schedule? This paper takes a first step in addressing this question by borrowing the concept of T-randomness, 0 <= T <= 1, from algorithmic information theory. Roughly speaking, the value T fixes the entropy rate of the considered schedules. For instance, the case T = 1 corresponds, in a specific sense, to schedules in which the pairs of interacting agents are chosen independently and uniformly (perfect randomness). The holy grail question can then be precisely stated as determining the optimal entropy rate to solve a given problem. We first show that perfect randomness is never required. Precisely, if a finite-state algorithm solves a problem with 1-randomness, then this algorithm still solves the same problem with T-randomness for some T < 1. Second, we illustrate how to compute bounds on the optimal entropy rate of a specific problem, namely the leader election problem.

Population protocols are a model presented recently for networks with a very large, possibly unknown number of mobile agents having small memory. This model has certain advantages over alternative models (such as DTN) for such networks. However, it was shown that the computational power of this model is limited to semi-linear predicates only. Hence, various extensions were suggested.

We present a model for asynchronous mobile agent networks that takes into account the notion of speed of the agents. Then, we study the gathering problem (GP), in which an unknown number of anonymous agents have constant values they must deliver (only once) to a non mobile agent, the base station.