This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages)
|
Amnesic flooding is a stateless/memoryless variant of the classic distributed flooding algorithm on networks/graphs.[1]
It can be stated informally as follows:
For a single source and in a synchronous network, the process begins (round 1) with a node sending a message to all its neighbours. Subsequently, every node that has received the message will forward it to all the neighbours that did not receive the message from in the previous round, and so on...'.
It can be easily seen that this will result in the message being flooded to every node in the network (i.e. Broadcast). Unlike classic flooding algorithms which keep a list of messages in circulation so that they can reject if the message is seen again (ensuring termination), amnesiac flooding keeps no record of messages received or their history (hence, called Amnesiac or Stateless). The paper[2] asked `Will Amnesiac Flooding ever terminate?' i.e. will message(s) circulate forever or will there be a round when no node will forward the message(s). The surprising result is that not only does Amnesiac Flooding terminate, it terminates almost as efficiently as the stateful flooding (in same number of rounds if the topology is bipartite and at most twice slower if it is non-bipartite).
History edit
Amnesiac Flooding was first introduced by Walter Hussak[3] and Amitabh Trehan[4] in an ACM PODC 2019 research paper.[2] More expanded versions later appeared at STACS 2020[5] and the Distributed Computing Journal (in 2023).[1]
More Results on AF and Extensions edit
A number of research paper follow up on the first introduction of the problem and the initial result on termination. In particular:
- Volker Turauwrote a series of papers proposing alternate analysis methods and variants of the original amnesiac flooding problem.[6][7][8]
- Weak Amnesiac Flooding termination: In,[9] the authors discuss and extend results on termination of multiple simultaneous amnesiac flooding messages proposed in [10]
References edit
- ^ a b Hussak, Walter; Trehan, Amitabh (2023-06-01). "Termination of amnesiac flooding". Distributed Computing. 36 (2): 193–207. doi:10.1007/s00446-023-00448-y. ISSN 1432-0452.
- ^ a b Hussak, Walter; Trehan, Amitabh (2019-07-16). "On Termination of a Flooding Process". Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing. PODC '19. New York, NY, USA: Association for Computing Machinery. pp. 153–155. doi:10.1145/3293611.3331586. ISBN 978-1-4503-6217-7. S2CID 263887313.
- ^ "Dr Walter Hussak, Loughborough University". www.lboro.ac.uk. Retrieved 2023-12-13.
- ^ University, Durham. "Dr Amitabh Trehan - Durham University". www.durham.ac.uk. Retrieved 2023-12-13.
- ^ Hussak, Walter; Trehan, Amitabh (2020). "On the Termination of Flooding". DROPS-IDN/V2/Document/10.4230/LIPIcs.STACS.2020.17. Schloss-Dagstuhl - Leibniz Zentrum für Informatik. doi:10.4230/LIPIcs.STACS.2020.17. S2CID 212419425.
- ^ Turau, Volker (2021). "Amnesiac Flooding: Synchronous Stateless Information Dissemination". In Bureš, Tomáš; Dondi, Riccardo; Gamper, Johann; Guerrini, Giovanna; Jurdziński, Tomasz; Pahl, Claus; Sikora, Florian; Wong, Prudence W.H. (eds.). Lecture Notes in Computer Science. Vol. 12607. Cham: Springer International Publishing. pp. 59–73. doi:10.1007/978-3-030-67731-2_5. ISBN 978-3-030-67731-2. S2CID 231705141.
{{cite book}}:|journal=ignored (help); Missing or empty|title=(help) - ^ Turau, Volker (2020). "Stateless Information Dissemination Algorithms". In Richa, Andrea Werneck; Scheideler, Christian (eds.). Lecture Notes in Computer Science. Vol. 12156. Cham: Springer International Publishing. pp. 183–199. doi:10.1007/978-3-030-54921-3_11. ISBN 978-3-030-54921-3.
{{cite book}}:|journal=ignored (help); Missing or empty|title=(help) - ^ Turau, Volker (2020-07-21), Analysis of Amnesiac Flooding, arXiv:2002.10752
- ^ Bayramzadeh, Zahra; Kshemkalyani, Ajay D.; Molla, Anisur Rahaman; Sharma, Gokarna (2021). Echihabi, Karima; Meyer, Roland (eds.). Weak Amnesiac Flooding of Multiple Messages. Lecture Notes in Computer Science. Cham: Springer International Publishing. pp. 88–94. doi:10.1007/978-3-030-91014-3_6. ISBN 978-3-030-91014-3. S2CID 244818918.
{{cite book}}:|journal=ignored (help) - ^ Hussak, Walter; Trehan, Amitabh (2020-09-12), Terminating cases of flooding, arXiv:2009.05776
This article needs additional or more specific categories. (April 2024) |