Quasi-self-stabilization of a distributed system assuming read/write atomicity

✍ Scribed by Ji-Cherng Lin; Tetz C. Huang; Cheng-Zen Yang; Nathan Mou

• Publisher: Elsevier Science
• Year: 2009
• Tongue: English
• Weight: 591 KB
• Volume: 57
• Category: Article
• ISSN: 0898-1221
• DOI: 10.1016/j.camwa.2008.02.052

✦ Synopsis

Self-stabilizing systems of the Dolev type were first introduced by Dolev et al. in their famous paper in 1993. 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 selfstabilizing 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.