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 (Next_p) 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:

• Inc_p : Is the set of processes q such that an event in q precedes the most recent event in p.
• Ninc_p : Is the set of processes q such that for all neighbors r of q an event in precedes the most recent event in p.

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.