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 selforganizing behavior can be implemented in such networks. We show that in any ring there exists a selfstabilizing 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 roundrobin 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 ringdirection 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 selfstabilizing implementations.