Skip to main content

Research Repository

Advanced Search

Termination of amnesiac flooding

Hussak, Walter; Trehan, Amitabh

Termination of amnesiac flooding Thumbnail


Walter Hussak


We consider a stateless ‘amnesiac’ variant of the stateful distributed network flooding algorithm, expanding on our conference papers [PODC’19, STACS’20]. Flooding begins with a set of source ‘initial’ nodes I seeking to broadcast a message M in rounds, in a network represented by an undirected graph (G, E) with set of nodes G and edges E. In every round, nodes with M send M to all neighbours from which they did not receive M in the previous round. Nodes do not remember earlier rounds, raising the possibility that M circulates indefinitely. Stateful flooding overcomes this by nodes recording every message circulated and ignoring M 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 (G, E) to be I-bipartite if the quotient graph, contracting all nodes in I to a single node, is bipartite. We prove that, if d is the diameter and e(I) the eccentricity of the set I, flooding terminates in e(I) rounds if (G, E) is I-bipartite and j rounds with e(I) < j ≤ e(I)+d+1≤2d+1 if (G, E) 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 τ rounds in single-source bipartite graphs terminate by round 2d+τ−1 , and all cases of multiple-edge fixed delays in multiple-source cycles terminate.


Hussak, W., & Trehan, A. (2023). Termination of amnesiac flooding. Distributed Computing, 36(2), 193-207.

Journal Article Type Article
Acceptance Date Apr 9, 2023
Online Publication Date May 1, 2023
Publication Date 2023-06
Deposit Date Apr 29, 2023
Publicly Available Date Aug 16, 2023
Journal Distributed Computing
Print ISSN 0178-2770
Electronic ISSN 1432-0452
Publisher Springer
Peer Reviewed Peer Reviewed
Volume 36
Issue 2
Pages 193-207
Public URL


Published Journal Article (629 Kb)

Publisher Licence URL

Copyright Statement
This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit

You might also like

Downloadable Citations