research-article

Distributed Reset

Authors:

M. GoudaAuthors Info & Claims

IEEE Transactions on Computers, Volume 43, Issue 9

Pages 1026 - 1038

https://doi.org/10.1109/12.312126

Published: 01 September 1994 Publication History

Abstract

A reset subsystem is designed that can be embedded in an arbitrary distributed system in order to allow the system processes to reset the system when necessary. Our design is layered, and comprises three main components: a leader election, a spanning tree construction, and a diffusing computation. Each of these components is self-stabilizing in the following sense: if the coordination between the up-processes in the system is ever lost (due to failures or repairs of processes and channels), then each component eventually reaches a state where coordination is regained. This capability makes our reset subsystem very robust: it can tolerate fail-stop failures and repairs of processes and channels, even when a reset is in progress.

References

[1]

{1} Y. Afek, B. Awerbuch, and E. Gafni, "Applying static network protocols to dynamic networks," in Proc. 28th IEEE Symp. Foundations of Comput. Sci., 1987.

[2]

{2} A. Arora, "A foundation of fault-tolerant computing," Ph.D. Dissertation, Univ. of Texas at Austin, Dec. 1992.

[3]

{3} A. Arora, P. Attie, M. Evangelist and M.G. Gouda, "Convergence of iteration systems," Distributed Computing, vol. 7, pp. 48-53, 1993.

Digital Library

[4]

{4} A. Arora and M. G. Gouda, "Distributed reset (extended abstract)," in Proc. 10th Conf. on Foundations of Software Technol. and Theoretical Comput. Sci., LNCS 472, 1990, pp. 316-331, (Springer-Verlag).

[5]

{5} J. E. Burns, M. G. Gouda, and R. E. Miller, "On relaxing interleaving assumptions," Tech. Rep. GIT-ICS-88/29, School of ICS, Georgia Inst. of Technol., 1988.

[6]

{6} G. M. Brown, M. G. Gouda, and C.-L. Wu, "Token systems that self-stabilize," IEEE Trans. Comput., vol. 38, no. 6, pp. 845-852, June 1989.

Digital Library

[7]

{7} J. E. Burns and J. Pachl, "Uniform self-stabilizing rings," ACM Trans. Programming Lang. Syst., vol. 11, no. 2, pp. 330-344, 1989.

Digital Library

[8]

{8} K. M. Chandy and L. Lamport, "Distributed snapshots: Determining global states of distributed systems," ACM Trans. Comput. Syst., vol. 3, no. 1, pp. 63-75, 1985.

Digital Library

[9]

{9} S. Dolev, A. Israeli, and S. Moran, "Self-stabilization of dynamic systems assuming only read/write atomicity," in Proc. Ninth ACM Symp. Principles of Distrib. Computing, 1990, pp. 103-117.

[10]

{10} E. W. Dijkstra and C. S. Scholten, "Termination detection for diffusing computations," Inform. Processing Lett., vol. 11, no. 1, pp. 1-4, 1980.

[11]

{11} M. Fischer, N. Lynch, and M. Paterson, "Impossibility of distributed consensus with one faulty process," J. ACM, vol. 32, no. 2, pp. 374-382, 1985.

Digital Library

[12]

{12} N. Frances, Fairness. New York: Springer-Verlag, 1986.

[13]

{13} M. G. Gouda and N. Multari, "Stabilizing communication protocols," IEEE Trans. Comput., vol. 40, no. 4, pp. 448-458, Apr. 1991.

Digital Library

[14]

{14} S. Katz and K. Perry, "Self-stabilizing extensions for message-passing systems," in Proc. Ninth ACM Symp. Principles of Distrib. Computing, 1990, pp. 91-101.

Digital Library

[15]

{15} L. Lamport and L. Lynch, "Distributed computing: Models and methods," Handbook of Theoretical Computer Science. New York: Elsevier Science, ch. 18, vol. 2, 1990, pp. 1158-1199.

[16]

{16} R. Perlman, "An algorithm for distributed computation of a spanning tree in an extended LAN," in Ninth ACM Data Commun. Symp., vol. 20, no. 7, 1985, pp. 44-52.

[17]

{17} W. Tajibnapis, "A correctness proof of a topology information maintenance protocol for a distributed computer network," Commun. ACM, vol. 20, no. 7, pp. 477-485, 1977.

Digital Library

Cited By

Altisen KCournier ADefalque GDevismes SKuznetsov PGelles ROlivetti D(2024)On Self-stabilizing Leader Election in Directed NetworksProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662778(527-537)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662778
Nguyen DGupta AKulkarni S(2023)Analyzing Program Transitions to Compute Benefit of Tolerating Consistency Violation FaultsProceedings of the 24th International Conference on Distributed Computing and Networking10.1145/3571306.3571391(58-69)Online publication date: 4-Jan-2023
https://dl.acm.org/doi/10.1145/3571306.3571391
Herman T(2022)Origin of Self-StabilizationEdsger Wybe Dijkstra10.1145/3544585.3544592(81-104)Online publication date: 12-Jul-2022
https://dl.acm.org/doi/10.1145/3544585.3544592
Show More Cited By

Distributed Reset
1. Software and its engineering
  1. Software organization and properties
    1. Software system structures

Recommendations

A low-overhead recovery technique using quasi-synchronous checkpointing
ICDCS '96: Proceedings of the 16th International Conference on Distributed Computing Systems (ICDCS '96)

In this paper, we propose a quasi-synchronous checkpointing algorithm and a low-overhead recovery algorithm based on it. The checkpointing algorithm preserves process autonomy by allowing them to take checkpoints asynchronously and uses communication-...
Designing masking fault-tolerance via nonmasking fault-tolerance
SRDS '95: Proceedings of the 14TH Symposium on Reliable Distributed Systems

Masking fault-tolerance guarantees that programs continually satisfy their specification in the presence of faults. By way of contrast, nonmasking fault-tolerance does not guarantee as much: it merely guarantees that when faults stop occurring, program ...
How to recover efficiently and asynchronously when optimism fails
ICDCS '96: Proceedings of the 16th International Conference on Distributed Computing Systems (ICDCS '96)

We propose a new algorithm for recovering asynchronously from failures in a distributed computation. Our algorithm is based on two novel concepts-a fault-tolerant vector clock to maintain causality information in spite of failures, and a history ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Computers

IEEE Transactions on Computers Volume 43, Issue 9

September 1994

128 pages

ISSN:0018-9340

Issue’s Table of Contents

Copyright © Copyright © 1994 IEEE. All Rights Reserved.

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 September 1994

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

99
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Altisen KCournier ADefalque GDevismes SKuznetsov PGelles ROlivetti D(2024)On Self-stabilizing Leader Election in Directed NetworksProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662778(527-537)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662778
Nguyen DGupta AKulkarni S(2023)Analyzing Program Transitions to Compute Benefit of Tolerating Consistency Violation FaultsProceedings of the 24th International Conference on Distributed Computing and Networking10.1145/3571306.3571391(58-69)Online publication date: 4-Jan-2023
https://dl.acm.org/doi/10.1145/3571306.3571391
Herman T(2022)Origin of Self-StabilizationEdsger Wybe Dijkstra10.1145/3544585.3544592(81-104)Online publication date: 12-Jul-2022
https://dl.acm.org/doi/10.1145/3544585.3544592
Kulkarni SAppleton GNguyen D(2022)Achieving Causality with Physical ClocksProceedings of the 23rd International Conference on Distributed Computing and Networking10.1145/3491003.3491009(97-106)Online publication date: 4-Jan-2022
https://dl.acm.org/doi/10.1145/3491003.3491009
Karaata MAlrashed EAllaho M(2022)Self-stabilizing c-wave algorithms for arbitrary networksComputing10.1007/s00607-022-01110-4105:1(53-88)Online publication date: 16-Aug-2022
https://dl.acm.org/doi/10.1007/s00607-022-01110-4
Nguyen DKulkarni SDatta AHansdah RKrishnaswamy DVaidya N(2019)Benefit of self-stabilizing protocols in eventually consistent key-value storesProceedings of the 20th International Conference on Distributed Computing and Networking10.1145/3288599.3288609(148-157)Online publication date: 4-Jan-2019
https://dl.acm.org/doi/10.1145/3288599.3288609
Blin LTixeuil S(2018)Compact deterministic self-stabilizing leader election on a ringDistributed Computing10.1007/s00446-017-0294-231:2(139-166)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.1007/s00446-017-0294-2
Datta ALarmore L(2018)Self-Stabilizing Leader Election in Dynamic NetworksTheory of Computing Systems10.1007/s00224-017-9758-962:5(977-1047)Online publication date: 1-Jul-2018
https://dl.acm.org/doi/10.1007/s00224-017-9758-9
Hajisheykhi RRoohitavaf MKulkarni S(2017)Bounded Auditable Restoration of Distributed SystemsIEEE Transactions on Computers10.1109/TC.2016.259557866:2(240-255)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1109/TC.2016.2595578
Datta ADevismes SLarmore L(2017)Self-stabilizing silent disjunction in an anonymous networkTheoretical Computer Science10.1016/j.tcs.2016.12.012665:C(51-72)Online publication date: 22-Feb-2017
https://dl.acm.org/doi/10.1016/j.tcs.2016.12.012
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents