SLIDE - THE KEY TO POLYNOMIAL END-TO-END COMMUNICATION

We consider the basic task of of end-to-end communication in dynamic n etworks, that is, delivery in finite time of data items generated on-l ine by a sender, to a receiver, in order and without duplication or om ission. A dynamic communication network is one in which links may repe atedly fail and recover. In such a network, though it is impossible to establish a communication path consisting of nonfailed links, reliabl e communication is possible, if there is no cut of permanently failed links between a sender and receiver. This paper presents the first pol ynomial complexity end-to-end communication protocol in dynamic networ ks. In the worst case the protocol sends O(n(2)m) messages per data it em 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 deliverin g tokens across an unreliable network. Slide is the basis for several self-stabilizing protocols and load-balancing algorithms for dynamic n etworks that have subsequently appeared in the literature. We use our end-to-end protocol to derive a file-transfer protocol for sufficientl y 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 protoc ol. (C) 1997 Academic Press.