# Counting with population protocols

Yves Mocquard, Emmanuelle Anceaume, James Aspnes, Yann Busnel, and Bruno Sericola.
Counting with population protocols.
*2015 IEEE 14th International Symposium on Network Computing and Applications*, September 2015, pp. 35–42.

## Abstract

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.

- IEEE NCA15 proceedings version:
**PDF**.
- Slides from Emmanuelle Anceaume's NCA15 talk: PDF.

## BibTeX

Download@inproceedings{MocquardAABS2015,
author = {Yves Mocquard and Emmanuelle Anceaume and James Aspnes and Yann Busnel and Bruno Sericola},
title = {Counting with population protocols},
booktitle = {2015 IEEE 14th International Symposium on Network Computing and Applications},
mon = sep,
year = {2015},
pages = {35--42}
}

Consolidated BibTeX file

Return to James Aspnes's publications

Return to James Aspnes's home page