End-to-end communication in unreliable networks
Eli M. Gafni, Yehuda Afek · 1988
This paper addresses the problem of end-toend communication over a dynamically changing network in which the sender and the receiver are not forever separated.We present several end-to-end communication protocols whose space complexity at each node is independent of either the input length or the network size.Although the time complexity of these protocols is bounded, their communication complexity is either unbounded, or exponential if an acyclic orientation of the network is given.To bound the communication complexity of the protocols, in the absence of an acyclic orientation, we assume either knowledge of the total number of nodes in the network, or that nodes have unique ids.These bounded communication-complexity protocols thus require O(logn) space per incident link at each node.In sum, we dispel the myth 'Supported by NSF Presidential Young