Brief announcement: Exact size counting in uniform population protocols in nearly logarithmic time

Doty, D, Eftekhari, M, Michail, O ORCID: 0000-0002-6234-3960, Spirakis, PG ORCID: 0000-0001-5396-3749 and Theofilatos, M ORCID: 0000-0002-3699-0179 (2018) Brief announcement: Exact size counting in uniform population protocols in nearly logarithmic time. In: International Symposium on Distributed Computing (DISC).

	Text 1805.04832.pdf - Submitted version Download (878kB)
	Text DEMST-disc18.pdf - Author Accepted Manuscript Download (278kB)

Official URL: http://www.dagstuhl.de/dagpub/978-3-95977-092-7

Abstract

We study population protocols: networks of anonymous agents whose pairwise interactions are chosen uniformly at random. The size counting problem is that of calculating the exact number n of agents in the population, assuming no leader (each agent starts in the same state). We give the first protocol that solves this problem in sublinear time. The protocol converges in O(log n log log n) time and uses O(n 60 ) states (O(1)+60 log n bits of memory per agent) with probability 1−O( lognlog n ). The time to converge is also O(log n log log n) in expectation. Crucially, unlike most published protocols with ω(1) states, our protocol is uniform: it uses the same transition algorithm for any population size, so does not need an estimate of the population size to be embedded into the algorithm.

Item Type:	Conference or Workshop Item (Unspecified)
Depositing User:	Symplectic Admin
Date Deposited:	22 Aug 2018 08:02
Last Modified:	19 Jan 2023 01:26
DOI:	10.4230/LIPIcs.DISC.2018.46
Related URLs:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3025362