Flooding-BA-PODC19-PreSubmission.pdf (726.2 kB)
On termination of a flooding process
conference contribution
posted on 2019-09-02, 11:23 authored by Walter HussakWalter Hussak, Amitabh TrehanFlooding 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 - 155Publisher
ACMVersion
- AM (Accepted Manuscript)
Rights holder
© The AuthorsPublisher 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-16Copyright date
2019ISBN
9781450362177Language
- en
Alternative title
Brief announcement: On termination of a flooding processLocation
Toronto, ON, CanadaEvent dates
July 29, 2019 - August 2, 2019Depositor
Dr Amitabh TrehanUsage metrics
Categories
No categories selectedLicence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC