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
Abstract
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.