Skip Navigation
*To search for student contact information, login to FlashLine and choose the "Directory" icon in the FlashLine masthead (blue bar).

Research News

Rizal Mohd Nor and Mikhail Nesterenko Win Best Student Paper Award

Posted Oct. 26, 2011
Rizal Mohd Nor, Mikhail Nesterenko (both of Kent State University) and Christian Scheideler (University of Padeborn) were awarded "best student paper" at the 13th International Symposium on Stabilization, Safety and Security of Distributed Systems (SSS) for their paper "Corona: A Stabilizing Deterministic Message-Passing Skip List".

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.