{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T14:55:53Z","timestamp":1763477753830,"version":"3.27.0"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,5,1]],"date-time":"2023-05-01T00:00:00Z","timestamp":1682899200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,5,1]],"date-time":"2023-05-01T00:00:00Z","timestamp":1682899200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2023,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider a stateless \u2018amnesiac\u2019 variant of the stateful distributed network flooding algorithm, expanding on our conference papers [PODC\u201919, STACS\u201920]. Flooding begins with a set of source \u2018initial\u2019 nodes<jats:italic>I<\/jats:italic>seeking to broadcast a message<jats:italic>M<\/jats:italic>in rounds, in a network represented by an undirected graph (<jats:italic>G<\/jats:italic>,\u00a0<jats:italic>E<\/jats:italic>) with set of nodes<jats:italic>G<\/jats:italic>and edges<jats:italic>E<\/jats:italic>. In every round, nodes with<jats:italic>M<\/jats:italic>send<jats:italic>M<\/jats:italic>to all neighbours from which they did not receive<jats:italic>M<\/jats:italic>in the previous round. Nodes do not remember earlier rounds, raising the possibility that<jats:italic>M<\/jats:italic>circulates indefinitely. Stateful flooding overcomes this by nodes recording every message circulated and ignoring<jats:italic>M<\/jats:italic>if received again. This overhead was assumed to be necessary. We show that almost optimal broadcast can still be achieved without this overhead. We prove that amnesiac flooding terminates on every finite graph and derive sharp bounds for termination times. Define (<jats:italic>G<\/jats:italic>,\u00a0<jats:italic>E<\/jats:italic>) to be<jats:italic>I-bipartite<\/jats:italic>if the quotient graph, contracting all nodes in<jats:italic>I<\/jats:italic>to a single node, is bipartite. We prove that, if<jats:italic>d<\/jats:italic>is the diameter and<jats:italic>e<\/jats:italic>(<jats:italic>I<\/jats:italic>) the eccentricity of the set<jats:italic>I<\/jats:italic>, flooding terminates in<jats:italic>e<\/jats:italic>(<jats:italic>I<\/jats:italic>) rounds if (<jats:italic>G<\/jats:italic>,\u00a0<jats:italic>E<\/jats:italic>) is I-bipartite and<jats:italic>j<\/jats:italic>rounds with<jats:italic>e<\/jats:italic>(<jats:italic>I<\/jats:italic>) &lt;<jats:italic>j<\/jats:italic><jats:inline-formula><jats:alternatives><jats:tex-math>$$\\le $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mo>\u2264<\/mml:mo><\/mml:math><\/jats:alternatives><\/jats:inline-formula><jats:inline-formula><jats:alternatives><jats:tex-math>$$e(I)+d+1 \\le 2d +1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>e<\/mml:mi><mml:mo>(<\/mml:mo><mml:mi>I<\/mml:mi><mml:mo>)<\/mml:mo><mml:mo>+<\/mml:mo><mml:mi>d<\/mml:mi><mml:mo>+<\/mml:mo><mml:mn>1<\/mml:mn><mml:mo>\u2264<\/mml:mo><mml:mn>2<\/mml:mn><mml:mi>d<\/mml:mi><mml:mo>+<\/mml:mo><mml:mn>1<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>if (<jats:italic>G<\/jats:italic>,\u00a0<jats:italic>E<\/jats:italic>) is non I-bipartite. The separation in the termination times can be used for distributed discovery of topologies\/distances in graphs. Termination is guaranteed if edges are lost during flooding but not, in general, if there is a delay at an edge. However, the cases of single-edge fixed delays of duration<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\tau $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>\u03c4<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>rounds in single-source bipartite graphs terminate by round<jats:inline-formula><jats:alternatives><jats:tex-math>$$2d+\\tau -1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mn>2<\/mml:mn><mml:mi>d<\/mml:mi><mml:mo>+<\/mml:mo><mml:mi>\u03c4<\/mml:mi><mml:mo>-<\/mml:mo><mml:mn>1<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and all cases of multiple-edge fixed delays in multiple-source cycles terminate.<\/jats:p>","DOI":"10.1007\/s00446-023-00448-y","type":"journal-article","created":{"date-parts":[[2023,5,1]],"date-time":"2023-05-01T13:02:05Z","timestamp":1682946125000},"page":"193-207","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Termination of amnesiac flooding"],"prefix":"10.1007","volume":"36","author":[{"given":"Walter","family":"Hussak","sequence":"first","affiliation":[]},{"given":"Amitabh","family":"Trehan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,5,1]]},"reference":[{"key":"448_CR1","doi-asserted-by":"crossref","unstructured":"Adamek, J., Nesterenko, M., Robinson, J.S., Tixeuil, S.: Stateless reliable geocasting. In: 36th IEEE Symposium on Reliable Distributed Systems, SRDS 2017, Hong Kong, Hong Kong, p. 44\u201353, IEEE Computer Society (2017)","DOI":"10.1109\/SRDS.2017.13"},{"key":"448_CR2","doi-asserted-by":"publisher","DOI":"10.1002\/0471478210","volume-title":"Distributed Computing: Fundamentals","author":"H Attiya","year":"2004","unstructured":"Attiya, H., Welch, J.: Distributed Computing: Fundamentals. Simulations and Advanced Topics. Wiley, Hoboken (2004)"},{"key":"448_CR3","doi-asserted-by":"publisher","unstructured":"Awerbuch, B., Khandekar, R.: Greedy distributed optimization of multi-commodity flows. In: Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing (PODC \u201907). Association for Computing Machinery, New York, NY, USA, p. 274\u2013283. https:\/\/doi.org\/10.1145\/1281100.1281140","DOI":"10.1145\/1281100.1281140"},{"key":"448_CR4","doi-asserted-by":"publisher","unstructured":"Awerbuch, B., Khandekar, R.: Stateless distributed gradient descent for positive linear programs. In: Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing (STOC \u201908). Association for Computing Machinery, New York, NY, USA, p. 691\u2013700. https:\/\/doi.org\/10.1145\/1374376.1374476","DOI":"10.1145\/1374376.1374476"},{"key":"448_CR5","doi-asserted-by":"publisher","unstructured":"Bayramzadeh, Z., Kshemkalyani, A.D., Molla, A.R., Sharma, G.: Weak amnesiac flooding. In: 20th International Symposium on Parallel and Distributed Computing ISPDC, p. 122-129 (2021). https:\/\/doi.org\/10.1109\/ISPDC52870.2021.9521629","DOI":"10.1109\/ISPDC52870.2021.9521629"},{"key":"448_CR6","doi-asserted-by":"publisher","unstructured":"Bayramzadeh, Z., Kshemkalyani, A.D., Molla, A.R., Sharma, G.: Weak amnesiac flooding of multiple messages. In: Echihabi, K., Meyer, R., (eds.) Networked Systems. NETYS (2021). Lecture Notes in Computer Science, vol. 12754. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-91014-3_6, https:\/\/doi.org\/10.1145\/3369740.3369786","DOI":"10.1007\/978-3-030-91014-3_6 10.1145\/3369740.3369786"},{"issue":"6","key":"448_CR7","doi-asserted-by":"publisher","first-page":"815","DOI":"10.1017\/S0963548306007565","volume":"15","author":"JN Cooper","year":"2006","unstructured":"Cooper, J.N., Spencer, J.: Simulating a random walk with constant error. Comb. Probab. Comput. 15(6), 815\u2013822 (2006)","journal-title":"Comb. Probab. Comput."},{"key":"448_CR8","doi-asserted-by":"crossref","unstructured":"Das Sarma A., Danupon N., Gopal P.: Fast distributed random walks. In: PODC, p. 161\u2013170 (2009)","DOI":"10.1145\/1582716.1582745"},{"key":"448_CR9","doi-asserted-by":"crossref","unstructured":"Das Sarma A., Danupon N., Gopal P., Prasad T.: Efficient distributed random walks with applications. In: PODC (2010)","DOI":"10.1145\/1835698.1835745"},{"key":"448_CR10","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/j.endm.2011.09.050","volume":"38","author":"B Doerr","year":"2011","unstructured":"Doerr, B., Fouz, M., Friedrich, T.: Social networks spread rumors in sublogarithmic time. Electron. Notes Discret. Math. 38, 303\u2013308 (2011)","journal-title":"Electron. Notes Discret. Math."},{"key":"448_CR11","doi-asserted-by":"publisher","unstructured":"Dolev, D., Erdmann, M., Lutz, N., Schapira, M., Zair, A.: Stateless computation. In: Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC \u201917), p. 419\u2013421, Association for Computing Machinery, New York, NY, USA (2017). https:\/\/doi.org\/10.1145\/3087801.3087854","DOI":"10.1145\/3087801.3087854"},{"key":"448_CR12","unstructured":"Els\u00e4sser, R., Sauerwald, T.: The power of memory in randomized broadcasting. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201908, p. 218\u2013227, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2008)"},{"issue":"3","key":"448_CR13","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/j.peva.2005.01.002","volume":"63","author":"C Gkantsidis","year":"2006","unstructured":"Gkantsidis, C., Mihail, M., Saberi, A.: Random walks in peer-to-peer networks: algorithms and evaluation. Perform Eval 63(3), 241\u2013263 (2006)","journal-title":"Perform Eval"},{"issue":"2","key":"448_CR14","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1109\/90.769773","volume":"7","author":"AS Gopal","year":"1999","unstructured":"Gopal, A.S., Gopal, I.S., Kutten, S.: Fast broadcast in high-speed networks. IEEE\/ACM Trans. Netw. 7(2), 262\u2013275 (1999)","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"448_CR15","doi-asserted-by":"crossref","unstructured":"Hussak, W., Trehan, A.: On termination of a flooding process. In: Robinson, P., Ellen, F. (eds.) Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, p. 153\u2013155. ACM (2019)","DOI":"10.1145\/3293611.3331586"},{"key":"448_CR16","unstructured":"Hussak, W., Trehan, A.: Terninating cases of flooding. CoRR (2020). arXiv:2009.05776"},{"key":"448_CR17","unstructured":"Hussak, W., Trehan, A.: On the termination of flooding. In: Paul, C., Bl\u00e4ser, M. (eds.) 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), Leibniz International Proceedings in Informatics (LIPIcs), vol. 154, p. 17:1\u201317:13, Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2020)"},{"key":"448_CR18","doi-asserted-by":"crossref","unstructured":"Karp, B., Kung, H.T.: Gpsr: greedy perimeter stateless routing for wireless networks. In: Proceedings of the 6th Annual International Conference on Mobile Computing and Networking, p. 243\u2013254, New York, NY, USA (2000)","DOI":"10.1145\/345910.345953"},{"key":"448_CR19","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/j.jcss.2019.07.001","volume":"106","author":"A Kosowski","year":"2019","unstructured":"Kosowski, A., Pajak, D.: Does adding more agents make a difference? A case study of cover time for the rotor-router. J. Comput. Syst. Sci. 106, 80\u201393 (2019)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"448_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2699440","volume":"62","author":"S Kutten","year":"2015","unstructured":"Kutten, S., Pandurangan, G., Peleg, D., Robinson, P., Trehan, A.: On the complexity of universal leader election. J. ACM 62(1), 1\u201327 (2015)","journal-title":"J. ACM"},{"key":"448_CR21","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/j.tcs.2014.02.009","volume":"561","author":"S Kutten","year":"2015","unstructured":"Kutten, S., Pandurangan, G., Peleg, D., Robinson, P., Trehan, A.: Sublinear bounds for randomized leader election. Theor. Comput. Sci. 561, 134\u2013143 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"448_CR22","volume-title":"Distributed Algorithms","author":"N Lynch","year":"1996","unstructured":"Lynch, N.: Distributed Algorithms. Morgan Kaufmann Publishers, San Mateo, CA (1996)"},{"key":"448_CR23","doi-asserted-by":"publisher","first-page":"711","DOI":"10.1109\/TCOM.1980.1094721","volume":"28","author":"J McQuillan","year":"1980","unstructured":"McQuillan, J., Richer, I., Rosen, E.: The new routing algorithm for ARPANET. IEEE Trans. Commun. 28, 711\u2013719 (1980)","journal-title":"IEEE Trans. Commun."},{"key":"448_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jpdc.2015.02.005","volume":"81\u201382","author":"O Michail","year":"2015","unstructured":"Michail, O., Spirakis, P.G.: Terminating population protocols via some minimal global knowledge assumptions. J. Parallel Distrib. Comput. 81\u201382, 1\u201310 (2015)","journal-title":"J. Parallel Distrib. Comput."},{"key":"448_CR25","unstructured":"Parulkar, G.M.: NOANET: An Experimental Flood Local Area Network PhD Dissertation, pp. 88\u2013103. University of Delaware, Delaware (1987)"},{"issue":"1","key":"448_CR26","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/0743-7315(90)90074-Y","volume":"8","author":"D Peleg","year":"1990","unstructured":"Peleg, D.: Time-optimal leader election in general networks. J. Parallel Distrib. Comput. 8(1), 96\u201399 (1990)","journal-title":"J. Parallel Distrib. Comput."},{"key":"448_CR27","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed Computing: A Locality Sensitive Approach","author":"D Peleg","year":"2000","unstructured":"Peleg, D.: Distributed Computing: A Locality Sensitive Approach. SIAM, Bangkok (2000)"},{"key":"448_CR28","doi-asserted-by":"crossref","unstructured":"Rahman, A., lesinski, W., Gburzynski, P.: Controlled flooding in wireless ad-hoc networks, In: Proceeding IWWAN\u201904, p. 73-78 (2004)","DOI":"10.1109\/IWWAN.2004.1525544"},{"key":"448_CR29","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1109\/TIT.1983.1056620","volume":"29","author":"A Segall","year":"1983","unstructured":"Segall, A.: Distributed network protocols. IEEE Trans. Inf. Theory 29, 23\u201335 (1983)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"448_CR30","volume-title":"Computer Networks","author":"A Tanenbaum","year":"2011","unstructured":"Tanenbaum, A.: Computer Networks. Pearson Prentice Hall, Hoboken (2011)"},{"key":"448_CR31","unstructured":"Tel, G.: Introduction to Distributed Algorithms. Cambridge University Press, New York, NY (1994)"},{"key":"448_CR32","unstructured":"Turau, V.: Analysis of amnesiac flooding. (2020). arXiv:2002.10752"},{"key":"448_CR33","doi-asserted-by":"crossref","unstructured":"Turau, V.: Stateless information dissemination algorithms. In: Structural Information and Communication Complexity - 27th International Colloquium, SIROCCO, p. 183\u2013199, Springer (2020)","DOI":"10.1007\/978-3-030-54921-3_11"},{"key":"448_CR34","doi-asserted-by":"crossref","unstructured":"Turau, V.: Amnesiac flooding: synchronous stateless information sissemination. In: 47th International Conference on Current Trends in Theory and Practice of Computer Science. SOFSEM 2021, pp. 59\u201373. Springer, LNTCS (2021)","DOI":"10.1007\/978-3-030-67731-2_5"},{"key":"448_CR35","doi-asserted-by":"crossref","unstructured":"Turau, V.: Synchronous concurrent broadcasts for intermittent channels with bounded capacities. In: Structural Information and Communication Complexity - 28th International Colloquium, SIROCCO, p. 296\u2013312, Springer (2021)","DOI":"10.1007\/978-3-030-79527-6_17"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-023-00448-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-023-00448-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-023-00448-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,19]],"date-time":"2024-10-19T14:46:55Z","timestamp":1729349215000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-023-00448-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,1]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["448"],"URL":"https:\/\/doi.org\/10.1007\/s00446-023-00448-y","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"type":"print","value":"0178-2770"},{"type":"electronic","value":"1432-0452"}],"subject":[],"published":{"date-parts":[[2023,5,1]]},"assertion":[{"value":"12 October 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 April 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 May 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing Interests"}}]}}