LOG-Space Polynomial End-to-End Communication

TitleLOG-Space Polynomial End-to-End Communication
Publication TypeTechnical Report
Year of Publication1994
AuthorsKushilevitz E, Ostrovsky R, Rosén A
Other Numbers938

Communication between processors is the essence of distributed computing: clearly, without communication distributed computation is impossible. However, as networks become larger and larger, the frequency of link failures increases. The End-to-End Communication is a classical problem that asks how to carry out fault-free communication between two processors over a network, in spite of such frequent communication faults. The sole minimum assumption is that the two processors that are trying to communicate are not permanently disconnected (i.e., the communication should proceed even in the case that there does not (ever) simultaneously exist, at any time, any operational path between the two processors that are trying to communicate.) For the first time, we present a protocol which solves this fundamental problem with logarithmic-space and polynomial-communication at the same time. This is an exponential memory improvement to all previous polynomial-communication solutions. That is, all previous polynomial-communication solutions needed at least linear (in n, the size of the network) amount of memory per edge. Our algorithm maintains a simple-to-compute O(log n)-bits potential function at each edge in order to perform routing, and uses a novel technique of packet canceling which allows us to keep only one packet per edge. We stress that both the computation of our potential function and our packet-canceling policy are totally local in nature; we believe that they are applicable to other settings as well.

Bibliographic Notes

ICSI Technical Report TR-94-068

Abbreviated Authors

E. Kushilevitz, R. Ostrovsky, and A. Rosen

ICSI Publication Type

Technical Report