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, w...

Full description

Saved in:
Bibliographic Details
Published in:Computers & mathematics with applications (1987) 2009, Vol.57 (2), p.184-194
Main Authors: Lin, Ji-Cherng, Huang, Tetz C., Yang, Cheng-Zen, Mou, Nathan
Format: Article
Language:English
Subjects:
0-configurations
Algorithms
Composite atomicity
Computational models
Computer networks
Computer simulation
Mathematical models
Mutual exclusion
Quasi-self-stabilizing
Read/write atomicity
Self-stabilizing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 2 n − 1 , quasi-self-stabilizing but not self-stabilizing if K is less than 2 n − 1 but greater than or equal to n , and not quasi-self-stabilizing if K is less than n .
ISSN:0898-1221
1873-7668
DOI:10.1016/j.camwa.2008.02.052