Traversal Algorithm

Wave algorithms have the following two additional properties:

• the initiator is the only process that decides
• all events are ordered totally by the participant in cause-effect order.

Wave algorithms with these properties are called traversal algorithms. or Traversal Algorithm if it satisfies these properties:

• In each computation, there is one initiator, which starts the algorithm by sending out exactly one message.
• A process, upon receipt of a message, either sends out one message or decides.
• Each process has sent a message at least once, then the algorithm terminates in the initiator.

Example of Traversing Algorithm:

Sequential Polling Algorithm: Sequence Polling Algorithm is the same as Polling Algorithm.

• One neighbor is polled at a time.
• The next neighbor is polled only when the reply of a previous neighbor is received.

Sequential Polling algorithm for Initiator-
var recp: integer init 0;
begin
     while recp<#Neighp do
          begin
               send(tok)to qrecp+1;
               receive(tok);
               recp:= recp + 1;
          end;
      decide
    end

Sequential Polling algorithm for non Initiator-
begin
     receive (tok)from q;
     send (tok) to q;
end

Note: Traversal Algorithms are used to construct Election Algorithms.

Topology

• Ring: It is a circular network structure where each network is connected with exactly two networks.
• Tree: It is a type of hierarchical topology where the root network is connected to all other networks and there is a minimum of three levels of hierarchy.
• Clique: Network channel is present between each pair of processes.

The metrics for measuring the efficiency of algorithms are:

• Time complexity is the number of messages in the longest chain.
• Message complexity is the number of messages carried out by an algorithm.

Here is a table showing different algorithms with their properties:

• N is the number of processes
• lEI the number of channels
• D the diameter of the network (in hops).
• DFS – Depth First Search

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.