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.) Awarded the 2020 ACM-EATCS Dijkstra Prize in Distributed Computing. An earlier version appeared in Twenty-Third Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, July 2004, pp. 290–299.
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.
@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}
)