Rafail Ostrovsky - Publications

Self-Stabilizing Algorithms for Synchronous Unidirectional Rings.

Alain Mayer, Rafail Ostrovsky, Moti Yung


Our main result is a {\bf protocol-compiler} that transforms any self-stabilizing protocol P for a (synchronous or asynchronous) {\bf bidirectional} ring to a self-stabilizing protocol P which runs on the synchronous {\bf unidirectional} ring. P requires O(S_{LE}(n) + (n)) space and has expected stabilization time O(T_{LE}(n) + n^2 + nT(n)), where S(n) (T(n)) is the space (time) performance of P and S_{LE}(n) (T_{LE}(n)) is the space (time) performance of a self-stabilizing leader-election protocol on a bidirectional ring. As subroutines, we also solve the problems of leader election and round-robin token management in our setting.

comment: Appeared In Proceedings of Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-96)

Fetch PostScript file of the paper     Fetch PDF file of the paper

Back to Publications List