Dynamic networks are as fast as static networks
- 1 January 1988
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 206-219
- https://doi.org/10.1109/sfcs.1988.21938
Abstract
An efficient simulation is given to show that dynamic networks are as fast as static ones up to a constant multiplicative factor. That is, any task can be performed in a dynamic asynchronous network essentially as fast as in a static synchronous network. The simulation protocol is based on an approach in which locality is perceived as the key to fast adaptation to changes in network topology. The heart of the simulation is a technique called a dynamic synchronizer, which achieves 'local' simulation of a global 'clock' in a dynamic asynchronous network. Using this result, improved solutions to a number of well-known problems on dynamic networks are obtained. It can also be used to improve the solution to certain static network problems.Keywords
This publication has 15 references indexed in Scilit:
- On the effects of feedback in dynamic network protocolsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- A new distributed algorithm to find breadth first search treesIEEE Transactions on Information Theory, 1987
- Checkpointing and Rollback-Recovery for Distributed SystemsIEEE Transactions on Software Engineering, 1987
- Complexity of network synchronizationJournal of the ACM, 1985
- Distributed BFS algorithmsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985
- Distributed network protocolsIEEE Transactions on Information Theory, 1983
- A Distributed Algorithm for Minimum-Weight Spanning TreesACM Transactions on Programming Languages and Systems, 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