Self-stabilizing behavior in networks of nondeterministically interacting sensors

Full textClick to download.
CitationIn Proc. of the 9th International Conference on Principles of Distributed Systems (OPODIS 2005)
AuthorsDana Angluin
James Aspnes
Michael J. Fischer
Hong Jiang


We consider anonymous, nondeterministically interacting devices deployed in a network of unknown size, and explore what kind of self-organizing behavior can be implemented in such networks. We show that in any ring there exists a self-stabilizing leader election protocol which uses O(log m) bits per node where m is the smallest positive integer that does not divide the size of the ring. We also show that round-robin token circulation can be done in this scenario with constant space per node. We give a protocol to enable anonymous nodes in regular graphs to distinguish different neighbors and a ring-direction protocol to establish consistent global direction, both of which use constant space per node. We also define a wide class of behaviors called elastic behaviors and show that nondeterminism in the transition function does not increase the class of elastic behaviors that have self-stabilizing implementations.

Back to publications
Back to previous page