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 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.

History

School

  • Science

Department

  • Computer Science

Published in

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

Pages

153 - 155

Publisher

ACM

Version

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

2019-07-16

Copyright date

2019

ISBN

9781450362177

Language

en

Alternative title

Brief announcement: On termination of a flooding process

Location

Toronto, ON, Canada

Event dates

July 29, 2019 - August 2, 2019

Depositor

Dr Amitabh Trehan

Exports

Logo branding

Categories

Exports