Flooding ( German: flood ) and flood algorithm is the simplest algorithm for distributing information in a distributed system. Requirement is only a coherent topology. In a network of initially uninformed nodes send one or more initiator node a message to all their neighbors. A node that receives the message and has not previously been informed, the message also sends to all its neighbors, and not returned to the sender. After a while all nodes are informed. As informed nodes send any more messages, the algorithm terminates.
Note: All nodes are not informed at the beginning.
Informed: = true;
If K is not informed, then
informed: = true;
Let E be the number of edges and k is the number of nodes. Each node must send to each neighbor its message. So go over each edge 2 News (2e ). However, all email except the initiator to the neighbor from which it received the message ( source ), no message back (-k ). An exception is the initiator who sends the message to all nodes in the network ( 1). There are thus dispatched to an initiator 2e -k 1 messages.
In a network with 5 nodes (A, B, C, D, E), there are 10 edges.
- A has four 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 to already counted three edges A, B, C.
This gives 10 edges.
Equation: 2e -k 1 = 2 * 10-5 1 = 16 messages would be sent.
At least in Fully - Connected Networks, the number of messages, you can also just about the number of nodes determined: k ² -2k 1 = 25-10 1 = 16 News
Flooding with confirmation
One problem with the normal Floodings is that the initiator does not recognize that all nodes have received a message. One solution to this problem is the flooding with confirmation.
Here, a process sends off a confirmation when it has received from all neighbors or child nodes to which it has sent a message, a confirmation. Also, a node sends a confirmation from when he got a message, but this can not end, because he has no more neighbors. The initiator knows that all have received a message when it has received from all its neighbors confirmations.
- Distributed system