Flooding algorithm
Flooding (German: fluten ) or flood algorithm is the simplest algorithm for information distribution in a distributed system . The only requirement is a coherent topology . In a network of initially uninformed nodes, one or more initiator nodes send a message to all of their neighbors. A node that receives the message and has not yet been informed also sends the message to all of its neighbors, but not back to the sender. After a while, all nodes are informed. Since informed nodes do not send any further messages, the algorithm terminates.
Pseudocode
Note: All nodes are initially not informed.
initiator
informiert := true; sende <nachricht> an alle Nachbarn
A node K receives <message> from a neighbor N
wenn K nicht informiert ist, dann
informiert := true;
sende <nachricht> an alle Nachbarn außer N
Message complexity
As a rule, the network of participants does not have a tree structure (as in the adjacent figures), but is meshed. Let e be the number of edges and k the number of nodes. Every node has to send its message to every neighbor. So 2 messages (2e) go over each edge, 1 in each direction. However, except for the initiator, none of them send back a message (-k) to the neighbor from whom they received the message (source). An exception is the initiator who sends the message to all nodes in the network (+1). With an initiator 2e-k + 1 messages are sent.
Example:
In a network with 5 nodes (A, B, C, D, E) there are 10 edges.
- A has 4 edges with B, C, D and E.
- B has 3 (uncounted) edges with C, D, E and to the already counted edge A.
- C has 2 (uncounted) edges to D, E and to already counted edges A, B.
- D has 1 (uncounted) edge to E and 3 to already counted edges A, B, C.
That makes 10 edges.
Equation: 2e-k + 1 = 2 * 10-5 + 1 = 16 messages would be sent.
At least with fully connected networks, the number of messages can only be determined from the number of nodes: k²-2k + 1 = 25-10 + 1 = 16 messages
Improvements
Flooding with confirmation
A problem with normal flooding is that the initiator does not recognize that all nodes have received its message. One solution to this problem is flooding with confirmation.
A process sends a confirmation when it has received a confirmation from all neighbors or child nodes to which it has sent a message. A node also sends a confirmation when it has already been informed or has received a message but cannot forward it because it no longer has any neighbors. The initiator knows that everyone has received a message when he has received confirmations from all of his neighbors. One problem with this binary feedback ("all received") is that non-responding nodes at higher levels gain a disproportionate influence in the sense of "not received". This can be countered in that instead of a yes / no response after a specified time (or a specified repetition interval), a response is given as to how many subnodes have reported back.