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
S.No. |
Algorithm |
Topology |
Centralized(C)/ Decentralized(D) |
Traversing |
Message Complexity(M) |
Time Complexity |
---|---|---|---|---|---|---|
01. |
Ring |
ring |
C |
no |
N |
N |
02. |
Tree |
tree |
D |
no |
N |
O(D) |
03. |
Echo |
arbitrary |
C |
no |
2|E| |
O(N) |
04. |
Polling |
clique |
C |
no |
2N-2 |
2 |
05. |
Finn |
arbitrary |
D |
no |
<=4.N.|E| |
O(D) |
06. |
Sequence Polling |
clique |
C |
yes |
2N-2 |
2N-2 |
07. |
Classical DFS |
arbitrary |
C |
yes |
2|E| |
2|E| |
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.
Contact Us