| Full text | Click to download. |
| Citation | In Proc. of the 9th International Conference on
Principles of Distributed Systems (OPODIS 2005)
|
| Authors | Dana 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.