Space-Optimal Counting in Population Protocols - DIStributed Computing 2015 Access content directly
Conference Papers Year : 2015

Space-Optimal Counting in Population Protocols

Abstract

In this paper, we study the fundamental problem of counting, which consists in computing the size of a system. We consider the distributed communication model of population protocols of finite state, anonymous and asynchronous mobile devices (agents) communicating in pairs (according to a fairness condition). This work significantly improves the previous results known for counting in this model, in terms of (exact) space complexity. We present and prove correct the first space-optimal protocols solving the problem for two classical types of fairness, global and weak. Both protocols require no initialization of the counted agents. The protocol designed for global fairness, surprisingly, uses only one bit of memory (two states) per counted agent. The protocol, functioning under weak fairness, requires the necessary logP bits (P states, per counted agent) to be able to count up to P agents. Interestingly, this protocol exploits the intriguing Gros sequence of natural numbers, which is also used in the solutions to the Chinese Rings and the Hanoi Towers puzzles.
Fichier principal
Vignette du fichier
56.pdf (360.82 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01207253 , version 1 (30-09-2015)

Identifiers

Cite

Joffroy Beauquier, Janna Burman, Simon Clavière, Devan Sohier. Space-Optimal Counting in Population Protocols. DISC 2015, Toshimitsu Masuzawa; Koichi Wada, Oct 2015, Tokyo, Japan. ⟨10.1007/978-3-662-48653-5_42⟩. ⟨hal-01207253⟩
396 View
173 Download

Altmetric

Share

Gmail Facebook X LinkedIn More