Computation in Networks of Passively Mobile Finite-State Sensors
Abstract
Suppose we have equipped each bird in a particular flock with a sensor that can determine whether the bird's temperature is elevated or not, and we wish to know whether at least 5 birds in the flock have elevated temperatures. We assume that the sensors are quite limited: each sensor has a constant number of bits of memory and can respond to a global start signal, and two sensors can communicate only when they are sufficiently close to each other. In this scenario, the sensors are mobile, but have no control over how they move, that is, they are passively mobile. Initially, we assume that the underlying pattern of movement guarantees a fairness condition on the interactions: every pair of birds in the flock repeatedly come su ciently close to each other for their sensors to communicate. Under these assumptions, there is a simple protocol ensuring that every sensor eventually contains the correct answer. At the global start signal, each sensor makes a measurement, resulting in a 1 (elevated temperature) or 0 (not elevated temperature) in a counter that can hold values from 0 to 4. When two sensors communicate, one of them sets its counter to the sum of the two counters, and the other one sets its counter to 0. If two counters ever sum to at least 5, the sensors go into a special alert state, which is then copied by every sensor that encounters it. The output of a sensor is 0 if it is not in the alert state, and 1 if it is in the alert state. If we wait a sufficient interval after we issue the global reset, we can retrieve the correct answer from any of the sensors. Now consider the question of whether at least 5% of the birds in the flock have elevated temperatures. Is there a protocol to answer this question in the same sense, without assumptions about the size of the flock? In Section 3 we show that such a protocol exists.
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 23, 2004
- Accession Number
- ADA461359
Entities
People
- Dana Angluin
- James Aspnes
- Michael J. Fischer
- Rene Peralta
- Zoe Diamadi
Organizations
- Yale University