Distributed Systems 2020/21 spring

Seminar 6: Calculate Vector Clock timestamps

Goal: To Understand and Implement the Vector Clock algorithm

Description: A vector clock is an algorithm for generating a partial ordering of events in a distributed system and detecting causality violations.

Definitions:

• The use of Vector clocks is an attempt to move away from the use of a physical clock for measuring ordering of events in a Distributed System. The vector clocks provide a sort of a Logical Clock that assigns a unique id to events in a Distributed System, such that it captures the casual order among events in a Distributed System. The Distributed System can be viewed as a system where series of processes are executed. These Processes communicate with each other via messages.
• The Happens before Relation (<):
  • If a, b are events in the same process, if a occurs before b, then a < b
  • if a denotes sending of message in process-a and b denotes receipt of message in process-b then a < b
  • The relation is transitive, a < b and b < c => a < c
• Why we Need Vector Clocks:
  • The need for vector clocks arise due to the limitations set by Lamport's Logical Clock:
    • Looking at the Lamport's timestamps, we can not detect Casual Relationship in Lamport's logical clock and we can not conclude which events are casually related.
    • Lamport's Logical Clock is a Partial Order of events.
    • Consider the following example:
      • if A -> B, then it is true that TS(A) < TS(B)
      • But if TS(A) < TS(B), then we can not conclude that A -> B (Not true for Concurrent Events)

• As shown in figure - Even though C(e11) < C(e32), we can not say whether e11 happened before e32 or not. In other words, we cannot establish the casual relationship between these two events.
• The solution to this problem is to make use of Vector Clock

• Casuality Relation:
  • It states: If an event e1 possibly influences the generation of event e2, then e1 < e2
  • The better way to establish such a relation is to rely on message-passing among the processes.
  • Message passing establishes a happens before order on events based on the communication pattern.
• Rules for Vector Clocks:
  • Initially, all clocks are set to 0
  • C_i[i] = C_i[i] + 1, for two successive internal events at P_i
  • At Process P_i , C_i[j] = Max(C_i[j], tm[j]), for all processes P_j , where tm is the vector timestamp borne by process m received by process P_i from some other process.

• Comparison of Vector Timestamp Clock values:
  • Equal: T_a = T_b , iff for all processes P_i , T_a[i] = T_b[i]
    • For instance, (2,2,2) = (2,2,2)
  • Not Equal: T_a != T_b , iff T_a[i] != T_b[i] for atleast one P_i
    • For instance, (2,1,2) != (2,2,2)
  • Less than or Equal: T_a {$ \le $} T_b , iff T_a[i] {$ \le $} T_b[i] for all P_i
    • For instance, (2,1,2) {$ \le $} (2,2,2)
  • Less than: T_a < T_b , iff
    • for all P_i , T_a[i] {$ \le $} T_b[i] and
    • there exists atleast one P_i , for which T_a < T_b
    • For instance, (2,1,2) < (2,2,2)
  • Concurrent: T_a || T_b , iff T_a !< T_b and T_b !< T_a
    • For instance, (2,3,2) || (3,1,2)
• EXERCISE:
  • Consider Figure below that shows five processes (p0, p1, p2, p3, p4) with local events and message passing events labelled as 1, 2, 3, 4 and so on to 59. Assume that the initial clock values are all initialized to 0, calculate the Vector Clock timestamps for each labelled event.

Deliverables of practical session: A PDF file containing the answers to above exercise.