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. Submitted to ACM Transactions on Autonomous and Adaptive Systems, Special Issue on Stabilization, Safety, and Security of Distributed Systems, March 2007. Last revised August 2008.
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.
@inproceedings(AngluinAFJ2005,
title="Self-stabilizing population protocols",
author="Dana Angluin and James Aspnes and Michael J. Fischer and Hong Jiang",
booktitle="Principles of Distributed Systems;
9th International Conference, OPODIS 2005;
Pisa, Italy; December 2005; Revised Selected Papers",
series="Lecture Notes in Computer Science",
volume=3974,
month=dec,
year=2005,
pages={103--117}
)