Dana Angluin, James Aspnes, Michael J. Fischer, and Hong Jiang. Self-stabilizing population protocols. Principles of Distributed Systems; 9th International Conference, OPODIS 2005; Pisa, Italy; December 2005; Revised Selected Papers, December 2005, pp. 103–117. ACM Transactions on Autonomous and Adaptive Systems 3(4):13. (Special issue on stabilization, safety, and security of distributed systems.)
This paper studies self-stabilization in networks of anonymous, asynchronously interacting agents where the size of the network is unknown. Dijkstra-style round-robin token circulation can be done deterministically with constant space per node in this model. Constant-space protocols are given for leader election in rings, local-addressing in degree-bounded graphs, and establishing consistent global direction in an undirected ring. A protocol to construct a spanning tree in regular graphs using O(log D) memory is also given, where D is the diameter of the graph. A general method for eliminating nondeterministic transitions from the self-stabilizing implementation of a large family of behaviors is used to simplify the constructions, and general conditions under which protocol composition preserves behavior are used in proving their correctness.
@article(AngluinAFJ2008,
title="Self-stabilizing population protocols",
author="Dana Angluin and James Aspnes and Michael J. Fischer and Hong Jiang",
journal="ACM Transactions on Autonomous and Adaptive Systems",
volume=3,
number=4,
pages={13},
month=nov,
year=2008,
)