Flooding-BA-PODC19-PreSubmission.pdf (726.2 kB)

On termination of a flooding process

Download (726.2 kB)
conference contribution
posted on 02.09.2019, 11:23 by Walter Hussak, Amitabh Trehan
Flooding is a fundamental distributed algorithms technique. Consider the following flooding process, for simplicity, in a synchronous message passing network: A distinguished node begins the flooding process by sending the (same) message to all its neighbours in the first round. In subsequent rounds, every node receiving the message relays a copy of the message further to all those, and only those, nodes it did not receive the message from in the previous round. However, the nodes do not remember if they've taken part in the flooding before and therefore will repeat the process every time they get a message. In other words, they execute an amnesiac flooding process with memory only of the present round. The flooding process terminates in a particular round when no edge in the network carries the message in that, and, hence, subsequent, rounds. We call this process Amnesiac Flooding (AF). In this work, the main question we address is whether AF will terminate on an arbitrary network (graph) and in what time? We show that, indeed, AF terminates on any arbitrary graph. Further, AF terminates in at most D rounds in bipartite graphs and at most 2D + 1 rounds in non-bipartite graphs - in this brief announcement, we show this for the bipartite case only. We also show that in a natural asynchronous variant of AF, an adversary can always ensure non-termination.



  • Science


  • Computer Science

Published in

Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC '19)


153 - 155




AM (Accepted Manuscript)

Rights holder

© The Authors

Publisher statement

© Owner/Author 2019. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in the Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, http://dx.doi.org/10.1145/3293611.3331586.

Publication date


Copyright date






Alternative title

Brief announcement: On termination of a flooding process


Toronto, ON, Canada

Event dates

July 29, 2019 - August 2, 2019


Dr Amitabh Trehan


Logo branding