## 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 Θ(log^{2} n) states per agent and run in O(log^{2} n) rounds (the number of interactions divided by n), w.h.p. and in expectation, improving on the running time of the Θ(log^{2} 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 language | English |
---|---|

Title of host publication | PODC 2017 - Proceedings of the ACM Symposium on Principles of Distributed Computing |

Publisher | Association for Computing Machinery |

Pages | 451-453 |

Number of pages | 3 |

Volume | Part F129314 |

ISBN (Electronic) | 9781450349925 |

DOIs | |

Publication status | Published - 26 Jul 2017 |

Event | 36th ACM Symposium on Principles of Distributed Computing, PODC 2017 - Washington, United States Duration: 25 Jul 2017 → 27 Jul 2017 |

### Conference

Conference | 36th ACM Symposium on Principles of Distributed Computing, PODC 2017 |
---|---|

Country/Territory | United States |

City | Washington |

Period | 25/07/2017 → 27/07/2017 |

## Keywords

- Exact majority
- Leader election
- Population protocols