A time and space optimal stable population protocol solving exact majority

9^th December 2021, 00:00
Leszek Gasieniec

Abstract

We study population protocols, a model of distributed computing appropriate for modelling well-mixed chemical reaction networks and other physical systems where agents exchange information in pairwise interactions, but have no control over their schedule of interaction partners. The well-studied majority problem is that of determining in an initial population of n agents, each with one of two opinions A or B, whether there are more A, more B, or a tie. A stable protocol solves this problem with probability 1 by eventually entering a configuration in which all agents agree on a correct consensus decision of A, B, or T, from which the consensus cannot change.

We describe a protocol that solves this problem using O(log n) states loglog n +O(1) bits of memory and optimal expected time O(log n). The number of states O(log n) is known to be optimal for the class of poly-logarithmic time stable protocols that are output dominant and monotone. These are two natural constraints satisfied by our protocol, making it simultaneously time- and state-optimal for that class. We introduce a key technique called a fixed resolution clock to achieve partial synchronization. Our protocol is non-uniform, i.e., the transition function has the value ?log n? encoded in it. We show that the protocol can be modified to be uniform, while increasing the state complexity to ?(log n loglog n).

This is a joint work with David Doty, Mahsa Eftekhari, Eric Severson (UC Davis, USA) and Grzegorz Stachowiak, Przemys?aw Uzna?ski (Wroclaw U, Poland).

Additional Materials

• https://arxiv.org/abs/2106.10201