Computation in Networks of Passively Mobile Finite-State Sensors
YALE UNIV NEW HAVEN CT DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
Suppose we have equipped each bird in a particular flock with a sensor that can determine whether the birds 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.
- Computer Programming and Software