The complexity of end-to-end communication in memoryless networks
Micah Adler, Faith Ellen Fich · 1999
End-to-end communication is the problem of sending a sequence of messages from a sender to a receiver when the network through which they communicate is unreliable. The model considered is an asynchronous network in which intermediate nodes are assumed to have no memory. Dynamic link failures are allowed: links can lose messages, but cannot reorder or duplicate them. Two problems are studied: sending a single message through a network and sending a stream of messages through a network. We provide lower bounds and upper bounds on the size of the headers needed to transmit information from the sender S to the receiver R. We prove that, for the complete network of n processors or any network that contains it as a minor (such as the n 2 input butterfly), headers of length\\Omega\\Gammangt n) are necessary to ensure delivery of one message, without ever generating an infinite amount of packet traffic. This lower bound holds even if only static link faults are allowed. It also matches the...