LOG-SPACE POLYNOMIAL END-TO-END COMMUNICATION

Citation
E. Kushilevitz et al., LOG-SPACE POLYNOMIAL END-TO-END COMMUNICATION, SIAM journal on computing, 27(6), 1998, pp. 1531-1549
Citations number
29
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Computer Science Theory & Methods",Mathematics,"Computer Science Theory & Methods",Mathematics
Journal title
ISSN journal
0097-5397
Volume
27
Issue
6
Year of publication
1998
Pages
1531 - 1549
Database
ISI
SICI code
0097-5397(1998)27:6<1531:LPEC>2.0.ZU;2-T
Abstract
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.