Brief Announcement: Fast Approximate Counting and Leader Election in Populations

Michail, Othon ORCID: 0000-0002-6234-3960, Spirakis, Paul G ORCID: 0000-0001-5396-3749 and Theofilatos, Michail ORCID: 0000-0002-3699-0179 (2018) Brief Announcement: Fast Approximate Counting and Leader Election in Populations. .

Text SIROCCO 2018 - Brief Announcement.pdf - Author Accepted Manuscript Download (237kB)

Abstract

Population protocols [2] are networks that consist of very weak computational entities (also called nodes or agents), regarding their individual capabilities and it has been shown that are able to perform complex computational tasks when they work collectively. Leader Election is the process of designating a single agent as the coordinator of some task distributed among several nodes. The nodes communicate among themselves in order to decide which of them will get into the leader state, starting from the same initial state q. An algorithm A solves the leader election problem if eventually the states of agents are divided into leader and follower, a unique leader remains elected and a follower can never become a leader. A randomized algorithm R solves the leader election problem if eventually only one leader remains in the system w.h.p.. Counting is the problem where nodes must determine the size n of the population. We call Approximate Counting the problem in which nodes must determine an estimation (formula presented) of the population size, where (formula presented). We call a the estimation parameter. Consider the setting in which an agent is in an initial state a, the rest n-1 agents are in state b and the only existing transition is (formula presented). This is the one-way epidemic process and it can be shown that the expected time to convergence under the uniform random scheduler is (formula presented)(e.g., [3]), thus parallel time (formula presented).

Item Type:	Conference or Workshop Item (Unspecified)
Depositing User:	Symplectic Admin
Date Deposited:	15 Mar 2019 14:45
Last Modified:	19 Jan 2023 01:01
DOI:	10.1007/978-3-030-01325-7_7
Related URLs:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3033399