Communication between processors is the essence of distributed computi
ng: clearly, without communication, distributed computation is impossi
ble. However, as networks become larger and larger, the frequency of l
ink failures increases. The end-to-end communication problem asks how
to efficiently carry out fault-free communication between two processo
rs over a network, in spite of such frequent link failures. The sole m
inimum assumption is that the two processors that are trying to commun
icate are not permanently disconnected (i.e., the communication should
proceed even when there does not (ever) simultaneously exist an opera
tional path between the two processors that are trying to communicate)
. We present a protocol to solve the end-to-end problem with logarithm
ic-space and polynomial communication at the same time. This is an exp
onential memory improvement to all previous polynomial communication s
olutions. That is, all previous polynomial communication solutions nee
ded at least linear (in n, the size of the network) amount of memory p
er link. Our protocol transfers packets over the network, maintains a
simple-to-compute O(log n)-bits potential function at each link in ord
er to perform routing, and uses a novel technique of packet canceling
which allows us to keep only one packet per link. The computations of
both our potential function and our packet-canceling policy are totall
y local in nature.