A population protocol for exact majority with $O(\log^{5/3} n)$ stabilization time and asymptotically optimal number of states

Berenbrink, Petra; Elsässer, Robert; Friedetzky, Tom; Kaaser, Dominik; Kling, Peter; Radzik, Tomasz

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 exact-majority 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 exact-majority protocols which stabilize in expected O(n^{1-Omega(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 exact-majority protocol with O(log n) states, which, prior to our work, was the fastest exact-majority 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.

Citation

Berenbrink, P., Elsässer, R., Friedetzky, T., Kaaser, D., Kling, P., & Radzik, T. (2018, October). A population protocol for exact majority with $O(\log^{5/3} n)$ stabilization time and asymptotically optimal number of states. Presented at International Symposium on DIStributed Computing (DISC), New Orleans, USA

• Presentation Conference Type: Conference Paper (published)
• Conference Name: International Symposium on DIStributed Computing (DISC)
• Start Date: Oct 15, 2018
• End Date: Oct 19, 2018
• Acceptance Date: Jul 13, 2018
• Online Publication Date: Sep 28, 2018
• Publication Date: Oct 15, 2018
• Deposit Date: Sep 11, 2018
• Publicly Available Date: Dec 13, 2018
• Pages: 10:1-10:18
• Series Title: Leibniz International Proceedings in Informatics (LIPIcs)
• Series Number: 121
• Series ISSN: 1868-8969
• Book Title: 32nd International Symposium on Distributed Computing (DISC 2018).
• DOI: https://doi.org/10.4230/lipics.disc.2018.10
• Public URL: https://durham-repository.worktribe.com/output/1144536
• Related Public URLs: https://arxiv.org/abs/1805.05157