Flooding algorithm: Difference between revisions

Revision as of 10:37, 30 March 2003

Revision as of 10:43, 30 March 2003

Line 1:

A '''flooding algorithm''' is a method for distributing material to every part of a connected system. The name derives from the concept of inundation by a [[flood]].

There are several variants of flooding algorithms: the one used on [[Usenet]] works as follows. Each node acts as both a transmitter and a receiver. Each node tries to forward every message to every one of its neighbors. This results in every message eventually being delivered to all reachable neighbors.

The actual algorithm is more complex than this, since precautions have to be taken to avoid wasted duplicate deliveries and infinite loops, and to allow messages to eventually expire from the system.

As a transmitter:

See also:

For each piece of information stored locally:

* [[Bellman flooding algorithm]]

:For each neighbor:

::If the piece of information is not marked as being delivered to you via that neighbor:

:::Check with them if they have it, and deliver it if they have not.

As a receiver:

For each transfer attempt from a neighbor:

:If already recieved, decline delivery

:Otherwise, receive, and mark as having been delivered from that neighbor.