On the effects of feedback in dynamic network protocols
- 1 January 1988
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 231-245
- https://doi.org/10.1109/sfcs.1988.21940
Abstract
A framework is introduced that provides a unified way for proving correctness as well as analyzing performance of a class of communication protocols called (asynchronous) reset protocols. They are logarithmic transformers, converting protocols working in a static asynchronous network into protocols working in a dynamic asynchronous network. The design of reset protocols is a classical problem in communication networking, renowned for its complexity. A paradigm is developed that gives fresh insight into this complicated problem. This additional insight leads to the development of reset protocols with complexities bounded by the communication complexity of the original protocol.Keywords
This publication has 11 references indexed in Scilit:
- Optimal algorithms for Byzantine agreementPublished by Association for Computing Machinery (ACM) ,1988
- Dynamic networks are as fast as static networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- Applying static network protocols to dynamic networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1987
- Local management of a global resource in a communication networkPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1987
- Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problemsPublished by Association for Computing Machinery (ACM) ,1987
- Detecting global termination conditions in the face of uncertaintyPublished by Association for Computing Machinery (ACM) ,1987
- A Distributed Algorithm for Minimum-Weight Spanning TreesACM Transactions on Programming Languages and Systems, 1983
- Termination detection for diffusing computationsInformation Processing Letters, 1980
- The New Routing Algorithm for the ARPANETIEEE Transactions on Communications, 1980
- Resynch Procedures and a Fail-Safe Network ProtocolIEEE Transactions on Communications, 1979