✍ Scribed by Yehuda Afek; Baruch Awerbuch MIT; ; Eli Gafni; Yishay Mansour; Adi Rosén; Nir Shavit
No coin nor oath required. For personal study only.
We consider the basic task of of end-to-end communication in dynamic networks, that is, delivery in finite time of data items generated on-line by a sender, to a receiver, in order and without duplication or omission.
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 communication path consisting of nonfailed links, reliable communication is possible, if there is no cut of permanently failed links between a sender and receiver.
This paper presents the first polynomial complexity end-to-end communication Ž 2 . protocol in dynamic networks. In the worst case the protocol sends O n m messages per data item delivered, where n and m are the number of processors and number of links in the network respectively. The centerpiece of our solution is the novel slide protocol, a simple and efficient method for delivering tokens across an unreliable network. Slide is the basis for several self-stabilizing protocols and load-balancing algorithms for dynamic networks that have subsequently appeared in the literature.
We use our end-to-end protocol to derive a file-transfer protocol for sufficiently Ž . large files. The bit communication complexity of this protocol is O nD bits, where Ž . D is the size in bits of the file. This file-transfer protocol yields an O n amortized message complexity end-to-end protocol.
📜 SIMILAR VOLUMES
**Discover the charming first enovella in a new Amish romance series from the _New York Times_ bestselling author of _Love Held Captive_ and *The Gift. * ** When Andy’s baby sister Trish gets stranded at the family cabin during a massive blizzard, he calls upon his best friends—the Magnificent Eigh