Wave Algorithm

Message Passing Schemes (Algorithms) are called wave algorithms in means asynchronous message passing no global clock or time.

A wave algorithm exchanges finite number of messages and then makes a decision which depends casually on some event in each process.

An Algorithm that satisfies the three requirements is considered as a Wave Algorithm in a distributed algorithm:

• Termination: Each computation is finite.
  • ∀C : lC| < ∞
• Decision: Each computation contains at least one decision event.
  • ∀C: ∃e ∈ C: e is a decisive event.
• Dependence: In each computation, each decided event is casually preceded by an event in each process.
  • ∀C: ∀e ∈ C : (e is a decide event ⇒ ∀q ∈ P’ ∃f ∈C_q: f ≥ e).

A wave algorithm starts from a particular process and the wave propagates to its neighbors, and neighbors propagate to their neighbors, and so on. When there are no further nodes to propagate wave returns back.

The strength of the Wave Algorithm lies in the asynchronous Communication where there is an equivalence lies between the casual and message chains. In wave algorithms, the existence of message chains is required for the computation of causal dependency. Wave algorithms can differ from each other on the basis of the following properties:

• Centralization: algorithm differs from each other if they have one initiator or more than one initiator.
  • An algorithm has exactly one initiator in each computation is called centralized,
  • If the algorithm can be started spontaneously by an arbitrary subset of the processes called decentralized.
• Initial Knowledge: An algorithm differs from one another if they have initial knowledge in the processes.
  • Process Identity: Each process has its unique name.
  • Neighbor Identity: Each process knows his neighbor’s name.
• Complexity: The complexity of the algorithm considers
  • the number of exchanged messages
  • the number of exchanged bits,
  • the time needed for one computation.
• Topology: An algorithm may be designed for a specific topology such as ring, tree, clique, etc.
• Number of decisions: Normally one decision occurs in each process. In some algorithms only one process may execute decide event whereas in some algorithms all processes decide. The tree algorithm cause a decision in exactly two processes.

Properties of waves:

• Each event in computation is preceded by an event in an initiator.
• A wave algorithm for arbitrary networks without initial knowledge of the neighbor’s identities. Then algorithm exchanges at least lEI messages in each computation.

Since propagation of packets is done by the wave network of nodes and it can be treated as partial order relation, 

Now, Consider a binary relation ≤_* by x ≤_* y ⇐⇒ (x * y) = x, i.e.; in the relation ≤* is a partial order on X, i.e., that this relation is transitive, antisymmetric, and reflexive.

• Transitivity:  We know x≤ y and y≤ z then x≤ z, Assume x ≤_* y and y ≤_* z; by definition of ≤_*, (x*y) = x and (y*z) = y. Using these and associativity we find (x * z) = (x * y) * z = x * (y * z) = x * y = x, i.e., x ≤_* z.
• Antisymmetry: Assume x ≤_* y and y ≤_* x; by definition of ≤_*, x * y = x and y * x = y. Using these and commutativity we find x = y.
• Reflexivity:  x * x = x, i.e., x ≤_* x, the reflexive property can be proved using idempotency.

Since it satisfies all three properties hence we conclude wave algorithm can be treated as the Partial order relation.

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.