Time & Global States: Logical Clocks, Consistency & System Views

TAKEAWAYS:

• Logical clocks (Lamport, vector) let processes agree on event ordering without global time.
• Global state is a snapshot of all processes’ states at a moment; causal consistency ensures events are seen in the right order.
• Partial views (e.g., a node’s local snapshot) can differ but must converge for consistency.
• Checkpointing and rollbacks recover from failures by replaying logs.
• Timeouts and heartbeats detect failures in distributed systems.
• Real-world use: eSewa’s transaction ordering, Daraz’s inventory consistency, and NTC’s network routing rely on these principles.

1. Why Time Matters in Distributed Systems

In a distributed system, no single clock exists. Processes run on separate machines with independent hardware clocks. Yet, they must agree on:

• The order of events (e.g., "Did transaction A happen before B?").
• Causality (if event X causes Y, Y must follow X everywhere).
• Failure detection (e.g., "Is this node still alive?").

Example: Imagine two Daraz warehouses updating stock simultaneously. If one warehouse’s update arrives after the other’s, a customer might see inconsistent inventory. Logical clocks prevent this.

2. Logical Clocks: Ordering Events Without Global Time

Since physical clocks drift, distributed systems use logical clocks to track event order. Two key types:

A. Lamport Timestamps

• Each event gets a timestamp based on local events.
• Rules:
  1. logical_clock = max(previous_clock, incoming_message_clock) + 1
  2. If two events are causally unrelated, their timestamps can overlap (e.g., A and B start at the same time).
  3. If A → B (A causes B), then timestamp(A) < timestamp(B).

Example:

Process P1: Event A (clock=0) → Event B (clock=1)
Process P2: Event C (clock=0) → Event D (clock=2)

If B sends a message to C, C’s clock becomes max(0, 1) + 1 = 2.

Mermaid diagram of Lamport timestamps:

sequenceDiagram
    participant P1
    participant P2
    P1->>P1: Event A (clock=0)
    P1->>P2: Message (clock=1)
    P2->>P2: Event C (clock=max(0,1)+1=2)
    P2->>P1: Message (clock=3)
    P1->>P1: Event D (clock=max(1,3)+1=4)

Advantages:

• Simple to implement.
• Detects causality (if A sends to B, A’s timestamp < B’s).

Disadvantages:

• Overlap: Two unrelated events can have the same timestamp (e.g., A and C above).
• No total order (only causal order).

B. Vector Clocks

• Each process maintains a vector of timestamps (one per process).
• When a message is sent, the sender’s vector is copied to the message.
• Receiver updates its vector by taking the component-wise max with the sender’s vector.

Example:

Process P1: [1, 0]
Process P2: [0, 1]

If P1 sends to P2:

• Message carries [1, 0].
• P2 updates to [max(1,0), max(0,1)] = [1, 1].

Mermaid diagram of vector clocks:

sequenceDiagram
    participant P1
    participant P2
    P1->>P1: Vector [1,0]
    P1->>P2: Message (vector [1,0])
    P2->>P2: Update to [max(1,0), max(0,1)] = [1,1]

Advantages:

• Total order: No overlaps; events are uniquely ordered.
• Detects causality and concurrency (events that could happen in any order).

Disadvantages:

• Higher overhead (storing vectors).
• Scales poorly with many processes.

Real-world use:

• eSewa transactions: Vector clocks ensure that payment debits and credits are ordered correctly across banks.
• WhatsApp message delivery: Ensures messages are read in the correct sequence by all recipients.

3. Global State and Consistency

A global state is a snapshot of all processes’ states at a single moment. However:

• Partial views: Each process only sees its local state.
• Concurrency: Multiple processes may update states simultaneously.

A. Types of Global States

B. Causal Consistency

• Events must be seen in the same order by all processes if they are causally related.
• Example: If A sends a message to B, B must see A’s update before its own.

Mermaid diagram of causal consistency:

sequenceDiagram
    participant A
    participant B
    participant C
    A->>B: Message X (causes B's update)
    B->>C: Message Y (causes C's update)
    note right of B: C must see X before Y

C. Eventual Consistency

• Updates propagate eventually, but may not be immediately visible.
• Example: Ncell’s cell tower updates (signal strength changes take time to sync).

Trade-off:

4. Handling Partial Views and Failures

Distributed systems must handle:

• Process failures (crashes, timeouts).
• Network partitions (e.g., NTC’s outages).
• Recovery (restoring state after failure).

A. Checkpointing and Rollback

• Checkpoint: Periodically save a process’s state to disk.
• Rollback: If a failure occurs, replay logs from the last checkpoint.

Example:

Process P1:
1. State = {A: 10}
2. Checkpoint saved (State = {A: 10})
3. Update: A = 20 (not yet checkpointed)
4. Failure occurs → Rollback to checkpoint {A: 10}

Mermaid diagram of checkpointing:

stateDiagram-v2
    [*] --> State1: {A: 10}
    State1 --> Checkpoint: Save {A: 10}
    Checkpoint --> State2: {A: 20}
    State2 --> Failure: Crash!
    Failure --> Rollback: Replay from checkpoint
    Rollback --> State1: {A: 10}

B. Timeouts and Heartbeats

• Heartbeat: Regular messages sent to detect liveness.
• Timeout: If no heartbeat is received, assume failure.

Example (NTC’s router):

Router A sends heartbeat to Router B every 5 sec.
If B doesn’t respond in 10 sec, A declares B failed.

Mermaid diagram of heartbeat timeout:

sequenceDiagram
    participant A
    participant B
    loop Every 5 sec
        A->>B: Heartbeat
    end
    B-->>A: ACK (or no response)
    alt No ACK in 10 sec
        A->>A: Declare B failed
    end

5. Real-World Applications

A. eSewa: Transaction Ordering

• Idea: Lamport timestamps ensure payment debits and credits are ordered correctly across banks.
• How:
  1. User initiates payment → eSewa assigns a Lamport timestamp.
  2. Banks process transactions in timestamp order.
  3. If a bank fails, logs are replayed from the last checkpoint.

B. Daraz: Inventory Consistency

• Idea: Vector clocks prevent "phantom stock" (e.g., a product showing "in stock" in one warehouse but "out of stock" in another).
• How:
  1. Warehouse A updates stock → sends vector clock [1, 0] to Daraz’s server.
  2. Warehouse B updates stock → sends [0, 1].
  3. Server merges updates in causal order.

C. NTC: Network Routing

• Idea: Logical clocks ensure routers agree on the order of link failures.
• How:
  1. Router X detects a link failure → assigns timestamp T.
  2. Router Y receives the failure report → updates its clock to max(T, local_clock) + 1.
  3. All routers eventually agree on the failure order.

6. Exam Tips

1. Logical Clocks:

   • Know Lamport vs. vector clocks (total order vs. causal order).
   • Draw a sequence diagram for Lamport timestamps (e.g., 3 processes exchanging messages).
   • Mention causality and concurrency in your answer.

2. Global State:

   • Define local, global, and partial states.
   • Compare causal vs. eventual consistency with pros/cons.
   • Use Daraz inventory or NTC routing as a worked example.

3. Failures and Recovery:

   • Explain checkpointing and rollback with a state diagram.
   • Describe heartbeats and timeouts (e.g., NTC routers).
   • Mention recovery logs (e.g., eSewa’s transaction logs).

4. Common Pitfalls:

   • Don’t confuse physical clocks (hardware) with logical clocks (software).
   • Avoid saying "global state is always consistent" — emphasize eventual consistency.
   • For vector clocks, always show the component-wise max update.

5. Diagrams to Draw:

   • Lamport timestamp sequence diagram (3+ processes).
   • Vector clock update example.
   • Checkpointing state diagram.
   • Heartbeat timeout sequence.