Campus Event Calendar
Event Entry
What and Who
Computation in Networks of Passively Mobile Finite-State Sensors
Prof. Dr. Michael Fischer
Yale University
Kolloquium
AG 1, AG 2, AG 3, AG 4, AG 5
AG Audience
Note: We use this to send email in the morning.
Date, Time and Location
Monday, 11 October 2004
13:30
90 Minutes
46.1 - MPII
024
Saarbrücken
Abstract
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.
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.
Contact
Gerhard Weikum
500
--email hidden
passcode not visible
logged in users only
Petra Schaaf, 10/07/2004 13:31 -- Created document.