LOG-Space Polynomial End-to-End Communication
Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosen
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.
comment: In SIAM Journal of Computing Volume 27, 1998. SIAM J. Comput. 27(6): 1531-1549 (1998). Preliminary version appeared in the Proceedings of Twenty-seventh ACM Symposium on Theory of Computing (STOC-95)
Fetch PostScript file of the paper Fetch PDF file of the paper
| Back to Publications List |