Counting with Population Protocols

Yves Mocquard (1) , Emmanuelle Anceaume (2) , James Aspnes (3) , Yann Busnel (4) , Bruno Sericola (5)

1 UR - Université de Rennes
2 CIDRE - Confidentialité, Intégrité, Disponibilité et Répartition
3 YALE - Department of Computer Science
4 ENSAI - Ecole Nationale de la Statistique et de l'Analyse de l'Information [Bruz]
5 DIONYSOS - Dependability Interoperability and perfOrmance aNalYsiS Of networkS

—The population protocol model provides theoretical foundations for analyzing the properties emerging from simple and pairwise interactions among a very large number n of anonymous agents. The problem tackled in this paper is the following one: is there an efficient population protocol that exactly counts the difference κ between the number of agents that initially and independently set their state to A and the one that initially set it to B, assuming that each agent only uses a finite set of states ? We propose a solution which guarantees with any high probability that after O (log n) interactions any agent outputs the exact value of κ. Simulation results illustrate our theoretical analysis.

Mots clés: —Population protocol; Majority algorithm; Perfor-mance evaluation; Counting problem

Domaines: Informatique [cs]; Algorithme et structure de données [cs.DS]; Calcul parallèle, distribué et partagé [cs.DC]

Yves Mocquard, Emmanuelle Anceaume, James Aspnes, Yann Busnel, Bruno Sericola. Counting with Population Protocols. 2015. ⟨hal-01170575⟩