{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,30]],"date-time":"2025-10-30T06:57:05Z","timestamp":1761807425835,"version":"3.41.0"},"reference-count":72,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2008,9,1]],"date-time":"2008-09-01T00:00:00Z","timestamp":1220227200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2008,9]]},"abstract":"<jats:p>In this article, we show that keeping track of history enables significant improvements in the communication complexity of dynamic network protocols. We present a communication optimal maintenance of a spanning tree in a dynamic network. The amortized (on the number of topological changes) message complexity is<jats:italic>O<\/jats:italic>(<jats:italic>V<\/jats:italic>), where<jats:italic>V<\/jats:italic>is the number of nodes in the network. The message size used by the algorithm is<jats:italic>O<\/jats:italic>(log |ID|) where |ID| is the size of the name space of the nodes. Typically, log |ID| =<jats:italic>O<\/jats:italic>(log<jats:italic>V<\/jats:italic>).<\/jats:p><jats:p>Previous algorithms that adapt to dynamic networks involved \u03a9 (<jats:italic>E<\/jats:italic>) messages per topological change\u2014inherently paying for re-computation of the tree from scratch.<\/jats:p><jats:p>Spanning trees are essential components in many distributed algorithms. Some examples include<jats:italic>broadcast<\/jats:italic>(dissemination of messages to all network nodes),<jats:italic>multicast, reset<\/jats:italic>(general adaptation of static algorithms to dynamic networks), routing,<jats:italic>termination detection<\/jats:italic>, and more. Thus, our efficient maintenance of a spanning tree implies the improvement of algorithms for these tasks. Our results are obtained using a novel technique to save communication. A node uses information received in the past in order to deduce present information from the fact that certain messages were NOT sent by the node's neighbor. This technique is one of our main contributions.<\/jats:p>","DOI":"10.1145\/1391289.1391292","type":"journal-article","created":{"date-parts":[[2008,9,16]],"date-time":"2008-09-16T16:32:40Z","timestamp":1221582760000},"page":"1-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":21,"title":["Optimal maintenance of a spanning tree"],"prefix":"10.1145","volume":"55","author":[{"given":"Baruch","family":"Awerbuch","sequence":"first","affiliation":[{"name":"Johns Hopkins University, Baltimore, Maryland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Israel","family":"Cidon","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shay","family":"Kutten","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,9,18]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1987.7"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0819"},{"key":"e_1_2_1_3_1","unstructured":"Afek Y. Awerbuch B. and Moriel H. 1989. Overhead of resetting a communication protocol is independent of the size of the network. (May) Unpublished manuscript. Afek Y. Awerbuch B. and Moriel H. 1989. Overhead of resetting a communication protocol is independent of the size of the network. (May) Unpublished manuscript."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/62546.62570"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/112600.112625"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/135419.135430"},{"volume-title":"Proceedings of the 5th Workshop on Distributed Algorithms. Lecture Notes in Computer Science, Springer-Verlag","author":"Afek Y.","key":"e_1_2_1_7_1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.312126"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2002.808411"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/4221.4227"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90018-A"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/93385.93412"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89570"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795279931"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/93385.93419"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/77600.77618"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63503"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1986.16"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185378"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/256292.256298"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1988.21938"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Baratz A. E. Gray J. P. Green Jr. P. E. Jaffe J. M. and Pozefski D. P. 1985. SNA networks of small systems. IEEE J. Select. Areas Commun. SAC-3 3 (May) 416--426. Baratz A. E. Gray J. P. Green Jr. P. E. Jaffe J. M. and Pozefski D. P. 1985. SNA networks of small systems. IEEE J. Select. Areas Commun. SAC-3 3 (May) 416--426.","DOI":"10.1109\/JSAC.1985.1146222"},{"key":"e_1_2_1_23_1","unstructured":"Barnes D. and Sakandar B. 2004. Cisco LAN Switching Fundamentals. Cisco Press ISBN: 1587050897. Barnes D. and Sakandar B. 2004. Cisco LAN Switching Fundamentals. Cisco Press ISBN: 1587050897."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/190314.190327"},{"volume-title":"Proceedings of IEEE INFOCOM. IEEE Computer Society Press","author":"Bellur B.","key":"e_1_2_1_25_1"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2004.03.009"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/214451.214456"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/52324.52357"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/75246.75269"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00619-9"},{"key":"e_1_2_1_31_1","article-title":"PARIS: An approach to integrated high-speed private networks","volume":"1","author":"Cidon I.","year":"1988","journal-title":"Int. J. Digital Analog Cabled Syst."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/26.387408"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.382023"},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","first-page":"195","DOI":"10.3233\/HSN-1999-165","article-title":"OPENET: An open and efficient control platform for ATM networks","volume":"8","author":"Cidon I.","year":"1999","journal-title":"J. High Speed Netw."},{"volume-title":"Proceedings of the 9th International Conference on Computer Communication (ICCC88)","author":"Cohen R.","key":"e_1_2_1_35_1"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(80)90021-6"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02278851"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281100.1281128"},{"key":"e_1_2_1_39_1","unstructured":"Even S. 1979. Graph Algorithms. Computer Science Press. Even S. 1979. Graph Algorithms. Computer Science Press."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1979.1094473"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3149.214121"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214055"},{"volume-title":"Proceedings of the 2nd Workshop on Distributed Algorithms (WDAG'87)","series-title":"Lecture Notes in Computer Science","author":"Gafni E.","key":"e_1_2_1_43_1"},{"key":"e_1_2_1_44_1","unstructured":"Gafni E. and Afek Y. 1987. Local fail-safe resynch procedure. unpublished manuscript (Apr.). Gafni E. and Afek Y. 1987. Local fail-safe resynch procedure. unpublished manuscript (Apr.)."},{"key":"e_1_2_1_45_1","unstructured":"Gallager R. G. 1976. A shortest path routing algorithm with automatic resynch. Tech. repo. MIT LIDS (Mar). Gallager R. G. 1976. A shortest path routing algorithm with automatic resynch. Tech. repo. MIT LIDS (Mar)."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1977.1093711"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/357195.357200"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/75247.75268"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.222913"},{"volume-title":"Proceedings of ITC'18","author":"Guerin R.","key":"e_1_2_1_50_1"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/26.87189"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/0169-7552(89)90066-4"},{"key":"e_1_2_1_54_1","unstructured":"IETF. http:\/\/www.ietf.org\/proceedings\/02nov\/179.htm. IETF. http:\/\/www.ietf.org\/proceedings\/02nov\/179.htm."},{"volume-title":"Proceedings of the 5th International Workshop on Distributed Algorithms","series-title":"Lecture Notes in Computer Science","author":"Italiano G. F.","key":"e_1_2_1_55_1"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009225"},{"key":"e_1_2_1_57_1","article-title":"A responsive distributed routing protocol","volume":"7","author":"Jaffe J.","year":"1982","journal-title":"IEEE Trans. Commun. COM-30"},{"volume-title":"Tech. Rep. 401, Dept of CS, Technion, Haifa, Israel (Feb).","year":"1986","author":"Korach E.","key":"e_1_2_1_58_1"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(89)90103-5"},{"volume-title":"Proceedings of the 13th International Symposium on Distributed Computing (DISC'99)","author":"Kutten S.","key":"e_1_2_1_60_1"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1980.1094721"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1147\/sj.344.0564"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1979.1094552"},{"key":"e_1_2_1_64_1","doi-asserted-by":"crossref","unstructured":"Ogier R. Templin F. and Lewis M. 2004. RFC3684: Topology Dissemination Based on Reverse-Path Forwarding (TBRPF). An Internet RFC: http:\/\/portal.acm.org\/citation.cfm-id=RFC3684. Ogier R. Templin F. and Lewis M. 2004. RFC3684: Topology Dissemination Based on Reverse-Path Forwarding (TBRPF). An Internet RFC: http:\/\/portal.acm.org\/citation.cfm-id=RFC3684.","DOI":"10.17487\/rfc3684"},{"key":"e_1_2_1_65_1","volume-title":"Interconnections: Bridges, Routers, Switches, and Internetworking Protocols","author":"Perlman R.","year":"1999","edition":"2"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/75246.75270"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(92)90017-7"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1983.1056620"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1981.1095036"},{"key":"e_1_2_1_70_1","article-title":"Broadcasting topology information in computer networks","author":"Spinelli J.M.","year":"1989","journal-title":"IEEE Trans. Commun."},{"key":"e_1_2_1_71_1","unstructured":"Tanenbaum A. 2002. Computer Networks (4th Ed.) Prentice-Hall Engewood Cliffs NJ. Tanenbaum A. 2002. Computer Networks (4th Ed.) Prentice-Hall Engewood Cliffs NJ."},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1109\/26.2794"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1983.1056696"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1391289.1391292","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1391289.1391292","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:58:04Z","timestamp":1750255084000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1391289.1391292"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,9]]},"references-count":72,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,9]]}},"alternative-id":["10.1145\/1391289.1391292"],"URL":"https:\/\/doi.org\/10.1145\/1391289.1391292","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2008,9]]},"assertion":[{"value":"2005-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-09-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}