Applying static network protocols to dynamic networks
- 1 October 1987
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 358-370
- https://doi.org/10.1109/sfcs.1987.7
Abstract
This paper addresses the problem of how to adapt an algorithm designed for fixed topology networks to produce the intended results, when run in a network whose topology changes dynamically, in spite of encountering topological changes during its execution. We present a simple and unified procedure, called a reset procedure, which, when combined with the static algorithm, achieves this adaptation. The communication and time complexities of the reset procedure, per topological change, are independent of the number of topological changes and are linearly bounded by the size of the subset of the network which participates in the algorithm.Keywords
This publication has 14 references indexed in Scilit:
- Reliable link initialization proceduresIEEE Transactions on Communications, 1988
- Generalized scheme for topology-update in dynamic networksPublished by Springer Nature ,1988
- Complexity of network synchronizationJournal of the ACM, 1985
- Impossibility of distributed consensus with one faulty processJournal of the ACM, 1985
- Distributed snapshotsACM Transactions on Computer Systems, 1985
- Distributed network protocolsIEEE Transactions on Information Theory, 1983
- Distributed Minimum Hop AlgorithmsPublished by Defense Technical Information Center (DTIC) ,1982
- Termination detection for diffusing computationsInformation Processing Letters, 1980
- Resynch Procedures and a Fail-Safe Network ProtocolIEEE Transactions on Communications, 1979
- Time, clocks, and the ordering of events in a distributed systemCommunications of the ACM, 1978