| Self-stabilizing systems in spite of distributed control |
| Full text |
 Pdf
(215 KB)
|
Source
|
Communications of the ACM
archive
Volume 17 , Issue 11 (November 1974)
table of contents
Pages: 643 - 644
Year of Publication: 1974
ISSN:0001-0782
|
|
Author
|
|
| Publisher |
|
| Bibliometrics |
Downloads (6 Weeks): 40, Downloads (12 Months): 273, Citation Count: 231
|
|
|
 ABSTRACT
The synchronization task between loosely coupled cyclic sequential processes (as can be distinguished in, for instance, operating systems) can be viewed as keeping the relation “the system is in a legitimate state” invariant. As a result, each individual process step that could possibly cause violation of that relation has to be preceded by a test deciding whether the process in question is allowed to proceed or has to be delayed. The resulting design is readily—and quite systematically—implemented if the different processes can be granted mutually exclusive access to a common store in which “the current system state” is recorded.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
Scholten, C.S. Private communication.
|
CITED BY 231
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Baruch Awerbuch , Shay Kutten , Yishay Mansour , Boaz Patt-Shamir , George Varghese, Time optimal self-stabilizing synchronization, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.652-661, May 16-18, 1993, San Diego, California, United States
|
|
|
Joffroy Beauquier , Christophe Genolini , Shay Kutten, Optimal reactive k-stabilization: the case of mutual exclusion, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.209-218, May 04-06, 1999, Atlanta, Georgia, United States
|
|
|
|
|
|
Alain Mayer , Yoram Ofek , Rafail Ostrovsky , Moti Yung, Self-stabilizing symmetry breaking in constant-space (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.667-678, May 04-06, 1992, Victoria, British Columbia, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Eyal Kushilevitz , Rafail Ostrovsky , Adi Rosén, Log-space polynomial end-to-end communication, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.559-568, May 29-June 01, 1995, Las Vegas, Nevada, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Shlomi Dolev , Amos Israeli , Shlomo Moran, Resource bounds for self stabilizing message driven protocols, Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.281-293, August 19-21, 1991, Montreal, Quebec, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
M. J. Fischer , S. Moran , R. Rudich , G. Taubenfeld, The wakeup problem, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.106-116, May 13-17, 1990, Baltimore, Maryland, United States
|
|
|
|
|
|
Yehuda Afek , David S. Greenberg , Michael Merritt , Gadi Taubenfeld, Computing with faulty shared memory, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.47-58, August 10-12, 1992, Vancouver, British Columbia, Canada
|
|
|
Shlomo Moran , Gadi Taubenfeld , Irit Yadin, Concurrent counting, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.59-70, August 10-12, 1992, Vancouver, British Columbia, Canada
|
|
|
|
|
|
|
|
|
Joffroy Beauquier , Maria Gradinariu , Colette Johnen, Memory space requirements for self-stabilizing leader election protocols, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.199-207, May 04-06, 1999, Atlanta, Georgia, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Alain Mayer , Rafail Ostrovsky , Moti Yung, Self-stabilizing algorithms for synchronous unidirectional rings, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.564-573, January 28-30, 1996, Atlanta, Georgia, United States
|
|
|
Yehuda Afek , Danny Dolev , Eli Gafni , Michael Merritt , Nir Shavit, A bounded first-in, first-enabled solution to the l-exclusion problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.3, p.939-953, May 1994
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ankur Bhargava , Kishore Kothapalli , Chris Riley , Christian Scheideler , Mark Thober, Pagoda: a dynamic overlay network for routing, data management, and multicasting, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Shlomi Dolev , Mohamed G. Gouda , Marco Schneider, Memory requirements for silent stabilization, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.27-34, May 23-26, 1996, Philadelphia, Pennsylvania, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Kishore Kothapalli , Christian Scheideler , Melih Onus , Andrea Richa, Constant density spanners for wireless ad-hoc networks, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Paolo Costa , Vincent Gramoli , Márk Jelasity , Gian Paolo Jesi , Erwan Le Merrer , Alberto Montresor , Leonardo Querzoni, Exploring the interdisciplinary connections of gossip-based systems, ACM SIGOPS Operating Systems Review, v.41 n.5, October 2007
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Shlomi Dolev , Elad M. Schiller , Paul G. Spirakis , Philippas Tsigas, Strategies for repeated games with subsystem takeovers: implementable by deterministic and self-stabilizing automata (extended abstract), Proceedings of the 2nd International Conference on Autonomic Computing and Communication Systems, p.1-10, September 23-25, 2008, Turin, Italy
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Riko Jacob , Andrea Richa , Christian Scheideler , Stefan Schmid , Hanjo Täubig, A distributed polylogarithmic time algorithm for self-stabilizing skip graphs, Proceedings of the 28th ACM symposium on Principles of distributed computing, August 10-12, 2009, Calgary, AB, Canada
|
|
|
Zeev Collin , Rina Dechter , Shmuel Katz, On the feasibility of distributed constraint satisfaction, Proceedings of the 12th international joint conference on Artificial intelligence, p.318-324, August 24-30, 1991, Sydney, New South Wales, Australia
|
|
|
|
|
|
|
|
|
|
INDEX TERMS
Primary Classification:
D.
Software
D.4
OPERATING SYSTEMS
D.4.1
Process Management
Subjects:
Multiprocessing/multiprogramming/multitasking
Additional Classification:
D.
Software
D.4
OPERATING SYSTEMS
D.4.1
Process Management
Subjects:
Synchronization;
Mutual exclusion
General Terms:
Performance,
Reliability
Keywords:
distributed control,
error recovery,
harmonious cooperation,
multiprocessing,
mutual exclusion,
networks,
robustness,
self-repair,
self-stabilization,
sharing,
synchronization
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
