article

Free access

Self-stabilization

Author:

Marco SchneiderAuthors Info & Claims

ACM Computing Surveys (CSUR), Volume 25, Issue 1

Pages 45 - 67

https://doi.org/10.1145/151254.151256

Published: 01 March 1993 Publication History

PDF eReader

Abstract

In 1973 Dijkstra introduced to computer science the notion of self-stabilization in the context of distributed systems. He defined a system as self-stabilizing when “regardless of its initial state, it is guaranteed to arrive at a legitimate state in a finite number of steps.” A system which is not self-stabilizing may stay in an illegitimate state forever. Dijkstra's notion of self-stabilization, which originally had a very narrow scope of application, is proving to encompass a formal and unified approach to fault tolerance under a model of transient failures for distributed systems. In this paper we define self-stabilization, examine its significance in the context of fault tolerance, define the important research themes that have arisen from it, and discuss the relevant results. In addition to the issues arising from Dijkstra's original presentation as well as several related issues, we discuss methodologies for designing self-stabilizing systems, the role of compilers with respect to self-stabilization, and some of the factors that prevent self-stabilization.

References

[1]

ABADIR, M. S., AND GOUDA, M.G. 1992. The stabilizing computer. In Proceedings of the 1992 International Conference on Parallel and Distributed Systems. (Dec.).

Google Scholar

[2]

AFEK, Y., AND BROWN, G. 1989. Self-stabilization of the alternating-bit protocol. In Proceedings of the 8th Symposium olz Reliable Dlstrtbuted Systems, 80-83.

Google Scholar

[3]

AFEK, Y., KUTTEN, S., AND YUNG, M. 1990. Memory-efficient self-~tabilization on general networks. In Proceedtngs of the 4th Internattonal Workshop on Distributed Algomthms (Bari, Italy, Sept.). In Lecture Notes in Computer Science, vol. 486. Springer-Verlag, New York, 15-28.

Crossref

Google Scholar

[4]

ARORA, A. 1992. A foundation for fault-tolerant computing. Ph.D. dissertation, Dept of Computer Sciences, Univ. of Texas at Austin.

Crossref

Google Scholar

[5]

AmORA, A., AND GOUDA, M.G. 1992. Closure and convergence: A foundation for fault-tolerant computing. In Proceedzngs of the 22rid Internatzonal Conference on Fault-Tolerant Computing Systems.

Google Scholar

[6]

ARORA, A., AND GOUDA, M. G. 1990. Distributed reset. In Proceedings of the lOth Conference on Foundatmns of Software Technology and Theorettcal Computer Science (Dec.). Also in Lecture Notes on Computer Science, vol. 472. Springer- Verlag, New York.

Crossref

Google Scholar

[7]

ARORA, A., DOLEV, S., AND GOUDA, M. G. 1991. Maintaining digital clocks in step In Proceedrags of the 5th Internattonal Workshop on Distrzbuted Algorzthms (Oct.). Also in Parall. Process. Lett. 1, 1 (Sept.), 11 18.

Crossref

Google Scholar

[8]

AWERBUCH, B., AND VARGHESE, G 1991 Distributed program checking: A paradigTn for building self-stabilizing distributed protocols. In Proceedings of the 32nd IEEE Sympostun't on Foundations of Computer Science (Oct.). IEEE, New York

Crossref

Google Scholar

[9]

AWERBUCH, B., PATT, B. AND VARGHHESE, G. 1991. Self-stabilization by local checking and correction. In Proceedings of the 32nd IEEE Symposzum on Foundations of Computer Science, (Oct.). IEEE, New York.

Crossref

Google Scholar

[10]

BASTIM, F., YEN, I., AND CHEN, I. 1988. A class of inherently fault tolerant distributed programs. IEEE Trans. So/ha Eng. 14, 1432-1442.

Crossref

Google Scholar

[11]

BASTANI, F., YEN, I., AND ZI.IAO, Y. 1989. On self, stabilization, non-determinism, and inherent fault tolerance. In Proceedings of the MCC Workshop on Self-Stabilizing Systems. MCC Tech. Rep. STP-379-89.

Google Scholar

[12]

BROWNE, J. C., EMERSON, A, GOUDA, M., MIRANKER, D., MOK, A., AND ROSmR, L. 1990 Boundedtime fault-tolerant rule-based systems. Telemotzcs Informat. 7, 3/4, 441-454.

Google Scholar

[13]

BROWN, G. M., GOUDA. M. G., AND WU, C.-L. 1989. Token systems that self-stabihze. {EEE Trans. Comput. 38, 6 (June 1989l, 845-852.

Crossref

Google Scholar

[14]

BURNS, J.E. 1987. Self-stabilizing rings without demons. Tech. Rep. GIT-ICS-87/36, Georgia Inst of Technology.

Google Scholar

[15]

BURNS, J. E., AND PACHL, J. 1989. Uniform selfstabilizing rings. ACM Trans Programm Lang. Syst. 11,330 344

Crossref

Google Scholar

[16]

BURNS, J. E, GOUDA, M. G., AND MmuEa, R. E 1990 Stabilization and pseudo-stabilization. Tech. Rep. TR-90-13, Dept. of Computer Sciences, Univ. of Texas at Austin

Crossref

Google Scholar

[17]

BURNS, J. E, GOUDA, M. G., AND MmLER, R. E 1989. On relaxing interleaving assumptions. In Proceedings of the MCC Workshop on Self- Stabzhzzng Systems MCC Tech. Rep. STP-379- 89.

Google Scholar

[18]

CHANDY, K. M., AND LAMPORT, L 1985. Distributed snapshots: Determining global states of distributed systems. ACM Trans. Comput. Syst. 3, 1, 63-75.

Crossref

Google Scholar

[19]

CnANDY, K. M., AND MISRA, J. 1988. Parallel Program Design: A Foundation. Addison-Wesley, New York.

Crossref

Google Scholar

[20]

CHANG, E. J. H, GONNET, G. H. AND ROTEM,'D. 1987. On the costs of self-stabilization. Ipf Process Lett. 24, (1987), 311-316.

Crossref

Google Scholar

[21]

CHEN, N. S., Yu, F. P., AND HUANG, S.T. 1991. A self-stabilizing algorithm for constructing spanning' trees. Inf. Process. Lett., 39, (1991), 147 151.

Crossref

Google Scholar

[22]

CHENG, A. M.K. 1990. Analysis and synthesis of real-time rule-based decision systems. Ph.D. dissertation, Dept of Computer Sciences, Univ. of Texas at Austin.

Crossref

Google Scholar

[23]

COUVREUR, J.-M., FRANCEZ, N., AND GOUDA, M. G. 1992. Asynchronous unison. In Proceedings of the 12th Internatmnal Conference on Distrzbuted Computzng Systems (Yokohama, Japan, June).

Google Scholar

[24]

CRISTIAN, F. 1991. Understanding fault-tolerant distributed systems. Commun. ACM 34, 2 (Feb.), 56-78.

Crossref

Google Scholar

[25]

CRIST~AN, F. 1985. A rigorous approach to faulttolerant programming. IEEE Trans. Softw. Eng 11, 1, (1985).

Google Scholar

[26]

DIJKSTRA, E.W. 1986. A belated proof of self-stabilization. Dzstrzb. Comput., 1, 5-6.

Crossref

Google Scholar

[27]

DIJKSTRA, E.W. 1974. Self-stabfiizing systems in spite of distributed control Com mun. ACM 17, 643-644.

Crossref

Google Scholar

[28]

DIJKSTRA, E.W. 1973. Self-stabilization in spite of distributed control. In Selected Wrztmgs on Computing: A Personal Perspectwe. Springer- Verlag, Berlin, 1982, 41-46. Originally pubhshed in 1973.

Google Scholar

[29]

DOLEV, S., ISRAELI, A., AND MORAN, S. 1990. Self-stabilization of dynamic systems. In Proceedmg's of the 9th Annual ACM Sympostum on Principles of Dzstributed Computing (Quebec City, Canada, Aug.). ACM, New York

Crossref

Google Scholar

[30]

EVANGELIST, M. 1989. Proceedings of the MCC Workshop on Self-Stabd~zmg Systems. MCC Tech. Rep. STP-379-89.

Google Scholar

[31]

FLATEBO, M., AND DATTA, A. 1992. Two-state self-stabilizing algorithms. In Proceedings of the 6th Internatmnal Parallel Processing Symposium (Beverly Hills, Calif. Mar.), 198 203.

Crossref

Google Scholar

[32]

FLATEBO, M., DATTA, A., AND GttosI-I, S. 1991 Self-stabilization in distributed systems. IEEE Comput.

Google Scholar

[33]

GAREY, M., AND JOHNSON, D. Computers and Intractabihty: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York.

Crossref

Google Scholar

[34]

GttOSH, S. 1990a. Self-stabilizing distributed systems with binary machines. In Proceedings of the 28th Annual Allerton Conference, 988 997.

Google Scholar

[35]

GHOSH, S. 1990b Understanding self-stabilization in distributed systems. Tech. Rep. TR-90- 02, Dept. of Computer Science, Univ. of Iowa.

Google Scholar

[36]

GOUDA, M.G. 1989. The inevitable properties of programs. Dept. of Computer Sciences, Univ. of Texas at Austin.

Google Scholar

[37]

GOUDA, M.G. 1991. The stabilizing philosopher: Asymmetry by memory and by action. Tech. Rep. TR-87~12, Dept. of Computer Sciences, Univ. of Texas at Austin.

Crossref

Google Scholar

[38]

GOUDA, M. G., AND EVANGELIST, M. 1990. Convergence/response tradeoffs in concurrent systems. In Proceedings of the 2nd IEEE Symposium on Parallel and Distributed Processing (Dec.). IEEE, New York.

Google Scholar

[39]

GOUDA, M. G., AND HERMAN, T. 1991. Adaptive programming. IEEE Trans. Softw. Eng. 17, 9 (Sept.).

Crossref

Google Scholar

[40]

GOUDA, M. G., AND HERMAN, T. 1990. Stabilizing unison. Inf. Process. Lett. 35 (1990), 171 175.

Crossref

Google Scholar

[41]

GOUDA, M. G., AND MULTARI, N. 1991. Stabilizing communication protocols. IEEE Trans. Cornput. 40, 4 (Apr.), 448-458.

Crossref

Google Scholar

[42]

GOUDA, M. G., HOWELL, R. R., AND ROSmR, L. E. The instability of self-stabilization. Acta Inf. 27, (1990), 697-724.

Crossref

Google Scholar

[43]

HADDIX, F.F. 1991. Stabilization of bounded token rings. Tech. Rep. ARL-TR-91-31, Applied Research Lab., Univ. of Texas at Austin.

Google Scholar

[44]

HERMAN, T. 1990. Probabilistic self-stabilization. Inf. Process. Lett. 15, 63-67.

Crossref

Google Scholar

[45]

HOARE, C. A. R. 1978. Communicating sequential processes. Commun. ACM 21,666-677.

Crossref

Google Scholar

[46]

ISRAELL A., AND JALFON, M. 1990. Token management schemes and random walks yield self stabilizing mutual exclusion. In Proceedings of the 9th Annual ACM Sympostum on Principles of Distributed Computing (Quebec City, Canada, Aug.). ACM, New York.

Crossref

Google Scholar

[47]

ISRAELI, A., AND JALFON, M. 1989. Self-stabilizing ring orientation. Tech. Rep., Dept. of Electrical Engineering, Technion-Israel.

Google Scholar

[48]

JOHNSON, D. 1990. A catalog of complexity classes. In Handbook of Theoretical Computer Science. vol. A. North-Holland, Amsterdam.

Crossref

Google Scholar

[49]

JOHNSON, B. 1988. The Design and Analysis of Fault-Tolerant Dlgttal Systems, Addison-Wesley, New York.

Crossref

Google Scholar

[50]

KA?Z~ S., AND PERRY, K.J. 1990. Self-stabilizing extensions for message-passing systems. In Proceedings of the 9th Annual ACM Sympostum on Principles o{ Distributed Computing (Quebec City, Canada, Aug.). ACM, New York.

Crossref

Google Scholar

[51]

KRUIJER, H. S. M. 1979. Self-stabilization (in spite of distributed control) in tree-structured systems. Inf. Process. Lett., 8, 2, 2 79.

Google Scholar

[52]

LAMPORT, L. 1986. The mutual exclusion problem: Part II--Statement and solutions. J. ACM 33, 327-348.

Crossref

Google Scholar

[53]

LAMPORT, L. 1984. Solved problems, unsolved problems and non-problems in concurrency. In Proceedings of the 3rd ACM Symposium on Principles of Distributed Computing. ACM, New York, 1-11.

Crossref

Google Scholar

[54]

LAPRIE, J.-C. 1985. Dependable computing and fault tolerance: Concepts and terminology. In Proceedtngs of FTCS-15, 2-11.

Google Scholar

[55]

LEHMAN, D., AND RABIN, M. 1981. On the advantages of free choice: A symmetric and fully distributed solution of the dining philosophers problem. In Proceedings of the 8th Annual ACM Symposium on Principles of Programmtng Languages. ACM, New York, 133-138.

Crossref

Google Scholar

[56]

LFN, X., AND GHOSH, S. 1991. Self-stabilizing maxima finding. In Proceedings of the 28th Ann ual Allerton Conference.

Google Scholar

[57]

MULTAR1, N. 1989. Towards a theory for selfstabilizing protocols. Ph.D. dissertation, Dept. of Computer Sciences, Univ. of Texas at Austin.

Crossref

Google Scholar

[58]

ZVEREN, C., WiLLSKY, A., AND ANTSAKLIS, P. 1989. Stability and stabilizability of discrete event dynamic systems. MIT LIDS Pub., LIDS-P- 1853, MIT, Cambridge, Mass.

Google Scholar

[59]

SCHNEIDER, M. 1992. Compiling self-stabihzation into sequential programs. Dept. of Computer Sciences, Umv. of Texas, Austin, Tex.

Google Scholar

[60]

SCHNEIDER, M. 1991. SelLstabilization--A unified approach to fault tolerance in the face of transient errors. In Tech. Rep. TR-91-18, Dept. of Computer Sciences, Univ. of Texas at Austin.

Google Scholar

[61]

TCHUENTE, M. 1981. Sur 1 auto-stabilisation dans un ~eseau ttordinateurs. RAIRO Inf. Theor. 15, 47 66. In French.

Google Scholar

[62]

WHITBY-STREVENS, C. 1979. On the performance of Dijkstra's self-stabilising algorithms in spite of distributed control. In Proceedings of the 1st Internattonal Conference on Distributed Computing Systems. IEEE, New York.

Google Scholar

Cited By

View all

Feng SChen MSu HKaminski BKatoen JZhan N(2023)Lower Bounds for Possibly Divergent Probabilistic ProgramsProceedings of the ACM on Programming Languages10.1145/35860517:OOPSLA1(696-726)Online publication date: 6-Apr-2023
https://dl.acm.org/doi/10.1145/3586051
Karaata MDabees A(2023)Fault-Tolerant Broadcast Algorithm for Tree Networks2023 15th International Conference on Computer and Automation Engineering (ICCAE)10.1109/ICCAE56788.2023.10111474(76-80)Online publication date: 3-Mar-2023
https://doi.org/10.1109/ICCAE56788.2023.10111474
Karaata MDabees A(2022)Safety and Observibility of Distributed Broadcast Algorithms2022 6th European Conference on Electrical Engineering & Computer Science (ELECS)10.1109/ELECS55825.2022.00010(17-20)Online publication date: Dec-2022
https://doi.org/10.1109/ELECS55825.2022.00010
Show More Cited By

Recommendations

A self-stabilizing link-coloring protocol resilient to unbounded byzantine faults in arbitrary networks
OPODIS'05: Proceedings of the 9th international conference on Principles of Distributed Systems

Self-stabilizing protocols can tolerate any type and any number of transient faults. However, in general, self-stabilizing protocols provide no guarantee about their behavior against permanent faults. This paper proposes a self-stabilizing link-coloring ...
Timer-based composition of fault-containing self-stabilizing protocols

One of the desired properties of distributed systems is self-adaptability against faults. Self-stabilizing protocols provide autonomous recovery from any finite number of transient faults. However, in practice, catastrophic faults rarely occur, while ...
Error-detecting codes and fault-containing self-stabilization

Reviews

Reviewer: David James Taylor

Self-stabilization is the property that guarantees that a system placed in an arbitrary state will return to a legitimate state within a finite number of state transitions. This paper provides an extensive survey of research into self-stabilization and such related notions as probabilistic self-stabilization and pseudo-stabilization. Although it provides a good general background and historical summary, the paper is likely to prove frustrating for a reader unfamiliar with the field. The authors frequently introduce a topic too briefly for it to be really appreciated and then refer the reader to the original work for details. In addition, the paper does not provide any proofs for self-stabilization. With no examples, the reader may be left without a grasp of the type of argument required. For the original Dijkstra unidirectional ring, it would not have been difficult to sketch a proof rather than leave the reader with the statement, “Furthermore it can be shown quite easily that if started in an arbitrary state, the system will stabilize.” The paper claims, as does much of the cited literature, that self-stabilization is a useful technique for fault tolerance. A critical reading of the paper suggests that the field has instead provided a number of impossibility results. In some instances, self-stabilization can only be achieved if a system has an infinite number of states; elsewhere it is indicated that termination and self-stabilization are frequently mutually exclusive. (The attempt to equate distributed systems with nonterminating systems and, thus, claim that termination is not a significant issue is unrealistic.) The quote from L. Lamport near the beginning of the paper, “I regard it [E. W. Dijkstra's original work on self-stabilization] to be a milestone in work on fault tolerance,” needs to be balanced by a reasonable assessment of the limited practical application that self-stabilization has had and is likely to have.

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ACM Computing Surveys Volume 25, Issue 1

March 1993

62 pages

ISSN:0360-0300

EISSN:1557-7341

DOI:10.1145/151254

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 March 1993

Published in CSUR Volume 25, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

280
Total Citations
View Citations
2,909
Total Downloads

Downloads (Last 12 months)180
Downloads (Last 6 weeks)34

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Feng SChen MSu HKaminski BKatoen JZhan N(2023)Lower Bounds for Possibly Divergent Probabilistic ProgramsProceedings of the ACM on Programming Languages10.1145/35860517:OOPSLA1(696-726)Online publication date: 6-Apr-2023
https://dl.acm.org/doi/10.1145/3586051
Karaata MDabees A(2023)Fault-Tolerant Broadcast Algorithm for Tree Networks2023 15th International Conference on Computer and Automation Engineering (ICCAE)10.1109/ICCAE56788.2023.10111474(76-80)Online publication date: 3-Mar-2023
https://doi.org/10.1109/ICCAE56788.2023.10111474
Karaata MDabees A(2022)Safety and Observibility of Distributed Broadcast Algorithms2022 6th European Conference on Electrical Engineering & Computer Science (ELECS)10.1109/ELECS55825.2022.00010(17-20)Online publication date: Dec-2022
https://doi.org/10.1109/ELECS55825.2022.00010
Hafaiedh ISlimane M(2022)A distributed formal-based model for self-healing behaviors in autonomous systems: from failure detection to self-recoveryThe Journal of Supercomputing10.1007/s11227-022-04614-078:17(18725-18753)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1007/s11227-022-04614-0
Chen MKatoen JKlinkenberg LWinkler T(2022)Does a Program Yield the Right Distribution?Computer Aided Verification10.1007/978-3-031-13185-1_5(79-101)Online publication date: 7-Aug-2022
https://dl.acm.org/doi/10.1007/978-3-031-13185-1_5
Lourenço CPinto J(2022)Why3-do: The Way of Harmonious Distributed System ProofsProgramming Languages and Systems10.1007/978-3-030-99336-8_5(114-142)Online publication date: 29-Mar-2022
https://doi.org/10.1007/978-3-030-99336-8_5
Salama MBahsoon RLago P(2021)Stability in Software Engineering: Survey of the State-of-the-Art and Research DirectionsIEEE Transactions on Software Engineering10.1109/TSE.2019.292561647:7(1468-1510)Online publication date: 1-Jul-2021
https://doi.org/10.1109/TSE.2019.2925616
Hoffmann RDésérable DSeredyński F(2021)A cellular automata rule placing a maximal number of dominoes in the square and diamondThe Journal of Supercomputing10.1007/s11227-020-03549-877:8(9069-9087)Online publication date: 1-Aug-2021
https://dl.acm.org/doi/10.1007/s11227-020-03549-8
Xing JWu WChen A(2019)Architecting Programmable Data Plane Defenses into the Network with FastFlexProceedings of the 18th ACM Workshop on Hot Topics in Networks10.1145/3365609.3365860(161-169)Online publication date: 13-Nov-2019
https://dl.acm.org/doi/10.1145/3365609.3365860
Hunter SApplegate EArora VChong BCooper KRincón-Guevara OVivas-Valencia C(2019)An Introduction to Multiobjective Simulation OptimizationACM Transactions on Modeling and Computer Simulation10.1145/329987229:1(1-36)Online publication date: 24-Jan-2019
https://dl.acm.org/doi/10.1145/3299872
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

A self-stabilizing link-coloring protocol resilient to unbounded byzantine faults in arbitrary networks

Timer-based composition of fault-containing self-stabilizing protocols

Error-detecting codes and fault-containing self-stabilization

Reviews

Access critical reviews of Computing literature here