Polynomial End-to-End Communication
Abstract
A dynamic communication network is one in which links may repeatedly fail and recover. In such a network, though it is impossible to establish a path of unfailed links, reliable communication is possible, if there is no cut of permanently failed links between a sender and receiver. We consider the basic task of end-to end communication, that is, delivery in finite time, of data items generated on-line at the sender, to the receiver, in order and without duplication, or omission. The best known previous solutions to this problem has exponential complexity. Moreover, it has been conjectured in (AG88) that a polynomial solution is impossible. This paper disapproves this conjecture, presenting the first polynomial end-to-end protocol. The protocol uses techniques adopted from shared memory algorithms, and introduces novel techniques for fast load balancing in communication networks. Keywords: Communication networks, Unbounded counters; Fault-tolerance.
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1989
- Accession Number
- ADA213776
Entities
People
- Baruch Awerbuch
- Nir Shavit
- Yishay Mansour
Organizations
- Massachusetts Institute of Technology