Dan Alistarh, James Aspnes, and Rati Gelashvili. Space-optimal majority in population protocols. Accepted to SODA 2018.

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.

@unpublished{AlistarhAG2017, author = {Dan Alistarh and James Aspnes and Rati Gelashvili}, title = {Space-optimal majority in population protocols}, month = jul, year = 2017, note={Accepted to SODA 2018} }

Consolidated BibTeX file

Return to James Aspnes's publications

Return to James Aspnes's home page