Vector Clocks

Question 1

What is a Vector Clock?

Answer 1

A vector clock for a system of N processes is an array of N integers

Question 2

How does a Vector clock work?

Answer 2

Each process keeps its own vector clock Vi, which it uses to timestamp local events.

Processes then attach vector timestamps on the messages they send to one another

Question 3

State the Rule for updating vector clocks: VC1

Answer 3

VC1: Initially, Vi[j] = 0 for i, j = 1, 2, …, N

Question 4

State the Rule for updating vector clocks: VC2

Answer 4

VC2: Just before pi

timestamps an event, its sets Vi[i] = Vi[i] + 1

Question 5

State the Rule for updating vector clocks: VC3

Answer 5

VC3: pi includes the value t = Vi in every message it sends

Question 6

State the Rule for updating vector clocks: VC4

Answer 6

VC4: When pi receives a timestamp in a message,it sets Vi[j] = max(Vi[j], t[j]) for j = 1, 2, …, N

Question 7

What is Vi[i]

Answer 7

Vi[i] is the number of events that pi has timestamped

Question 8

What is Vi[j]

Answer 8

Vi[j] for j ≠ i is the number of events that have occurred at pj that potentially have affected pi

Question 9

How can vector timestamps be compared?

Answer 9

♦ V = V’  V[j] = V’[j] for j = 1, 2, …, N
♦ V ≤ V’  V[j] ≤ V’[j] for j = 1, 2, …, N
♦ V < V’  V ≤ V’ and V ≠ V’

Question 10

Give an advantage of Vector clocks

Answer 10

Allows causal ordering for all events in the system

Question 11

Give a disadvantage of Vector clocks

Answer 11

storage and message overhead proportional to N, the number of processes