Papers › A stable majority population protocol using logarithmic time and states
A stable majority population protocol using logarithmic time and states
David Doty, Mahsa Eftekhari, Eric Severson
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
We study population protocols, a model of distributed computing appropriate for modeling 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(logn) states (loglogn + O(1) bits of memory) and optimal expected time O(logn). The number of states O(logn) is known to be optimal for the class of stable protocols that are "output dominant" and "monotone". These are two natural constraints satisfied by our protocol, making it state-optimal for that class. We use, and develop novel analysis of, a key technique called a "fixed resolution clock" due to Gasieniec, Stachowiak, and Uznanski, who showed a majority protocol using O(logn) time and states that has a positive probability of error. Our protocol is *nonuniform*: the transition function has the value ⌈logn ⌉ encoded in it. We show that the protocol can be modified to be uniform, while increasing the state complexity to Θ(logn loglogn).
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections