More Like this

1. Time-Space Trade-offs in Population Protocols

   https://doi.org/10.1137/1.9781611974782.169  

   Alistarh, Dan; Aspnes, James; Eisenstat, David; Gelashvili, Rati; Rivest, Ronald L. (January 2017, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms)

   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 convergence to a single agent in a special “leader” state), and majority (in which agents must converge 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/polylogn) 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 convergence time can be achieved using O (log2 n) space per node, in the case of both tasks. Overall, our results highlight a time complexity separation between O (log log n) and Θ(log2 n) state space size for both majority and leader election in population protocols, and introduce new techniques, which should be applicable more broadly. 

   more » « less
2. Optimal Document Exchange and New Codes for Small Number of Insertions and Deletions

   Haeupler, Bernhard (October 2019, IEEE Symposium on Foundations of Computer Science)

   We give the first communication-optimal document exchange protocol. For any n and k 

   more » « less
3. The Computational Power of Discrete Chemical Reaction Networks with Bounded Executions

   https://doi.org/10.4230/LIPIcs.DISC.2024.20  

   Doty, David; Heckmann, Ben (October 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Alistarh, Dan (Ed.)

   Chemical reaction networks (CRNs) model systems where molecules interact according to a finite set of reactions such as A + B → C, representing that if a molecule of A and B collide, they disappear and a molecule of C is produced. CRNs can compute Boolean-valued predicates ϕ:ℕ^d → {0,1} and integer-valued functions f:ℕ^d → ℕ; for instance X₁ + X₂ → Y computes the function min(x₁,x₂), since starting with x_i copies of X_i, eventually min(x₁,x₂) copies of Y are produced. We study the computational power of execution bounded CRNs, in which only a finite number of reactions can occur from the initial configuration (e.g., ruling out reversible reactions such as A ⇌ B). The power and composability of such CRNs depend crucially on some other modeling choices that do not affect the computational power of CRNs with unbounded executions, namely whether an initial leader is present, and whether (for predicates) all species are required to "vote" for the Boolean output. If the CRN starts with an initial leader, and can allow only the leader to vote, then all semilinear predicates and functions can be stably computed in O(n log n) parallel time by execution bounded CRNs. However, if no initial leader is allowed, all species vote, and the CRN is "non-collapsing" (does not shrink from initially large to final O(1) size configurations), then execution bounded CRNs are severely limited, able to compute only eventually constant predicates. A key tool is a characterization of execution bounded CRNs as precisely those with a nonnegative linear potential function that is strictly decreased by every reaction [Czerner et al., 2024]. 

   more » « less
4. Dynamic size counting in population protocols

   David Doty and Mahsa Eftekhari (January 2022, SAND 2022: 1st Symposium on Algorithmic Foundations of Dynamic Networks)

   James Aspnes and Othon Michail (Ed.)

   The population protocol model describes a network of anonymous agents that interact asynchronously in pairs chosen at random. Each agent starts in the same initial state s. We introduce the *dynamic size counting* problem: approximately counting the number of agents in the presence of an adversary who at any time can remove any number of agents or add any number of new agents in state s. A valid solution requires that after each addition/removal event, resulting in population size n, with high probability each agent "quickly" computes the same constant-factor estimate of the value log2n (how quickly is called the *convergence* time), which remains the output of every agent for as long as possible (the *holding* time). Since the adversary can remove agents, the holding time is necessarily finite: even after the adversary stops altering the population, it is impossible to *stabilize* to an output that never again changes. We first show that a protocol solves the dynamic size counting problem if and only if it solves the *loosely-stabilizing counting* problem: that of estimating logn in a *fixed-size* population, but where the adversary can initialize each agent in an arbitrary state, with the same convergence time and holding time. We then show a protocol solving the loosely-stabilizing counting problem with the following guarantees: if the population size is n, M is the largest initial estimate of logn, and s is the maximum integer initially stored in any field of the agents' memory, we have expected convergence time O(logn+logM), expected polynomial holding time, and expected memory usage of O(log2(s)+(loglogn)2) bits. Interpreted as a dynamic size counting protocol, when changing from population size nprev to nnext, the convergence time is O(lognnext+loglognprev). 

   more » « less
5. Time and Space Optimal Counting in Population Protocols

   https://doi.org/10.4230/LIPIcs.OPODIS.2016.13  

   Aspnes, James; Beauquier, Joffroy; Burman, Janna; Sohier, Devan (January 2016, Leibniz international proceedings in informatics)

   This work concerns the general issue of combined optimality in terms of time and space complexity. In this context, we study the problem of counting resource-limited and passively mobile nodes in the model of population protocols, in which the space complexity is crucial. The counted nodes are memory-limited anonymous devices (called agents) communicating asynchronously in pairs (according to a fairness condition). Moreover, we assume that these agents are prone to failures so that they cannot be correctly initialized. This study considers two classical fairness conditions, and for each we investigate the issue of time optimality of (exact) counting given optimal space. First, with randomly interacting agents (probabilistic fairness), we present a ``non-guessing'' time optimal protocol of O(n log n) expected interactions given an optimal space of only one bit (for a population of size n). We prove the time optimality of such protocol. Then, under weak fairness (where every pair of agents interacts infinitely often), we show that a space optimal (semi-uniform) solution cannot converge faster than in Ω(2n) time, in terms of non-null transitions (i.e, the transitions that affect the states of the interacting agents). This result together with the time complexity analysis of an already known space optimal protocol shows that it is also optimal in time (given the optimal space constraints). 

   more » « less