Time-Clocks

Question 1

What is the paper “Time, Clocks, and the Ordering of Events in a Distributed System” about?

Answer 1

The paper answers the question “How do you determine the order of events in a distributed system without a global clock?”.

OPTIONAL NOTE: In a distributed system, you don’t have a single clock shared across all nodes. This makes it hard to say definitively which event happened before another, especially when messages are in transit.

Question 2

What is meant by “Happened-Before Relation (->)” (DEfinition, 3 points, W.M.T)

Answer 2

This is a partial ordering of events, capturing causal dependencies.

Definition:
Event a → b (read as “a happened before b”) if:

1. Within the same process:
   If a and b occur in process P, and a comes before b, then a → b.
2. Message transmission:
   If a is the send of a message by one process and b is the receive of that message by another, then a → b.
3. Transitivity:
   If a → b and b → c, then a → c.

NOTE:
If a → b, then a could have influenced b.
If neither a → b nor b → a, the events are concurrent (denoted a || b).

Question 3

What is meant by Logical Clocks

Answer 3

A logical clock is a way of ordering events in a distributed system based on their causal relationships, rather than real-world time.

Properties Desired:
If a → b, then C(a) < C(b) (preserve causal order).

Conversely, C(a) < C(b) does not imply a → b.

Logical Clock Algorithm:
Each process Pi maintains a local clock Ci, which is an increasing counter:

For each event at process Pi:
Before executing any event:

𝐶𝑖 := 𝐶𝑖 + 1
​
When sending a message:
Send the current clock value as a timestamp: T = Ci.

When receiving a message with timestamp T_m:

Set: 𝐶𝑖 := max(𝐶𝑖,𝑇𝑚) + 1

This ensures:
If a → b, then C(a) < C(b)
But again, C(a) < C(b) does not imply a → b (non-causal orderings are possible).

Question 4

What is meant by Total Ordering of Events?

Answer 4

For some algorithms, a total order (i.e., ordering all events) is needed.

Lamport defines a total order (⇒) based on timestamp + process ID:

Define:
For events a and b,

𝑎 ⇒ 𝑏 ⟺  [𝐶(𝑎) < 𝐶(𝑏)]or[𝐶(𝑎) = 𝐶(𝑏)and𝑃𝐼𝐷(𝑎) < 𝑃𝐼𝐷(𝑏)]

This breaks ties by lexicographic comparison.

Application:
Useful for algorithms needing consistent global ordering, e.g.:

Distributed databases
Distributed ledgers

Question 5

What is the difference between partial and total ordering?

Answer 5

Partial order: Some events are ordered (e.g., message send before receive), but many events are incomparable (i.e., concurrent).

Total Order: All events are arranged linearly. No “incomparable” pairs in which every event is either before or after every other.

Question 6

What is Partial Order and Total Order

Answer 6

Partial Order: Some events are ordered (e.g., message send before receive), but many events are incomparable (i.e., concurrent).

Total Order: All events are arranged linearly. No “incomparable” pairs in which every event is either before or after every other.