Slide—The Key to Polynomial End-to-End Communication
Yehuda Afek, Baruch Awerbuch, Eli M. Gafni, Yishay Mansour, Adi Rosén, Nir Shavit · Journal of Algorithms · 1997
We consider the basic task of ofend-to-end communicationin 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 protocol in dynamic networks. In the worst case the protocol sendsO(n2m) messages per data item delivered, wherenandmare the number of processors and number of links in the network respectively. The centerpiece of our solution is the novelslideprotocol, a simple and efficient method for delivering tokens across an unreliable network.Slideis 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 isO(nD) bits, whereDis the size in bits of the file. This file-transfer protocol yields anO(n)amortizedmessage complexity end-to-end protocol.