Amnesiac flooding

Last updated July 29, 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] or any sequence thereof.^[4]

For $I\subseteq V$ a subset of the nodes of a graph $G$ , then $t(I)$ the time until an amnesiac flood terminates when started from $I$ is known to obey the following bounds: $t(I)=e(I)$ if $G$ is $I$ -bipartite and $e(I)<t(I)\leq e(I)+d(G)+1$ if it is not, where $e(I)$ is the eccentricity of $I$ and $d(G)$ is the diameter.^[1] A graph is $I$ -bipartite, if the quotient graph of $G$ with $I$ contracted to a single node is bipartite.^[1] This termination time is optimal for $I$ -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 $e(I)+1$ rounds has been proposed.^[5]

A dynamic version of amnesiac flooding has been introduced ^[4] 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 ( $v$ sends an arbitrary message to its neighbours that didn't send it any message last round) and the ranked-full send case ( $v$ sends the highest ranked message $m$ to all of its neighbours that did not send it $m$ last round).^[4] However, the unranked-full send ( $v$ sends an arbitrary message $m$ to all of its neighbours that did not send it $m$ last round) does not necessarily terminate without additional stored information (such as the diameter of the graph ^[6]).

Related Research Articles

The Ford–Fulkerson method or Ford–Fulkerson algorithm (FFA) is a greedy algorithm that computes the maximum flow in a flow network. It is sometimes called a "method" instead of an "algorithm" as the approach to finding augmenting paths in a residual graph is not fully specified or it is specified in several implementations with different running times. It was published in 1956 by L. R. Ford Jr. and D. R. Fulkerson. The name "Ford–Fulkerson" is often also used for the Edmonds–Karp algorithm, which is a fully defined implementation of the Ford–Fulkerson method.

<span class="mw-page-title-main">Breadth-first search</span> Algorithm to search the nodes of a graph

Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next depth level. Extra memory, usually a queue, is needed to keep track of the child nodes that were encountered but not yet explored.

<span class="mw-page-title-main">Hypergraph</span> Generalization of graph theory

In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices.

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets $and, that is, every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.$

In optimization theory, maximum flow problems involve finding a feasible flow through a flow network that obtains the maximum possible flow rate.

In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge (u,v) from vertex u to vertex v, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks. Precisely, a topological sort is a graph traversal in which each node v is visited only after all its dependencies are visited. A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG). Any DAG has at least one topological ordering, and algorithms are known for constructing a topological ordering of any DAG in linear time. Topological sorting has many applications, especially in ranking problems such as feedback arc set. Topological sorting is possible even when the DAG has disconnected components.

In combinatorial mathematics, the Prüfer sequence of a labeled tree is a unique sequence associated with the tree. The sequence for a tree on n vertices has length n − 2, and can be generated by a simple iterative algorithm. Prüfer sequences were first used by Heinz Prüfer to prove Cayley's formula in 1918.

In graph theory, a domatic partition of a graph $is a partition of into disjoint sets,,..., such that each V i is a dominating set for G . The figure on the right shows a domatic partition of a graph; here the dominating set consists of the yellow vertices, consists of the green vertices, and consists of the blue vertices.$

<span class="mw-page-title-main">Maximal independent set</span> Independent set which is not a subset of any other independent set

In graph theory, a maximal independent set (MIS) or maximal stable set is an independent set that is not a subset of any other independent set. In other words, there is no vertex outside the independent set that may join it because it is maximal with respect to the independent set property.

In mathematical optimization, the push–relabel algorithm is an algorithm for computing maximum flows in a flow network. The name "push–relabel" comes from the two basic operations used in the algorithm. Throughout its execution, the algorithm maintains a "preflow" and gradually converts it into a maximum flow by moving flow locally between neighboring nodes using push operations under the guidance of an admissible network maintained by relabel operations. In comparison, the Ford–Fulkerson algorithm performs global augmentations that send flow following paths from the source all the way to the sink.

In computer science, the Hopcroft–Karp algorithm is an algorithm that takes a bipartite graph as input and produces a maximum-cardinality matching as output — a set of as many edges as possible with the property that no two edges share an endpoint. It runs in $time in the worst case, where is set of edges in the graph, is set of vertices of the graph, and it is assumed that . In the case of dense graphs the time bound becomes, and for sparse random graphs it runs in time with high probability.$

The distributed minimum spanning tree (MST) problem involves the construction of a minimum spanning tree by a distributed algorithm, in a network where nodes communicate by message passing. It is radically different from the classical sequential problem, although the most basic approach resembles Borůvka's algorithm. One important application of this problem is to find a tree that can be used for broadcasting. In particular, if the cost for a message to pass through an edge in a graph is significant, an MST can minimize the total cost for a source process to communicate with all the other processes in the network.

In distributed computing, leader election is the process of designating a single process as the organizer of some task distributed among several computers (nodes). Before the task has begun, all network nodes are either unaware which node will serve as the "leader" of the task, or unable to communicate with the current coordinator. After a leader election algorithm has been run, however, each node throughout the network recognizes a particular, unique node as the task leader.

<span class="mw-page-title-main">Maximum cut</span> Problem of finding a maximum cut in a graph

In a graph, a maximum cut is a cut whose size is at least the size of any other cut. That is, it is a partition of the graph's vertices into two complementary sets $S$ and $T$ , such that the number of edges between $S$ and $T$ is as large as possible. Finding such a cut is known as the max-cut problem.

In the mathematical fields of graph theory and combinatorial optimization, the bipartite dimension or biclique cover number of a graph G = (V, E) is the minimum number of bicliques (that is complete bipartite subgraphs), needed to cover all edges in E. A collection of bicliques covering all edges in G is called a biclique edge cover, or sometimes biclique cover. The bipartite dimension of G is often denoted by the symbol d(G).

David Bernard Shmoys is a Professor in the School of Operations Research and Information Engineering and the Department of Computer Science at Cornell University. He obtained his Ph.D. from the University of California, Berkeley in 1984. His major focus has been in the design and analysis of algorithms for discrete optimization problems.

In mathematics and computer science, graph edit distance (GED) is a measure of similarity between two graphs. The concept of graph edit distance was first formalized mathematically by Alberto Sanfeliu and King-Sun Fu in 1983. A major application of graph edit distance is in inexact graph matching, such as error-tolerant pattern recognition in machine learning.

Yo-Yo is a distributed algorithm aimed at minimum finding and leader election in generic connected undirected graph. Unlike Mega-Merger it has a trivial termination and cost analysis.

In graph theory, an odd cycle transversal of an undirected graph is a set of vertices of the graph that has a nonempty intersection with every odd cycle in the graph. Removing the vertices of an odd cycle transversal from a graph leaves a bipartite graph as the remaining induced subgraph.

DSatur is a graph colouring algorithm put forward by Daniel Brélaz in 1979. Similarly to the greedy colouring algorithm, DSatur colours the vertices of a graph one after another, adding a previously unused colour when needed. Once a new vertex has been coloured, the algorithm determines which of the remaining uncoloured vertices has the highest number of colours in its neighbourhood and colours this vertex next. Brélaz defines this number as the degree of saturation of a given vertex. The contraction of the term "degree of saturation" forms the name of the algorithm. DSatur is a heuristic graph colouring algorithm, yet produces exact results for bipartite, cycle, and wheel graphs. DSatur has also been referred to as saturation LF in the literature.

References

1 2 3 4 5 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.
1 2 Hussak, Walter; Trehan, Amitabh (2020). "On the Termination of Flooding". In Paul, Christophe; Bläser, Markus (eds.). 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, March 10-13, 2020, Montpellier, France. LIPIcs. Vol. 154. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. pp. 17:1–17:13. doi: 10.4230/LIPICS.STACS.2020.17 .
↑ 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.
1 2 3 Hussak, Walter; Trehan, Amitabh (2020-09-12), Terminating cases of flooding, arXiv: 2009.05776
↑ 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.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[:1-1] 1 2 3 4 5 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.

[:0-2] 1 2 Hussak, Walter; Trehan, Amitabh (2020). "On the Termination of Flooding". In Paul, Christophe; Bläser, Markus (eds.). 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, March 10-13, 2020, Montpellier, France. LIPIcs. Vol. 154. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. pp. 17:1–17:13. doi: 10.4230/LIPICS.STACS.2020.17 .

[3] 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.

[:2-4] 1 2 3 Hussak, Walter; Trehan, Amitabh (2020-09-12), Terminating cases of flooding, arXiv: 2009.05776

[5] 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.

[6] 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.

[1]

[2]

[3]

[4]

[5]

[6]