## 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**

- If
**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)

- if

- Looking at the Lamport's timestamps, we can not detect

- The need for vector clocks arise due to the limitations set by

- 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
on events based on the communication pattern.*happens before order*

- It states:
**Rules for Vector Clocks:**- Initially, all clocks are set to
**0** , for two successive internal events at*C*_{i}[i] = C_{i}[i] + 1**P**_{i}- At Process
**P**,_{i}, for all processes*C*_{i}[j] = Max(C_{i}[j], tm[j])**P**, where_{j}**tm**is the vector timestamp borne by process**m**received by process**P**from some other process._{i}

- Initially, all clocks are set to

**Comparison of Vector Timestamp Clock values:****Equal:****T**, iff for all processes_{a}= T_{b}**P**,_{i}*T*_{a}[i] = T_{b}[i]- For instance, (2,2,2) = (2,2,2)

**Not Equal:****T**, iff_{a}!= T_{b}for atleast one*T*_{a}[i] != T_{b}[i]**P**_{i}- For instance, (2,1,2) != (2,2,2)

**Less than or Equal:****T**, iff_{a}{$ \le $} T_{b}for all*T*_{a}[i] {$ \le $} T_{b}[i]**P**_{i}- For instance, (2,1,2) {$ \le $} (2,2,2)

**Less than:****T**, iff_{a}< T_{b}- for all
**P**,_{i}and*T*_{a}[i] {$ \le $} T_{b}[i] - there exists atleast one
**P**, for which_{i}**T**_{a}< T_{b} - For instance, (2,1,2) < (2,2,2)

- for all
**Concurrent:****T**, iff_{a}|| T_{b}**T**and_{a}!< T_{b}**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.**