Berenbrink, Petra ;
Elsässer, Robert ;
Friedetzky, Tom ;
Kaaser, Dominik ;
Kling, Peter ;
Radzik, Tomasz
A Population Protocol for Exact Majority with O(log5/3 n) Stabilization Time and Theta(log n) States
Abstract
A population protocol is a sequence of pairwise interactions of n agents. During one interaction, two randomly selected agents update their states by applying a deterministic transition function. The goal is to stabilize the system at a desired output property. The main performance objectives in designing such protocols are small number of states per agent and fast stabilization time.
We present a fast population protocol for the exactmajority problem, which uses Theta(log n) states (per agent) and stabilizes in O(log^{5/3} n) parallel time (i.e., in O(n log^{5/3} n) interactions) in expectation and with high probability. Alistarh et al. [SODA 2018] showed that exactmajority protocols which stabilize in expected O(n^{1Omega(1)}) parallel time and have the properties of monotonicity and output dominance require Omega(log n) states. Note that the properties mentioned above are satisfied by all known population protocols for exact majority, including ours. They also showed an O(log^2 n)time exactmajority protocol with O(log n) states, which, prior to our work, was the fastest exactmajority protocol with polylogarithmic number of states. The standard design framework for majority protocols is based on O(log n) phases and requires that all agents are well synchronized within each phase, leading naturally to upper bounds of the order of log^2 n because of Theta(log n) synchronization time per phase. We show how this framework can be tightened with weak synchronization to break the O(log^2 n) upper bound of previous protocols.
BibTeX  Entry
@InProceedings{berenbrink_et_al:LIPIcs:2018:9799,
author = {Petra Berenbrink and Robert Els{\"a}sser and Tom Friedetzky and Dominik Kaaser and Peter Kling and Tomasz Radzik},
title = {{A Population Protocol for Exact Majority with O(log5/3 n) Stabilization Time and Theta(log n) States}},
booktitle = {32nd International Symposium on Distributed Computing (DISC 2018)},
pages = {10:110:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770927},
ISSN = {18688969},
year = {2018},
volume = {121},
editor = {Ulrich Schmid and Josef Widder},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9799},
URN = {urn:nbn:de:0030drops97999},
doi = {10.4230/LIPIcs.DISC.2018.10},
annote = {Keywords: Population Protocols, Randomized Algorithms, Majority}
}
04.10.2018
Keywords: 

Population Protocols, Randomized Algorithms, Majority 
Seminar: 

32nd International Symposium on Distributed Computing (DISC 2018)

Issue date: 

2018 
Date of publication: 

04.10.2018 