Implementation of Dijkstra’s Token Circulation on Sensor Network

摘要

Sensor networks can consist of large number of sensors. Often, sensors networks use low cost units and thus a subject to malfunctions that can bring the system to inconsistent states. After deployment, the system can be situated in places that are hard to reach and therefore manual reboot operations are undesirable and even unfeasible. Therefore, it is imperative to consider the eventual recovery of arbitrary fault when designing sensor networks. Dijkstra’s algorithm is an important foundation of self-managing computer system and fault-tolerance computing system in distributed systems, since it allows a distributed system to recover from arbitrary starting state within a finite time. The arbitrary starting state ca model arbitrary failure (as long as the code segment stays correct).Another key advantage of Dijkstra’s asynchronous algorithm is that no global clock is needed. This project tests an implementation of Dijkstra’s algorithm using snapshotting techniques that we developed in an earlier work. These sensors can initiate from any state but they come into a consistent one after several cycles of running. We demonstrate the usefulness of our testing technique.