×

Quasi-self-stabilization of a distributed system assuming read/write atomicity. (English) Zbl 1165.68321

Summary: Self-stabilizing systems of the Dolev type were first introduced by D. Dolev, C. Dwork, O. Waarts and M. Yung in their famous paper in 1993 [J. ACM 40, No. 1, 17–47 (1993; Zbl 0774.68017)]. In contrast to self-stabilizing systems of the Dijkstra type, such self-stabilizing systems assume the read/write atomicity model instead of the composite atomicity model. In this paper, we introduce the notion of quasi-self-stabilizing systems of the Dolev type. A naturally-adapted version from Dijkstra’s \(K\)-state mutual exclusion algorithm is employed to illustrate the new notion. The adapted algorithm is shown to be self-stabilizing if \(K\) is greater than or equal to \(2n - 1\), quasi-self-stabilizing but not self-stabilizing if \(K\) is less than \(2n - 1\) but greater than or equal to \(n\), and not quasi-self-stabilizing if \(K\) is less than \(n\).

MSC:

68M14 Distributed systems

Citations:

Zbl 0774.68017
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Dijkstra, E. W., Self-stabilizing systems in spite of distributed control, Commun. ACM, 17, 643-644 (1974) · Zbl 0305.68048
[2] L. Lamport, Solved problems, unsolved problems and non-problems in concurrency, invited address, in: Proc. of the Third Annual ACM Symposium on Principles of Distributed Computing, 1984 pp. 1-11; L. Lamport, Solved problems, unsolved problems and non-problems in concurrency, invited address, in: Proc. of the Third Annual ACM Symposium on Principles of Distributed Computing, 1984 pp. 1-11
[3] Huang, T. C., A self-stabilizing algorithm for the shortest path problem assuming read/write atomicity, J. Comput. Syst. Sci., 71, 70-85 (2005) · Zbl 1081.68004
[4] Huang, T. C., A self-stabilizing algorithm for the shortest path problem assuming the distributed demon, Comput. Math. Appl., 50, 671-681 (2005) · Zbl 1090.90007
[5] Dijkstra, E. W., Self-stabilization in spite of distributed control, (Selected Writings on Computing a Personal Perspective (1982), Springer-Verlag: Springer-Verlag Berlin, Heidelberg, New York), 41-46
[6] Dijkstra, E. W., A belated proof of self-stabilization, Distrib. Comput., 1, 5-6 (1986) · Zbl 0604.68015
[7] Dolev, S.; Israeli, A.; Moran, S., Self-stabilization of dynamic systems assuming only read/write atomicity, Distrib. Comput., 7, 3-16 (1993) · Zbl 1282.68084
[8] Dolev, S., Self-Stabilization (2000), MIT Press: MIT Press Massachusetts · Zbl 1026.93001
[9] Collin, Z.; Dolev, S., Self-stabilizing depth-first search, Inform. Process. Lett., 49, 297-301 (1994) · Zbl 0803.68041
[10] Huang, T. C.; Lin, J. C.; Mou, N., A self-stabilizing algorithm for the center-finding problem assuming read/write atomicity, Comput. Math. Appl., 48, 1667-1676 (2004) · Zbl 1075.68064
[11] S. Shukla, D.J. Rosenkrantz, S.S. Ravi, Observations on self-stabilizing graph algorithms on anonymous networks, in: Proc. of the 2nd Workshop on Self-Stabilizing Systems, WSS, 1995, pp. 7.1-7.15; S. Shukla, D.J. Rosenkrantz, S.S. Ravi, Observations on self-stabilizing graph algorithms on anonymous networks, in: Proc. of the 2nd Workshop on Self-Stabilizing Systems, WSS, 1995, pp. 7.1-7.15
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.