Flooding algorithm
Overview
 
A flooding algorithm is an algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

 for distributing material to every part of a connected network
Computer network
A computer network, often simply referred to as a network, is a collection of hardware components and computers interconnected by communication channels that allow sharing of resources and information....

. The name derives from the concept of inundation by a flood
Flood
A flood is an overflow of an expanse of water that submerges land. The EU Floods directive defines a flood as a temporary covering by water of land not normally covered by water...

.

Flooding algorithms are used in systems such as Usenet
Usenet
Usenet is a worldwide distributed Internet discussion system. It developed from the general purpose UUCP architecture of the same name.Duke University graduate students Tom Truscott and Jim Ellis conceived the idea in 1979 and it was established in 1980...

 and peer-to-peer
Peer-to-peer
Peer-to-peer computing or networking is a distributed application architecture that partitions tasks or workloads among peers. Peers are equally privileged, equipotent participants in the application...

 file sharing systems and as part of some routing protocol
Routing protocol
A routing protocol is a protocol that specifies how routers communicate with each other, disseminating information that enables them to select routes between any two nodes on a computer network, the choice of the route being done by routing algorithms. Each router has a priori knowledge only of...

s, including OSPF
Open Shortest Path First
Open Shortest Path First is an adaptive routing protocol for Internet Protocol networks. It uses a link state routing algorithm and falls into the group of interior routing protocols, operating within a single autonomous system . It is defined as OSPF Version 2 in RFC 2328 for IPv4...

, DVMRP, and those used in ad-hoc wireless networks.

There are several variants of flooding algorithm: most work roughly as follows.
  1. Each node acts as both a transmitter and a receiver.
  2. Each node tries to forward every message to every one of its neighbors except the source node.

This results in every message eventually being delivered to all reachable parts of the network.

Real-world flooding algorithms have to be 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.

Flooding algorithms are also useful for solving many mathematical problems, including maze
Maze
A maze is a tour puzzle in the form of a complex branching passage through which the solver must find a route. In everyday speech, both maze and labyrinth denote a complex and confusing series of pathways, but technically the maze is distinguished from the labyrinth, as the labyrinth has a single...

 problems and many problems in graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

.
There are several disadvantages with this approach to routing.
 
x
OK