LOG-Space Polynomial End-to-End Communication
Title | LOG-Space Polynomial End-to-End Communication |
Publication Type | Technical Report |
Year of Publication | 1994 |
Authors | Kushilevitz, E., Ostrovsky R., & Rosén A. |
Other Numbers | 938 |
Abstract | 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. |
URL | http://www.icsi.berkeley.edu/ftp/global/pub/techreports/1994/tr-94-068.pdf |
Bibliographic Notes | ICSI Technical Report TR-94-068 |
Abbreviated Authors | E. Kushilevitz, R. Ostrovsky, and A. Rosen |
ICSI Publication Type | Technical Report |