Quasi-self-stabilization of a distributed system assuming read/write atomicity
Self-stabilizing systems of the Dolev type were first introduced by Dolev etal. 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 Dijkstras K K -state mutual exclusion algorithm is employed to illustrate the new notion. The adapted algorithm is shown to be self-stabilizing if K K is greater than or equal to 2n?1 2 n ? 1 , quasi-self-stabilizing but not self-stabilizing if K K is less than 2n?1 2 n ? 1 but greater than or equal to n n , and not quasi-self-stabilizing if K K is less than n n .
quasi-self-stabilizing self-stabilizing read/write atomicity composite atomicity mutual exclusion computational models 0-configurations