Fast Approximate Counting and Leader Election in Populations

2018/06/07 by Othon Michail, Michail, Othon, Paul G. Spirakis +3
Computer Science · Mathematics · #Bayesian Modeling and Causal Inference #Distributed #FOS: Computer and information sciences #Machine Learning and Algorithms #Markov Chains and Monte Carlo Methods #Parallel #and Cluster Computing (cs.DC)

paper · pdf · doi:10.48550/arxiv.1806.02638

openalex publication_date 2018/06/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the problems of leader election and population size counting for population protocols: networks of finite-state anonymous agents that interact randomly under a uniform random scheduler. We show a protocol for leader election that terminates in O(log_m(n) ⋅ log₂ n) parallel time, where m is a parameter, using O(max\m,log n\) states. By adjusting the parameter m between a constant and n, we obtain a single leader election protocol whose time and space can be smoothly traded off between O(log² n) to O(log n) time and O(log n) to O(n) states. Finally, we give a protocol which provides an upper bound n of the size n of the population, where n is at most n^a for some a>1. This protocol assumes the existence of a unique leader in the population and stabilizes in Θ(logn) parallel time, using constant number of states in every node, except the unique leader which is required to use Θ(log²n) states.

Related

• Exact size counting in uniform population protocols in nearly logarithmic time
• Population protocols for leader election and exact majority with O(log² n) states and O(log² n) convergence time
• Polylogarithmic-Time Leader Election in Population Protocols Using Polylogarithmic States
• Almost logarithmic-time space optimal leader election in population\n protocols
• Almost Time-Optimal Loosely-Stabilizing Leader Election on Arbitrary Graphs Without Identifiers in Population Protocols