Amnesiac flooding: Difference between revisions
Content deleted Content added
m v2.05 - Fix errors for CW project (Reference before punctuation) |
clean up refs; cats look ok to me |
||
| Line 5: | Line 5: | ||
''When a node receives a message, it forwards it to all of its neighbours it did not receive the message from. To initiate a broadcast on a network, a node simply sends the message to all of its neighbours.'' |
''When a node receives a message, it forwards it to all of its neighbours it did not receive the message from. To initiate a broadcast on a network, a node simply sends the message to all of its neighbours.'' |
||
The algorithm has been shown to terminate when the message begins at any subset of the network nodes <ref name=":1" /><ref name=":0">{{Citation |last1=Hussak |first1=Walter |title=Terminating cases of flooding |date=2020-09-12 |arxiv=2009.05776 |last2=Trehan |first2=Amitabh}}</ref><ref>{{Citation |last=Turau |first=Volker |title=Analysis of Amnesiac Flooding |date=2020-07-21 |arxiv=2002.10752}}</ref><ref>{{Cite book |last=Turau |first=Volker |date=2021 |
The algorithm has been shown to terminate when the message begins at any subset of the network nodes <ref name=":1" /><ref name=":0">{{Citation |last1=Hussak |first1=Walter |title=Terminating cases of flooding |date=2020-09-12 |arxiv=2009.05776 |last2=Trehan |first2=Amitabh}}</ref><ref>{{Citation |last=Turau |first=Volker |title=Analysis of Amnesiac Flooding |date=2020-07-21 |arxiv=2002.10752}}</ref><ref>{{Cite book |last=Turau |first=Volker |date=2021|publisher=Springer International Publishing |isbn=978-3-030-67731-2 |editor-last=Bureš |editor-first=Tomáš |series=Lecture Notes in Computer Science |volume=12607 |location=Cham |pages=59–73 |language=en |chapter=Amnesiac Flooding: Synchronous Stateless Information Dissemination|title=47th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2021, Bolzano-Bozen, Italy, January 25–29, 2021, Proceedings |doi=10.1007/978-3-030-67731-2_5 |editor2-last=Dondi |editor2-first=Riccardo |editor3-last=Gamper |editor3-first=Johann |editor4-last=Guerrini |editor4-first=Giovanna |editor5-last=Jurdziński |editor5-first=Tomasz |editor6-last=Pahl |editor6-first=Claus |editor7-last=Sikora |editor7-first=Florian |editor8-last=Wong |editor8-first=Prudence W.H. |s2cid=231705141}}</ref> or any sequence thereof.<ref name=":0" /> |
||
For <math>I \subseteq V</math> a subset of the nodes of a graph <math>G</math>, then <math>t(I)</math> the time until an amnesiac flood terminates when started from <math>I</math> is known to obey the following bounds: <math>t(I)=e(I)</math> if <math>G</math> is <math> I</math>-bipartite and <math>e(I)<t(I) \leq e(I)+d(G)+1</math> if it is not, where <math>e(I)</math> is the [[Eccentricity (graph theory)|eccentricity]] of <math>I</math> and <math>d(G)</math> is the [[Diameter (graph theory)|diameter]].<ref name=":1" /> A graph is <math>I</math>-bipartite, if the [[quotient graph]] of <math>G</math> with <math>I</math> contracted to a single node is [[Bipartite graph|bipartite]].<ref name=":1" /> This termination time is optimal for <math>I</math>-bipartite graphs and is asymptotically optimal for single node initialisation on non-bipartite graphs. |
For <math>I \subseteq V</math> a subset of the nodes of a graph <math>G</math>, then <math>t(I)</math> the time until an amnesiac flood terminates when started from <math>I</math> is known to obey the following bounds: <math>t(I)=e(I)</math> if <math>G</math> is <math> I</math>-bipartite and <math>e(I)<t(I) \leq e(I)+d(G)+1</math> if it is not, where <math>e(I)</math> is the [[Eccentricity (graph theory)|eccentricity]] of <math>I</math> and <math>d(G)</math> is the [[Diameter (graph theory)|diameter]].<ref name=":1" /> A graph is <math>I</math>-bipartite, if the [[quotient graph]] of <math>G</math> with <math>I</math> contracted to a single node is [[Bipartite graph|bipartite]].<ref name=":1" /> This termination time is optimal for <math>I</math>-bipartite graphs and is asymptotically optimal for single node initialisation on non-bipartite graphs. |
||
| Line 12: | Line 12: | ||
== Variants of Amnesiac Flooding == |
== Variants of Amnesiac Flooding == |
||
Since its introduction, several variants of and related problems to amnesiac flooding have been studied. For example, a modified variant requiring the initial set to retain their knowledge of this membership and the message for a single round, but always requiring <math>e(I)+1</math> rounds has been proposed.<ref>{{Cite book |last=Turau |first=Volker |date=2020 | |
Since its introduction, several variants of and related problems to amnesiac flooding have been studied. For example, a modified variant requiring the initial set to retain their knowledge of this membership and the message for a single round, but always requiring <math>e(I)+1</math> rounds has been proposed.<ref>{{Cite book |last=Turau |first=Volker |date=2020 |title=Structural Information and Communication Complexity |publisher=Springer International Publishing |isbn=978-3-030-54921-3 |editor-last=Richa |editor-first=Andrea Werneck |series=Lecture Notes in Computer Science |volume=12156 |location=Cham |pages=183–199 |language=en |chapter=Stateless Information Dissemination Algorithms |doi=10.1007/978-3-030-54921-3_11 |editor2-last=Scheideler |editor2-first=Christian |chapter-url=https://link.springer.com/chapter/10.1007/978-3-030-54921-3_11}}</ref> |
||
A dynamic version of amnesiac flooding has been introduced <ref name=":0" /> considering the case where there are multiple different messages in the system and where each node can only send one message per round. This has been shown to terminate in the partial send case (<math>v</math> sends an arbitrary message to its neighbours that didn't send it any message last round) and the ranked-full send case (<math>v</math> sends the highest ranked message <math>m</math> to all of its neighbours that did not send it <math>m</math> last round).<ref name=":0" /> However, the unranked-full send (<math>v</math> sends an arbitrary message <math>m</math> to all of its neighbours that did not send it <math>m</math> last round) does not necessarily terminate without additional stored information (such as the diameter of the graph <ref>{{Cite book |last1=Bayramzadeh |first1=Zahra |
A dynamic version of amnesiac flooding has been introduced <ref name=":0" /> considering the case where there are multiple different messages in the system and where each node can only send one message per round. This has been shown to terminate in the partial send case (<math>v</math> sends an arbitrary message to its neighbours that didn't send it any message last round) and the ranked-full send case (<math>v</math> sends the highest ranked message <math>m</math> to all of its neighbours that did not send it <math>m</math> last round).<ref name=":0" /> However, the unranked-full send (<math>v</math> sends an arbitrary message <math>m</math> to all of its neighbours that did not send it <math>m</math> last round) does not necessarily terminate without additional stored information (such as the diameter of the graph <ref>{{Cite book |last1=Bayramzadeh |first1=Zahra |contribution=Weak Amnesiac Flooding of Multiple Messages |last2=Kshemkalyani |first2=Ajay D. |last3=Molla |first3=Anisur Rahaman |last4=Sharma |first4=Gokarna |date=2021 |title= Networked Systems: 9th International Conference, NETYS 2021, Virtual Event, May 19–21, 2021, Proceedings |publisher=Springer International Publishing |isbn=978-3-030-91014-3 |editor-last=Echihabi |editor-first=Karima |series=Lecture Notes in Computer Science |location=Cham |pages=88–94 |language=en |doi=10.1007/978-3-030-91014-3_6 |editor2-last=Meyer |editor2-first=Roland |s2cid=244818918}}</ref>). |
||
== References == |
== References == |
||
{{reflist}} |
{{reflist}} |
||
[[Category:Flooding algorithms]] |
[[Category:Flooding algorithms]] |
||
{{Improve categories|date=April 2024}} |
|||
[[Category:Distributed algorithms]] |
[[Category:Distributed algorithms]] |
||
Revision as of 04:17, 30 May 2024
In distributed computing amnesic flooding is a stateless distributed flooding algorithm that can be implemented as a broadcast protocol in synchronous distributed networks without the need to store messages or flags between communication rounds.[1] The algorithm is simple:
When a node receives a message, it forwards it to all of its neighbours it did not receive the message from. To initiate a broadcast on a network, a node simply sends the message to all of its neighbours.
The algorithm has been shown to terminate when the message begins at any subset of the network nodes [1][2][3][4] or any sequence thereof.[2]
For a subset of the nodes of a graph , then the time until an amnesiac flood terminates when started from is known to obey the following bounds: if is -bipartite and if it is not, where is the eccentricity of and is the diameter.[1] A graph is -bipartite, if the quotient graph of with contracted to a single node is bipartite.[1] This termination time is optimal for -bipartite graphs and is asymptotically optimal for single node initialisation on non-bipartite graphs.
This termination is robust with respect to the loss of edges and nodes, however it fails with delays on edges or the addition of new edges.[1][2]
Variants of Amnesiac Flooding
Since its introduction, several variants of and related problems to amnesiac flooding have been studied. For example, a modified variant requiring the initial set to retain their knowledge of this membership and the message for a single round, but always requiring rounds has been proposed.[5]
A dynamic version of amnesiac flooding has been introduced [2] considering the case where there are multiple different messages in the system and where each node can only send one message per round. This has been shown to terminate in the partial send case ( sends an arbitrary message to its neighbours that didn't send it any message last round) and the ranked-full send case ( sends the highest ranked message to all of its neighbours that did not send it last round).[2] However, the unranked-full send ( sends an arbitrary message to all of its neighbours that did not send it last round) does not necessarily terminate without additional stored information (such as the diameter of the graph [6]).
References
- ^ a b c d e 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 c d e Hussak, Walter; Trehan, Amitabh (2020-09-12), Terminating cases of flooding, arXiv:2009.05776
- ^ Turau, Volker (2020-07-21), Analysis of Amnesiac Flooding, arXiv:2002.10752
- ^ 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.). 47th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2021, Bolzano-Bozen, Italy, January 25–29, 2021, Proceedings. 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.
- ^ Turau, Volker (2020). "Stateless Information Dissemination Algorithms". In Richa, Andrea Werneck; Scheideler, Christian (eds.). Structural Information and Communication Complexity. 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.
- ^ Bayramzadeh, Zahra; Kshemkalyani, Ajay D.; Molla, Anisur Rahaman; Sharma, Gokarna (2021). "Weak Amnesiac Flooding of Multiple Messages". In Echihabi, Karima; Meyer, Roland (eds.). Networked Systems: 9th International Conference, NETYS 2021, Virtual Event, May 19–21, 2021, Proceedings. 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.