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. To appear, ACM Transactions on Autonomous and Adaptive Systems, 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.
@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}
)