Self-Stabilizing Algorithms for Synchronous Unidirectional Rings.
Alain Mayer, Rafail Ostrovsky, Moti Yung
Abstract: 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) + S(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 |