Oberseminar
Mahsa Eftekhari & Eric Severson University of California, Davis
April 23, 2021, 17:00, zoom: https://uni-hamburg.zoom.us/j/94889228942
Title: A stable majority population protocol using logarithmic time and states
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 ?(lognloglogn).