Brief announcement: Population Protocols for Leader Election and Exact Majority with O(log2 n) States and O(log2 n) Convergence Time

Andreas Bilke, Colin Cooper, Robert Elsässer, Tomasz Radzik

Research output: Chapter in Book/Report/Conference proceedingOther chapter contributionpeer-review

29 Citations (Scopus)


We consider the model of population protocols, which can be viewed as a sequence of random pairwise interactions of n agents (nodes). During each interaction, two agents v and w selected uniformly at random update their states on the basis of their current states, and the whole system should in long run converge towards a desired global final configuration. We study population protocols for two problems: the leader election and the exact majority voting. Both protocols use Θ(log2 n) states per agent and run in O(log2 n) rounds (the number of interactions divided by n), w.h.p. and in expectation, improving on the running time of the Θ(log2 n)-state protocols proposed recently by Alistarh et al. [SODA 2017]. Our protocols are based on the idea of agents counting their local interactions and rely on the probabilistic fact that the uniform random selection would limit the divergence of the individual counts.

Original languageEnglish
Title of host publicationPODC 2017 - Proceedings of the ACM Symposium on Principles of Distributed Computing
PublisherAssociation for Computing Machinery
Number of pages3
VolumePart F129314
ISBN (Electronic)9781450349925
Publication statusPublished - 26 Jul 2017
Event36th ACM Symposium on Principles of Distributed Computing, PODC 2017 - Washington, United States
Duration: 25 Jul 201727 Jul 2017


Conference36th ACM Symposium on Principles of Distributed Computing, PODC 2017
Country/TerritoryUnited States


  • Exact majority
  • Leader election
  • Population protocols

Cite this