Abstract
Certain types of system faults, notably data errors due to transient faults, can be repaired by software. The repair consists of identifying faulty variables and then rewriting data to correct the fault. If fault identification is imprecise, repair procedures can contaminate non faulty processes from data originating at faulty processes. This contamination danger is resolved by delaying data correction for a sufficiently long period. In order to delay correction, processes use a repair timer. This paper considers the problem of how asynchronous processes can implement a repair timer that is itself subject to faults. The main results are requirement specifications for a distributed repair timer and a repair timer algorithm. The algorithm self-stabilizes in O(D) rounds, where D is the diameter of the network, and provides reliable timing from k-faulty configurations within O(k) rounds.
This work is supported by NSF CAREER award CCR-9733541.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
A Arora, S Dolev, and MG Gouda. Maintaining digital clocks in step. Parallel Processing Letters, 1:11–18, 1991.
B Awerbuch. Complexity of network synchronization. Journal of the ACM, 32:804–823, 1985.
JM Couvreur, N Francez, and MG Gouda. Asynchronous unison. In ICDCS92 Proceedings of the 12th International Conference on Distributed Computing Systems, pages 486–493, 1992.
S Dolev. Optimal time self-stabilization in dynamic systems. In WDAG93 Distributed Algorithms 7th International Workshop Proceedings, Springer-Verlag LNCS:725, pages 160–173, 1993.
S Even and S Rajsbaum. Unison, canon and sluggish clocks in networks controlled by a synchronizer. Mathematical Systems Theory, 28:421–435, 1995.
S Ghosh, A Gupta, T Herman, and SV Pemmaraju. Fault-containing self-stabilizing algorithms. In PODC96 Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing, pages 45–54, 1996.
S Ghosh, A Gupta, and SV Pemmaraju. A fault-containing self-stabilizing algorithm for spanning trees. Journal of Computing and Information, 2:322–338, 1996.
MG Gouda and T Herman. Stabilizing unison. Information Processing Letters, 35:171–175, 1990.
T Herman. Superstabilizing mutual exclusion. In Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA'95), pages 31–40, 1995.
T Herman. Distributed repair timers. Technical Report TR 98-05, University of Iowa Department of Computer Science, 1998.
T Herman and S Ghosh. Stabilizing phase-clocks. Information Processing Letters, 54:259–265, 1995.
S Kutten and B Patt-Shamir. Time-adaptive self stabilization. In PODC97 Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing, pages 149–158, 1997.
C Lin and J Simon. Possibility and impossibility results for self-stabilizing phase clocks on synchronous rings. In Proceedings of the Second Workshop on Self-Stabilizing Systems, pages 10.1–10.15, 1995.
J Misra. Phase synchronization. Information Processing Letters, 38:101–105, 1991.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Herman, T. (1998). A stabilizing repair timer. In: Kutten, S. (eds) Distributed Computing. DISC 1998. Lecture Notes in Computer Science, vol 1499. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0056483
Download citation
DOI: https://doi.org/10.1007/BFb0056483
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-65066-9
Online ISBN: 978-3-540-49693-9
eBook Packages: Springer Book Archive