Lamport Clocks

Summary

• Lamport’s Logical Clock
• Lamport’s Total Order
• Distributed Mutual Exclusion Lock Algorithm
• Lamport’s Physical Clock
• IPC Time and Clock Drift

Lamport’s Logical Clock

Each node knows:

• its own events
• its own communication events

Lamport’s Logical Clock

• Monotonic increasing set of own event times
  • condition 1: $C_i(a) < C_i(b)$
• Message receipt time greater than send time
  • condition 2: $C_i(a) < C_j(d)$
    • Choose $C_j(d) = Max(C_i(a)\text{++}, C_j)$
• Timestamp of concurrent events
  • arbitrary time stamps

$C(x) < C(y) \nRightarrow x \rightarrow y$

Above is only true on single processor, or when x is a send event and y is the corresponding recv event

Lamport’s clocks only give partial order

Lamport’s Total Order

Condition for $\Rightarrow$

• $a \Rightarrow b \iff C_i(a) < C_j(b) \text{ or } (C_i(a) = C_j(b) \text{ and } P_i \ll P_j)$
  • $\ll =$ arbitrary “well-known” condition to break a tie

No single total order

Distributed Mutual Exclusion Lock Algorithm

To request a lock:

• Send a message to all other nodes
  • Lock Request: Timestamp
• Nodes put request in its queue
  • Priority queue based on timestamp
• Acknowledge requsts to peers

Tie goes to lower node number

I only have the lock when:

• Its at the top of my queue
• Has been ACKed by others
  • Or all the lock requests are later than mine

To release a lock:

• Sends unlock message
• Peers remove completed request from queue

Correctness?

• Messages arrive in order
• No message loss
• Queue’s totally ordered
  • Lamport’s logical clock + pid tie breaker

Deferring ACKs if my req precedes yours

• Combine with unlock means going from 3(N-1) to 2(N-1)

Lamport’s Physical Clock

$$a \mapsto b \implies C_i(a) < C_j(b)$$

Physical clock conditions:

• PC1 (bound on individual clock drift)
  • $(\frac{dC_i(t)}{dt}-1) < k \forall i; (k \ll 1)$
• PC2 (bound on mutual drift)
  • $\forall i,j: C_i(t) - C_j(t) < \epsilon$

IPC Time and Clock Drift

let $\mu$ be lower bound on IPC

To avoid anomalies if $a \text{ on } P_i \mapsto b \text{ on } P_j$

1. $C_i(t + \mu) - C_j(t) > 0$
2. $C_i(t + \mu) - C_i(t) > \mu(1-k)$

Using 1 and 2 and bound by $\epsilon$ on mutual drift, $\mu >= \frac{\epsilon}{1-k}$ to avoid anomalies