Complexity of network synchronization
- 1 October 1985
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 32 (4), 804-823
- https://doi.org/10.1145/4221.4227
Abstract
The problem of simulating a synchronous network by an asynchronous network is investigated. A new simulation technique, referred to as a synchronizer, which is a new, simple methodology for designing efficient distributed algorithms in asynchronous networks, is proposed. The synchronizer exhibits a trade-off between its communication and time complexities, which is proved to be within a constant factor of the lower bound.Keywords
This publication has 7 references indexed in Scilit:
- Efficiency of Synchronous Versus Asynchronous Distributed SystemsJournal of the ACM, 1983
- Distributed network protocolsIEEE Transactions on Information Theory, 1983
- A Distributed Algorithm for Minimum-Weight Spanning TreesACM Transactions on Programming Languages and Systems, 1983
- Decentralized maximum-flow protocolsNetworks, 1982
- An O(n2log n) parallel max-flow algorithmJournal of Algorithms, 1982
- Synchronization in Distributed ProgramsACM Transactions on Programming Languages and Systems, 1982
- Time, clocks, and the ordering of events in a distributed systemCommunications of the ACM, 1978