{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:38:17Z","timestamp":1787337497575,"version":"build-2736575974"},"reference-count":30,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>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 problem asks how to efficiently carry out fault-free communication between two processors over a network, in spite of such frequent link failures. 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 when there does not (ever) simultaneously exist an operational path between the two processors that are trying to communicate).<\/jats:p>\n                  <jats:p>We present a protocol to solve the end-to-end 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 link.<\/jats:p>\n                  <jats:p>Our protocol transfers packets over the network, maintains a simple-to-compute O(log n)-bits potential function at each link in order 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 totally local in nature.<\/jats:p>","DOI":"10.1137\/s0097539795296760","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1531-1549","source":"Crossref","is-referenced-by-count":7,"title":["Log-Space Polynomial End-to-End Communication"],"prefix":"10.1137","volume":"27","author":[{"given":"Eyal","family":"Kushilevitz","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rafail","family":"Ostrovsky","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Adi","family":"Ros\u00e9n","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1145\/174147.169676"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0819"},{"key":"R3","unstructured":"Y. Afek, B. Awerbuch, and E. Gafni,\n                      Applying static network protocols to dynamic networks\n                      , in Proc. 28th IEEE Ann. Symp. on Foundations of Computer Science, 1987, pp. 358\u2013370."},{"key":"R4","unstructured":"Y. Afek, B. Awerbuch, and H. Moriel,\n                      A Complexity Preserving Reset Procedure\n                      , Technical Report MIT\/LCS\/TM\u2010389, MIT, Cambridge, MA, May 1989."},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230160405"},{"key":"R6","unstructured":"Y. Afek and E. Gafni,\n                      End\u2010to\u2010end communication in unreliable networks\n                      , in Proc. 7th ACM Symp. on Principles of Distributed Computing, August 1988, pp. 131\u2013148."},{"key":"R7","unstructured":"Y. Afek and E. Gafni,\n                      Bootstrap network resynchronization: An efficient technique for end\u2010to\u2010end communication\n                      , in Proc. 10th Ann. ACM Symp. on Principles of Distributed Computing, August 1991, pp. 295\u2013307."},{"key":"R8","unstructured":"A. Arora and M. Gouda,\n                      Distributed reset\n                      , in Proc. 10th Conf. on Foundations of Software Technology and Theoretical Computer Science, Lecture Notes in Comp. Sci. 472, Springer\u2010Verlag, New York, 1990, pp. 316\u2013331."},{"key":"R9","unstructured":"B. Awerbuch, O. Goldreich, and A. Herzberg,\n                      A quantitative approach to dynamic networks\n                      , in Proc. 9th ACM Symp. on Principles of Distributed Computing, August 1990, pp. 189\u2013204."},{"key":"R10","unstructured":"Y. Afek, E. Gafni, and A. Ros\u00e9n,\n                      The slide mechanism with applications in dynamic networks\n                      , in Proc. 11th ACM Symp. on Principles of Distributed Computing, August 1992, pp. 35\u201346."},{"key":"R11","unstructured":"A. Awerbuch, S. Kutten, Y. Mansour, B. Patt\u2010Shamir, and G. Varghese,\n                      Time optimal self\u2010stabilizing synchronization\n                      , in Proc. 25th ACM Symp. on the Theory of Computing, 1992, pp. 652\u2013661."},{"key":"R12","unstructured":"Y. Afek, S. Kutten, and M. Yung,\n                      Memory\u2010efficient self\u2010stabilization on general networks\n                      , in Proc. 4th Workshop on Distributed Algorithms, Italy, 1990, Lecture Notes in Comp. Sci. 486, Springer\u2010Verlag, New York, 1990, pp. 15\u201328."},{"key":"R13","unstructured":"B. Awerbuch and T. Leighton,\n                      A simple local\u2010control approximation algorithm for multi\u2010commodity flow\n                      , in Proc. 34th IEEE Symp. on Foundations of Computer Science, 1993, pp. 459\u2013469."},{"key":"R14","unstructured":"B. Awerbuch and T. Leighton,\n                      Improved approximation algorithms for the multi\u2010commodity flow problem and local competitive routing in dynamic networks\n                      , in Proc. 26th ACM Symp. on the Theory of Computing, 1994, pp. 487\u2013496."},{"key":"R15","unstructured":"Baruch Awerbuch, Yishay Mansour, An efficient topology update protocol for dynamic networks, Lecture Notes in Comput. Sci., Vol. 647, Springer, Berlin, 1992, 185\u20132021250388"},{"key":"R16","unstructured":"B. Awerbuch, Y. Mansour, and N. Shavit,\n                      Polynomial end to end communication\n                      , in Proc. 30th IEEE Ann. Symp. on Foundations of Computer Science, October 1989, pp. 358\u2013363."},{"key":"R17","unstructured":"B. Awerbuch and R. Ostrovsky,\n                      Memory\u2010efficient and self\u2010stabilizing network RESET\n                      , in Proc. 13th ACM Symp. on Principles of Distributed Computing, August 1994, pp. 254\u2013263."},{"key":"R18","unstructured":"B. Awerbuch, B. Patt\u2010Shamir, and G. Varghese,\n                      Self\u2010stabilization by local checking and correction\n                      , in Proc. 32nd IEEE Ann. Symp. on Foundations of Computer Science, October 1991, pp. 268\u2013277."},{"key":"R19","unstructured":"B. Awerbuch and M. Sipser,\n                      Dynamic networks are as fast as static networks\n                      , in Proc. 29th IEEE Ann. Symp. on Foundations of Computer Science, October 1988, pp. 206\u2013220."},{"key":"R20","unstructured":"B. Awerbuch and G. Varghese,\n                      Distributed program checking: A paradigm for building self\u2010stabilizing distributed protocols\n                      , in Proc. 32nd IEEE Ann. Symp. on Foundations of Computer Science, October 1991, pp. 258\u2013267."},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1109\/26.2744"},{"key":"R21","unstructured":"also in IFIP 3rd Workshop on Protocol Specification, Testing and Verification, III."},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1145\/361179.361202"},{"key":"R23","first-page":"1292","volume":"1958","author":"Koroljuk V.","year":"1958","journal-title":"Dopovidi Akad. Nauk Ukra\u00ef n. RSR."},{"key":"R24","unstructured":"S. Dolev and J. Welch,\n                      Crash resilient communication in dynamic networks\n                      , in Proc. 7th International Workshop on Distributed Algorithms, Lecture Notes in Comp. Sci. 725, Springer\u2010Verlag, New York, 1993, pp. 129\u2013144."},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1979.1094473"},{"key":"R26","unstructured":"G. Itkis and L. Levin,\n                      Fast and lean self\u2010stabilizing asynchronous protocols\n                      , in Proc. 35th IEEE Ann. Symp. on Foundations of Computer Science, November 1994, pp. 226\u2013239."},{"key":"R27","unstructured":"S. Katz and K. Perry,\n                      Self\u2010stabilizing extensions for message\u2010passing systems\n                      , in Proc. 9th ACM Symp. on Principles of Distributed Computing, August 1990, pp. 91\u2013101."},{"key":"R28","unstructured":"A. Mayer, Y. Ofek, R. Ostrovsky, and M. Yung,\n                      Self\u2010stabilizing symmetry breaking in constant\u2010space\n                      , in Proc. 24th ACM Symp. on the Theory of Computing, 1992, pp. 667\u2013678."},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1983.1056696"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539795296760","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:14:10Z","timestamp":1787336050000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539795296760"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":30,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539795296760"],"URL":"https:\/\/doi.org\/10.1137\/s0097539795296760","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}