On The Termination of a Flooding Process

Amitabh Trehan; Walter Hussak

arxiv: 1907.07078 · v1 · pith:H4EMNSXBnew · submitted 2019-07-16 · 💻 cs.DS · cs.DC· cs.DM

On The Termination of a Flooding Process

Walter Hussak , Amitabh Trehan This is my paper

Pith reviewed 2026-05-24 20:28 UTC · model grok-4.3

classification 💻 cs.DS cs.DCcs.DM

keywords amnesiac floodingterminationbipartite graphsdistributed algorithmssynchronous networkseccentricitydiameterbroadcast

0 comments

The pith

Synchronous amnesiac flooding terminates in e rounds exactly when the graph is bipartite.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that a simple flooding process where nodes forget they have seen the message still always terminates on any finite connected graph when communication is synchronous. It terminates precisely after e rounds, with e the eccentricity of the starting node, exactly when the graph is bipartite. When the graph is not bipartite termination occurs later, after more than e but at most e plus d plus one rounds, d the diameter. These bounds show the process achieves optimal time for reaching all nodes without any auxiliary structures such as spanning trees.

Core claim

We show that synchronous AF from a single source node terminates on G in e rounds, where e is the eccentricity of the source node, if and only if G is bipartite. For non-bipartite G, synchronous AF from a single source terminates in j rounds where e < j ≤ e+d+1 and d is the diameter of G. This limits termination time to at most d and at most 2d + 1 for bipartite and non-bipartite graphs respectively.

What carries the argument

The amnesiac flooding process, in which nodes forward messages without remembering prior receptions, analyzed through the bipartiteness of the underlying graph.

If this is right

AF is asymptotically time optimal for broadcast to all nodes
AF removes the need to construct and maintain spanning trees
The separation in termination times suggests a way to discover graph topology or distances in a distributed manner
In asynchronous settings an adaptive adversary can prevent termination

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Similar termination analysis might apply to other memoryless distributed processes
These results could inform design of lightweight broadcast protocols in networks with unknown bipartiteness

Load-bearing premise

Nodes have no memory of the flooding event and rounds proceed synchronously on a finite connected graph.

What would settle it

A finite connected bipartite graph where synchronous amnesiac flooding from a source fails to terminate after exactly e rounds would falsify the claim.

read the original abstract

Flooding is among the simplest and most fundamental of all distributed network algorithms. A node begins the process by sending a message to all its neighbours and the neighbours, in the next round forward the message to all the neighbours they did not receive the message from and so on. We assume that the nodes do not keep a record of the flooding event. We call this amnesiac flooding (AF). Since the node forgets, if the message is received again in subsequent rounds, it will be forwarded again raising the possibility that the message may be circulated infinitely even on a finite graph. As far as we know, the question of termination for such a flooding process has not been settled - rather, non-termination is implicitly assumed. In this paper, we show that synchronous AF always terminates on any arbitrary finite graph and derive exact termination times which differ sharply in bipartite and non-bipartite graphs. Let $G$ be a finite connected graph. We show that synchronous AF from a single source node terminates on $G$ in $e$ rounds, where $e$ is the eccentricity of the source node, if and only if $G$ is bipartite. For non-bipartite $G$, synchronous AF from a single source terminates in $j$ rounds where $e < j \leq e+d+1$ and $d$ is the diameter of $G$. This limits termination time to at most $d$ and at most $2d + 1$ for bipartite and non-bipartite graphs respectively. If communication/broadcast to all nodes is the motivation, our results show that AF is asymptotically time optimal and obviates the need for construction and maintenance of spanning structures like spanning trees. The clear separation in the termination times of bipartite and non-bipartite graphs also suggests mechanisms for distributed discovery of the topology/distances in arbitrary graphs. For comparison, we show that, in asynchronous networks, an adaptive adversary can force AF to be non-terminating.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper settles termination for synchronous amnesiac flooding with sharp bounds that split cleanly on bipartiteness.

read the letter

The core result is that synchronous amnesiac flooding from one source always ends on a finite connected graph: exactly at eccentricity e when the graph is bipartite, and otherwise after some number of rounds between e+1 and e+d+1. That directly contradicts the prior implicit assumption of possible infinite circulation and supplies the first explicit bounds differentiated by bipartiteness. The authors also show an adaptive adversary can prevent termination in the asynchronous case, which sharpens the contrast with the synchronous setting. These facts are useful for anyone analyzing broadcast or basic information dissemination without memory at the nodes. The work also points out that the termination times make AF asymptotically optimal for reaching all nodes, removing any need for spanning trees in that respect, and that the bipartite/non-bipartite gap might support simple distributed tests for graph properties. The model is stated plainly: synchronous rounds, finite undirected connected graph, single source, nodes forward only to neighbors that did not send in the current round and retain no history. No hidden parameters or fitted quantities appear. The main limitation visible from the abstract is the lack of any proof sketch or derivation steps, so the exact reasoning for the non-bipartite upper bound cannot be checked here. The range given for non-bipartite graphs is not a single exact value, only an interval, which is still a concrete advance but leaves some tightness open. The paper is aimed at distributed-computing researchers who work on network primitives and broadcast. Anyone modeling flooding or gossip without state will find the bounds directly applicable. It deserves a serious referee because the question it answers was open, the claims are precise, and the setting is standard enough that verification is feasible.

Referee Report

0 major / 3 minor

Summary. The paper analyzes termination of synchronous amnesiac flooding (AF) on finite connected undirected graphs. It claims that AF from a single source terminates after exactly e rounds (e = eccentricity of the source) if and only if the graph is bipartite. For non-bipartite graphs termination occurs after some j rounds satisfying e < j ≤ e + d + 1 (d = diameter). This yields termination bounds of at most d rounds for bipartite graphs and at most 2d + 1 rounds for non-bipartite graphs. The paper further shows that an adaptive adversary can force non-termination in asynchronous networks.

Significance. If the stated bounds hold, the work settles the termination question for amnesiac flooding, a fundamental distributed process whose non-termination had been implicitly assumed. It establishes that AF is asymptotically time-optimal for broadcast without constructing or maintaining spanning trees. The sharp bipartite/non-bipartite separation in termination times offers a potential primitive for distributed topology or distance discovery. The asynchronous non-termination result clarifies the role of the synchrony assumption. These are solid contributions to distributed algorithms on graphs.

minor comments (3)

The abstract introduces eccentricity e and diameter d without a formal definition or reference to their standard graph-theoretic meanings; a brief definition upon first use would improve clarity for readers outside graph theory.
The sentence 'As far as we know, the question of termination for such a flooding process has not been settled' would benefit from a short related-work paragraph or citations to prior flooding analyses (even if none address the amnesiac case directly).
The claim that AF 'obviates the need for construction and maintenance of spanning structures' is stated without a direct time comparison to standard BFS-tree flooding; a one-sentence contrast in the abstract or introduction would strengthen the optimality argument.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, recognition of the contributions, and recommendation of minor revision. No major comments were listed in the report, so we have no specific points requiring point-by-point rebuttal. We will incorporate any minor suggestions during revision.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper establishes termination bounds for synchronous amnesiac flooding via direct mathematical argument on finite connected graphs, using the explicit definitions of the process (per-round forwarding to non-sending neighbors with no memory), eccentricity e, diameter d, and bipartiteness. No parameters are fitted to data and then renamed as predictions; no self-citations are invoked as load-bearing support for the central iff statement or the j-bound; no ansatz is smuggled in; and the result is not a renaming of a known empirical pattern. The derivation is self-contained under the stated model assumptions (synchrony, amnesiac nodes, single source, finite connected undirected G) and does not reduce to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 0 invented entities

Result rests on standard assumptions of synchronous distributed computing and finite graphs; no free parameters or invented entities are introduced in the abstract.

axioms (3)

domain assumption The underlying communication network is a finite connected undirected graph.
Explicitly stated as the setting for the termination claims.
domain assumption Nodes operate in synchronous rounds and forward every received message to all neighbors except the immediate sender.
Defines the synchronous AF model used for the termination bounds.
domain assumption Nodes maintain no memory of prior flooding events (amnesiac property).
Central modeling choice that creates the possibility of infinite circulation.

pith-pipeline@v0.9.0 · 5896 in / 1411 out tokens · 25307 ms · 2026-05-24T20:28:28.559052+00:00 · methodology

On The Termination of a Flooding Process

Core claim

What carries the argument

If this is right

Where Pith is reading between the lines

Load-bearing premise

What would settle it

discussion (0)