Recent Results in Population Protocols for Exact Majority and Leader Election

Abstract

Population protocols act in a simple and natural framework to solve fun- damental problems in networks. Given a population of n anonymous nodes (agents), a scheduler chooses in discrete time steps two nodes for interac- tion, which then exchange their current states and perform a so called state transition. We focus on the random scheduler, which selects in each step two nodes uniformly at random for interaction, and on the problems of exact ma- jority and leader election. In exact majority, initially the nodes possess one of two opinions, A or B, and the population is required to converge to a con- figuration, in which every node has the opinion of the initial majority. In leader election, each node starts with the same state, and the system should converge to a configuration, with exactly one node in a leader state. The goal is to design protocols, which require a small number of states and reach a correct final configuration as fast as possible. In this paper, we give an overview of the population protocols for these problems, focusing on the most recent results.