Flooding algorithm

from Wikipedia, the free encyclopedia
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.


Note: All nodes are initially not informed.


 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.


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


Flooding with confirmation

Flooding algorithm with confirmations

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.