Sensor nets are examples of a new kind of distributed
computing system where nodes are numerous but computationally weak, and
communication is limited and intermittant. Much work has focused on the
problem of gathering data from local sensors, filtering it, and routing
results back to a base station. We view a sensor net as a diffuse
computing engine and ask what its computational capabilities are. We
consider two models where nodes are identical, passively mobile, and
finite state. Any pair of nodes can communicate and change state if
they happen to encounter each other.
In the first model, encounters are chosen by an adversary scheduler,
subject only to a fairness constraint. Every predicate definable in
Presburger arithmetic is computable in the sense that every node
eventually stabilizes to the correct output. This family includes many
interesting predicates such as, "at least five sensors have input = 1"
or "the majority of nodes have sensor input = 1".
In the second model, encounters are chosen uniformly at random. Here,
every Presburger predicate can be computed in expected time O(n^2 log n)
with polynomially small error probability. By simulating counter
machines, we show that every predicate computed by a log space Turing
machine with unary input tape can be computed by our randomized model in
polynomial expected time with polynomially small error probability.
This is joint work with Dana Angluin, James Aspnes, Zoe Diamadi, and
Rene Peralta.