# Computation in networks of passively mobile finite-state sensors

Dana Angluin, James Aspnes, Zoë Diamadi, Michael J. Fischer, and René Peralta.
Computation in networks of passively mobile finite-state sensors.
*Distributed Computing* 18(4):235–253, March 2006. (PODC 2004 special issue.)
An earlier version appeared in
*Twenty-Third Annual ACM SIGACT-SIGOPS Symposium on
Principles of Distributed Computing*, July 2004, pp. 290–299.

## Abstract

We explore the computational power of networks of small
resource-limited mobile agents.
We define two new models of computation based on pairwise interactions of
finite-state agents in populations of finite but unbounded size.
With a fairness condition on interactions, we define
the concept of eventual computation of a function or predicate,
and give protocols that eventually compute functions in a class
including Boolean combinations of threshold-k, parity, majority,
and simple arithmetic.
We prove that all eventually computable predicates are in NL.
With uniform random sampling of pairs to interact, we define
the model of conjugating automata and show that any counter machine
with O(1) counters of capacity O(n) can be simulated with
high probability by a protocol in a population of size n.
We prove that all predicates computable with high probability
in this model are in P intersect RL.
Several open problems and promising future directions are discussed.

- Technical report: PDF.
- PODC proceedings version: PDF.
- Journal version:
**PDF**.

## BibTeX

Download@article(AngluinADFP2006,
title="Computation in networks of passively mobile finite-state sensors",
author="Dana Angluin and James Aspnes and Zo{\"e} Diamadi and Michael J. Fischer and Ren\'e Peralta",
journal="Distributed Computing",
month=mar,
year=2006,
pages={235--253}
)

Consolidated BibTeX file

Return to James Aspnes's publications

Return to James Aspnes's home page