Distributed program checking: a paradigm for building self-stabilizing distributed protocols
- 9 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 258-267
- https://doi.org/10.1109/sfcs.1991.185377
Abstract
The notion of distributed program checking as a means of making a distributed algorithm self-stabilizing is explored. A compiler that converts a deterministic synchronous protocol pi for static networks into a self-stabilizing version of pi for dynamic networks is described. If T/sub pi / is the time complexity of pi and D is a bound on the diameter of the final network, the compiled version of pi stabilizes in time O(D+T/sub pi /) and has the same space complexity as pi . The general method achieves efficient results for many specific noninteractive tasks. For instance, solutions for the shortest paths and spanning tree problems take O(D) to stabilize, an improvement over the previous best time of O(D/sup 2/).<>Keywords
This publication has 19 references indexed in Scilit:
- Memory-efficient self stabilizing protocols for general networksPublished by Springer Nature ,1991
- Uniform self-stabilizing ringsACM Transactions on Programming Languages and Systems, 1989
- Simple and efficient election algorithms for anonymous networksPublished by Springer Nature ,1989
- A new approach to the maximum-flow problemJournal of the ACM, 1988
- Complexity of network synchronizationJournal of the ACM, 1985
- Fault-tolerant broadcast of routing informationComputer Networks (1976), 1983
- Distributed network protocolsIEEE Transactions on Information Theory, 1983
- Vulnerabilities of network control protocolsACM SIGCOMM Computer Communication Review, 1981
- The New Routing Algorithm for the ARPANETIEEE Transactions on Communications, 1980
- Self-stabilizing systems in spite of distributed controlCommunications of the ACM, 1974