A RANDOMIZED 1-LATENT, TIME-ADAPTIVE AND SAFE SELF-STABILIZING MUTUAL EXCLUSION PROTOCOL
Abstract
For bidirectional rings, there have been proposed self-stabilizing mutual exclusion protocols, which are either time-adaptive (i.e., efficient in recovery) or 1-latent (i.e., efficient in legal execution) but not both. This paper proposes a randomized self-stabilizing mutual exclusion protocol that inherits both of the advantages from them: It is 1-latent in the sense that the privilege is circulated in a linear round (i.e., very intuitively, the privilege is transferred from a process to another by a "step"), provided that the system always stays in legitimate configurations, and is weakly time-adaptive in the sense that the system stabilizes from any configuration c in O(f) steps with a high probability, where f is the number of corrupted processes in c. It also guarantees with a high probability that there is at most one privilege even while converging to a legitimate configuration.
References
- Information Processing Letters 57, 301 (1996), DOI: 10.1016/0020-0190(96)00026-9. Crossref, ISI, Google Scholar
- Information Processing Letters 59, 281 (1996), DOI: 10.1016/0020-0190(96)00121-4. Crossref, ISI, Google Scholar
S. Ghosh , Fault-containing self-stabilizing algorithms, Proceedings of the 15th Annual ACM Symposium on Principles of Distributed Computing (1996) pp. 45–54. Google Scholar- Information Processing Letters 73, 145 (2000), DOI: 10.1016/S0020-0190(00)00006-5. Crossref, ISI, Google Scholar
- Information Processing Letters 73, 41 (2000), DOI: 10.1016/S0020-0190(99)00164-7. Crossref, ISI, Google Scholar
J. Beauquier , C. Genolini and S. Kutten , Optimal reactive k-stabilization: the case of mutual exclusion, Proceedings of the 18th Annual ACM Symposium on Principles of Distributed Computing (1999) pp. 209–218. Google ScholarS. Kutten and B. Patt-Shamir , Time-adaptive self-stabilization, Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing (1997) pp. 149–158. Google Scholar- Distributed Computing 13, 1 (2000), DOI: 10.1007/s004460050001. Crossref, ISI, Google Scholar
- Journal of Parallel and Distributed Computing 62(5), 865 (2002), DOI: 10.1006/jpdc.2001.1826. Crossref, ISI, Google Scholar
- Journal of Parallel and Distributed Computing 62(5), 745 (2002), DOI: 10.1006/jpdc.2001.1823. Crossref, ISI, Google Scholar
- IEICE Transactions on Fundamentals E85-A(5), 949 (2002). Google Scholar
- Communications of the ACM 17(11), 643 (1974), DOI: 10.1145/361179.361202. Crossref, ISI, Google Scholar
- ACM Transactions on Programming Languages and Systems 11, 330 (1989), DOI: 10.1145/63264.63403. Crossref, ISI, Google Scholar
J. Beauquier , Self-stabilizing local mutual exclusion and daemon refinement, Proceedings of the Distributed Computing 14th International Conference (DISC00),LNCS 1914 (Springer, 2000) pp. 223–237. Google ScholarC. Johnen , Service time optimal self-stabilizing token circulation protocol on anonymous unidirectional rings, Proceedings of 21st IEEE Symposium on Reliable Distributed Systems (SRDS 02) (2002) pp. 80–89. Google Scholar- Distributed Computing 1, 5 (1986), DOI: 10.1007/BF01843566. Crossref, ISI, Google Scholar
- IEEE Transactions on Parallel and Distributed Systems 8(2), 154 (1997), DOI: 10.1109/71.577257. Crossref, ISI, Google Scholar
- R. Segala, "Modeling and verification of randomized distributed real-time systems," Ph.D Thesis, MIT, 1995 . Google Scholar


