Simple and Fast Approximate Counting and Leader Election in Populations

4^th December 2018, 14:00 NeST Software Lab
Michail Theofilatos

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 provide simple protocols for approximate counting of the size of the population and for leader election. We show a protocol for leader election that terminates in O(log^2(n)/log(m)) parallel time, where 1 <= m <= n 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^2(n)) to O(log(n)) time and O(log(n)) to O(n) states. We also 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 constant a>1. This protocol assumes the existence of a unique leader in the population and stabilizes in ?(log(n)) parallel time, using constant number of states in every node, except from the unique leader which is required to use ?(log^2(n)) states.

[Joint work with Othon Michail and Paul G. Spirakis]