King's College London

Research portal

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

Research output: Chapter in Book/Report/Conference proceedingOther chapter contribution

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

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

Conference

Conference36th ACM Symposium on Principles of Distributed Computing, PODC 2017
CountryUnited States
CityWashington
Period25/07/201727/07/2017

King's Authors

Abstract

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.

View graph of relations

© 2018 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454