Self-stabilization: beyond the token circulation

Augusto Ciuffoletti

To appear at Nineteenth Annual ACM SIGACT-SIGOPS Symposium on PRINCIPLES OF DISTRIBUTED COMPUTING (PODC 2000), Portland, Oregon, 16-19 July 2000


We give a formal statement of the original definition of self-stabilization, and explore its strengths and its limits. We prove that the original definition cannot be applied to systems using redundant paths among units, a key feature of the Internet architecture. We introduce an extended definition that admits redundant paths, and a sample algorithm that solves a simple handshake problem. Please consider this paper for a brief announcement in case it were not accepted as a regular paper. Keywords: Self-stabilization, fault-tolerant distributed system, handshake protocol.