Time In Distributed Systems

Required Reading:

• Logical Time: A Way to Capture Causality in Distributed Systems.

Optional Reading:

• Time, Clocks and The Ordering of Events in Distributed Systems

Summary

• Why do we need time?
• Why is measuring time hard in DS?
• Logical Time
• Common Notations
  • Events
• Concurrent Events
• Lamport’s Scalar Clock
  • Clock Rules
• Vector Clock
• Matrix Clock

Why do we need time?

Ordering:

• is easy in local systems
• helps us decide causality
• allows scheduling fairness and SLOs

Why is measuring time hard in DS?

It’s impossible to know how long network traffic will take

Node clocks are not gauranteed to be synchronized

No gaurantees there won’t be failures

Logical Time

Virtual time measured virtual clocks

• Generate time stamps
• Advance
• Can be used for ordering

Logical Clock can be thought of as a generator of timestamps.

• Scalar (Lamport’s) clocks
  • process has knowledge of total number of events
• Vector clocks
  • process has knowledge of how many events occured on which process
• Matrix clocks
  • process has knowledge of which processes have knowledge about how many events occured at each process
  • kind of like read-receipts

… if an event a causally affects an event b, then the timestamp of a must be smaller than the timestamp of b. [Logical Time]

$e_1 \rightarrow e_2 \Rightarrow C(e_1) < C(e_2)$

Common Notations

$p_i$ generates events $e_i^0, e_i^1, \dots, e_i^k, e_i^{k+1}, \dots, e_i^n$

$e_i^k \rightarrow e_i^{k+1}$

• e sub i of k ‘happens before’ e sub i of k plus 1
• The kth event of the ith process ‘happens before’ the 1 + kth event of the ith process

$H_i$ := ordered sequence of events in $p_i$

• History of i

Events

• $send(m)$, $recv(m)$ have visible output
• at any node, $recv_i(m) \rightarrow send_i(m+1)$
• $send_i(m) \rightarrow recv_j(m)$

Concurrent Events

Concurrent Events := two events in which neither event happens before the Other

$e_1 \nrightarrow e_2 \land e_2 \nrightarrow e_1 \Rightarrow e_1 || e_2$

Lamport’s Scalar Clock

Each node has it’s own implementation of the clock which runs the clock rules to generate timestamps

Nodes only know the value of the timestamp that they computed

Clock Rules

1. Process imcrements timestamp on successive events
2. If a process receives a message, the new timestamp is the maximum of the message’s timestamp +1 and the processes original timestamp

Vector Clock

Each process maintains its own view of time at other nodes

Matrix Clock

Each process maintains its view about every other process’ view of the global time

Possible to use garbage collection, since we know all processes know everything that has happened past a certain point.