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

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 KK-state mutual exclusion algorithm is employed to illustrate the new notion. The adapted algorithm is shown to be self-stabilizing if KK is greater than or equal to 2n−12n−1, quasi-self-stabilizing but not self-stabilizing if KK is less than 2n−12n−1 but greater than or equal to nn, and not quasi-self-stabilizing if KK is less than nn.