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) + (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 |