Different Wave Algorithm
- Ring algorithm
- Polling algorithm
- Tree algorithm
- Echo algorithm
- Phase algorithm
- Finn’s algorithm
The Ring Algorithm
The channel for the propagation of the process is selected such that it forms a Hamiltonian cycle(all the nodes traversed). In other words, the process (p) and its neighbor (Nextp) is given such that channels selected in this way form a Hamiltonian cycle(all the nodes traversed).
- It has only one initiator.
- Each other node passes the message forward.
- Ring Algorithm is Centralized.
- The initiator is the deciding node.
For initiator-
begin
send (tok) to Nextp;
receive (tok);
decide;
end
Ring algorithm for non initiator-
begin
receive (tok);
send (tok) to Nextp;
end
The Polling Algorithm
The algorithm will send out a wave that will reach all the nodes and will come back to the originator and when the wave is subsided then the algorithm will terminate.
- It works on a clique network.
- It has only one initiator.
- Polling Algorithm is Centralized.
- The initiator is the deciding node.
In the polling algorithm, the initiator asks each neighbor to reply with a message and decides after receipt of all messages.
Polling algorithm for Initiator-
var recp: integer init 0;
begin
for all q Neighp
do send (tok)to qf;
while recp<#Neighp do
begin
receive(tok);
recp:= recp + 1;
end
decide
end
// here recp is used as a count variable
Polling algorithm for non Initiator-
begin
receive (tok)from qf;
send (tok) to q;
end
Polling can also be used in a star network in which the initiator is the center.
Note: Wave Algorithm used for all of the fundamental tasks i.e., broadcasting, synchronization, and computing global functions.
The Tree Algorithm
Characteristics of algorithm are as follows:
- Non centralized wave algorithm for (1) tree network (2) arbitrary network if a spanning tree is available.
- If a process has received a message via each of incident channel except one, the process sends a message via remaining channel.
- More than one process may decide.
- The tree algorithm causes a decision in exactly two process.
Tree Algorithm:
Boolean rec {q} for each q ϵ Neigh
Begin while ≠ {q: recp {q} is false > 1 do
Begin receive <tok> from q : recp [q] = true
End
Send <tok> to q0
Receive <tok> from q0
Recp [q0] = true decide
For all q . Neigh send <tok> to q
End
Example:
In the tree network shown, there are two process that receives a message via each of their channel and decide. The other processes are still waiting for message with their program counter pointing at x in the terminal configuration.
we get rec1(12) = True; rec5(6) = true; rec3(4) = true; rec9(7) = true; rec9(8) = true; rec10(12) = true; rec11(12) = true;
Because the node 1,3,5,7,8,10,11 are terminal node
rec13(12) = true because node 12 sends a message to node 13(as it has received a message via each of its incident channels except one that is (13). Node receives message from each of its incident channel (2,4,6,9) except 13.
The Echo Algorithm
The characteristics of this algorithm are:
- Centralized wave algorithm for network of arbitrary topology.
- First notice that wave with one initiator defines as spanning tree take the parent channel to be one through which the first message is received.
- Initiator send the message to all its neighbor
- Upon receipt of the first message a non-initiative forward message to all its Neighbour except the one from which the message was received.
- When the initiator has received echo message from all its Neighbour it decides.
Echo algorithm for initiator:
Begin for all q.neigh do
Send <tok> to q;
While receivesp < Neighp do
Begin receives <tok> ; recp = recp+1 end;
End
Decide
End
Echo algorithm for non-initiators:
Begin receives <tok> from neighbour q ;
Father = q
recp = recp + 1
for all q ϵ neighp : q ≭ fatherp do
Send <tok> to q
While recp < ≭ Neighp do
Begin receives <tok>p
recp = recp + 1
End
Send <tok> to fatherp
End
The Phase Algorithm
It is a decentralized algorithm for network of arbitrary topology.
This can be used as wave algorithm for directed networks.
The algorithm requires that the process know the diameter D of the network.
The algorithm is also correct if the process uses instead of D, a constant D larger than the network diameter. Thus, in order to apply this algorithm, it is not necessary that diameter is known exactly, it suffices if the upper (i.e., N-1) on the network diameter is known.
As it can be used in arbitrary, directed networks where channels can carry messages in one direction only, the Neighbours of node p are:
- In-Neighbor : Process that can send message to p
- Out-Neighbor : Process to which p can send messages
In phase algorithm, each process sends exactly D messages to each out-neighbor. Only after I messages have been received from each in-neighbor,(I + 1)th message is sent to each out-neighbor.
The Finn’s Algorithm
This is another wave algorithm that can be used in arbitrary directed networks.
It does not require the diameter of the network to be known in advance but relieve on the availability of the unique identities for the processes.
Set of processes identities are exchanged in messages, which causes the bit complexity of the algorithm to be rather high.
Process p maintains two set of process identities:
- Incp : Is the set of processes q such that an event in q precedes the most recent event in p.
- Nincp : Is the set of processes q such that for all neighbors r of q an event in precedes the most recent event in p.
Wave and Traversal Algorithm in Distributed System
As we know a distributed system is a collection where different processes in order to perform a task communicate with each other. In wave algorithm exchange of messages and decision take place, which depends on the number of messages in each event of a process. As it is important to traverse in a connected network Wave algorithm has applications in many fields such as Distributed Databases, Wireless Networks, etc.