Distributed Computing Wikiclass | Tutorial / Time in Distributed Systems

A Distributed Computing Tutorial by Steven Choy

Question 1: Lamport’s Timestamp

Write the Lamport’s Timestamp for the following events.

Question 2: Vector Timestamp

Write the Vector Clock for the following events.

The simple rules for updating the vector clocks:
- Initially, V_i[j] = 0 for i, j = 1, 2..., N
- Just before p_i timestamps an event, it sets V_i[i] := V_i[i] + 1
- p_i includes the value t = V_i in every message it sends
- When p_i receives a timestamp t in a message, it sets V_i[j] := max(V_i[j], t[j]), for j = 1, 2...,N. Taking the component-wise maximum of two vector timestamps in this way is known as a merge operation.

Question 3: Logical time in distributed systems

Consider a system of four processes (A, B, C, and D) to be synchronized using Lamport’s logical clocks. Assume that the sending and receiving of messages are the only events to be counted. The following events are then occurred:

1. B sends M1 to C.

2. Before receiving M1, C sends M2 to A.

3. After receiving M1, C sends M3 to D.

4. After receiving M2, A sends M4 to D.

5. D receives M3 followed by M4.

6. After receiving M4, D sends M5 to B.

7. After sending M5, D sends M6 to C.

8. C receives M6, and then sends M7 to B.

9. B receives M7 followed by M5.

The following summarizes the events to be counted for each process in order of occurrence:

Process A: receive M2, send M4

Process B: send M1, receive M7, receive M5

Process C: send M2, receive M1, send M3, receive M6, send M7

Process D: receive M3, receive M4, send M5, send M6

(a) Give the timestamps for each of the seven messages.

(b) Give the timestamps for each message if vector clocks are used.

(d) * Identify any causality problem.

(e) * How do you detect the causality problem using the vector timestamps?

Extra Materials

Suggested answers are available here.