Simple and Fast Approximate Counting and Leader Election in Populations

Michail, Othon ORCID: 0000-0002-6234-3960, Spirakis, PG ORCID: 0000-0001-5396-3749 and Theofilatos, Michail ORCID: 0000-0002-3699-0179 (2018) Simple and Fast Approximate Counting and Leader Election in Populations. In: 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2018), 2018-11-4 - 2018-11-7, Tokyo, Japan..

Text SSS_2018_paper_22.pdf - Author Accepted Manuscript Download (1MB)

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 (Formula Presented) 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(log2 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 na for some constant 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 from the unique leader which is required to use Θ(log2 n) states.

Item Type:	Conference or Workshop Item (Unspecified)
Uncontrolled Keywords:	Population protocol, Epidemic, Leader election, Counting, Approximate counting, Polylogarithmic time protocol
Depositing User:	Symplectic Admin
Date Deposited:	11 Sep 2018 11:10
Last Modified:	19 Jan 2023 01:25
DOI:	10.1007/978-3-030-03232-6_11
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3025734