Rizal Mohd Nor and Mikhail Nesterenko Win Best Student Paper AwardPosted Oct. 26, 2011
A self-stabilizing program is guaranteed to eventually recover from an arbitrary transient fault. This property makes self-stabilization particularly suitable for fault tolerance engineering of such large scale failure-prone systems as peer-to-peer networks. However, proving self-stabilizing program correct is challenging since a large number of incorrect initial states has to be considered. This is especially true for realistic execution models such as message passing systems. Hence, the power of self-stabilization remains under-utilized in peer-to-peer algorithm design.
In this paper we present two necessary conditions for the existence of a self-stabilizing solution to a peer-to-peer problem: initially the state information has to form a weakly-connected graph and all the identifiers should be present in the system. On the basis of these results we present and rigorously prove correct Corona: a self-stabilizing deterministic skip list construction algorithm for message-passing systems.