computation in networks of passively mobile finite-state sensors
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 stable computation of a function or predicate, and give protocols that stably compute functions in a class including Boolean combinations of threshold- k , parity, majority, and simple arithmetic. We prove that all stably 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 ? RL . Several open problems and promising future directions are discussed.
mobile agent finite-state agent stable computation diffuse computation intermittent communication sensor net