About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Paper
Slide - The Key to Polynomial End-to-End Communication
Abstract
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 protocol in dynamic networks. In the worst case the protocol sends O(n2m) 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. © 1997 Academic Press.