Total Algorithm
A total algorithm is a distributed algorithm where the participation of all nodes or processes in the network is required before a decision can be taken. It is sometimes also named wave algorithm. A special form of total algorithm is a traversal algorithm where all events of a wave a strictly ordered by a causality relation and in which the last event occurs in the same process as the first event, namely in the initiator node.
Total algorithms and wave algorithms can be considered as distributed algorithms initiated by a single event where the participation of all processes in the network is required before a particular final event, often a decision, takes place. In wave algorithms and related flooding techniques a node sends new information to all of its neighbors. The activity spreads like a wave or a controlled chain-reaction through the network, and all nodes are visited until the decision can take place and the algorithm is finally terminated. They can be used to spread and disseminate information in a distributed system, to calculate the topology of a network, or to collect and gather information in a distributed system.
Examples for a total algorithm are the
In order to reach all nodes of a system, the algorithm has to broadcast the corresponding information through the whole system. Often this is done in a first phase. There are two possibilities to
- Flooding: a node receiving data sends it immediately to all its neighbors by broadcasting
- Gossiping: a node selects from time to time randomly one of its neighbors to send the data
Both result in an epidemic spread of information. Gossiping is of course much slower than flooding. Flooding leads to an ordered wave, whereas gossiping leads to disordered epidemic spread of information.
