Dan Alistarh, James Aspnes, and Rati Gelashvili. Space-optimal majority in population protocols. Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), January 2018, pp. 2221–2239.
Population protocols are a popular model of distributed computing, in which n agents with limited local state interact randomly, and cooperate to collectively compute global predicates. Inspired by recent developments in DNA programming, an extensive series of papers, across different communities, has examined the computability and complexity characteristics of this model. Majority, or consensus, is a central task in this model, in which agents need to collectively reach a decision as to which one of two initial states A or B had higher initial count. Two complexity metrics are important: the time that a protocol requires to stabilize to a stable output decision, and the state space size that each agent requires to do so.
It is currently known that majority requires Ω(log log n) states per agent to allow for fast (polylogarithmic time) stabilization, and that O(log² n) states are sufficient. Thus, there is an exponential gap between the upper and lower bounds for this problem.
We address this question. On the negative side, we provide a new lower bound of Ω(log n) states for any protocol which converges to a stable output in O(n c) time, for any c ≤ 1 constant. This result is conditional on basic monotonicity and output assumptions, satisfied by all known protocols. Technically, it represents a significant departure from previous lower bounds, in that it does not rely on the existence of dense configurations. Instead, we introduce a new generalized surgery technique to prove the existence of incorrect executions for any algorithm which would contradict the lower bound.
On the positive side, we give a new algorithm for majority which uses O(log n) states, and converges in O(log² n) time. Central to the algorithm is a new leaderless phase clock technique, which allows nodes to synchronize in phases of Θ(n log n) consecutive interactions using O(log n) states per node, exploiting a new connection between population protocols and power-of-two-choices load balancing mechanisms. Besides logarithmic-state majority, we employ the phase clock to build a new leader election algorithm with a state space of size O(log n), which stabilizes in O(log² n) expected time.
@inproceedings{AlistarhAG2018,
author = {Dan Alistarh and
James Aspnes and
Rati Gelashvili},
editor = {Artur Czumaj},
title = {Space-Optimal Majority in Population Protocols},
booktitle = {Proceedings of the Twenty-Ninth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2018, New Orleans, LA, USA, January 7-10, 2018},
pages = {2221--2239},
publisher = {{SIAM}},
year = {2018},
url = {https://doi.org/10.1137/1.9781611975031.144},
doi = {10.1137/1.9781611975031.144},
timestamp = {Thu, 04 Jan 2018 13:55:11 +0100},
biburl = {https://dblp.org/rec/bib/conf/soda/AlistarhAG18},
bibsource = {dblp computer science bibliography, https://dblp.org}
}