Flooding algorithm

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.

Pseudocode

Note: All nodes are not informed at the beginning.

Initiator

Informed: = true;   send to all neighbors A node K receives from a neighbor N

If K is not informed, then        informed: = true;        send to all neighbors except N message complexity

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.

Example:

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

Improvements

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.

  • Algorithm
  • Distributed system
338235
de