Time and Ordering Lab

Retrieval Prompts

1. State the happens-before relation in words, including the three rules.
2. Write the Lamport clock update rule from memory for a local event, a send, and a receive.
3. Write the vector clock update rule from memory for the same three cases.
4. State the comparison rule for "a happens before b" using vector clocks.
5. State two things you should never use wall-clock time for in a distributed system.

Compare and Distinguish

Separate these pairs cleanly in writing:

• wall-clock time vs monotonic time
• monotonic time vs logical time
• Lamport clock vs vector clock
• L(a) < L(b) vs a -> b
• "concurrent" in a distributed sense vs "simultaneous" in a wall-clock sense

Common Mistake Check

For each, identify the error:

1. "Our servers run NTP so timestamp-based last-write-wins is safe."
2. "I used System.nanoTime() to stamp events and compared them across two services."
3. "Lamport timestamps L(a) = 3 and L(b) = 3 mean a and b are concurrent."
4. "Vector clocks give a total order over events."
5. "We resolve write conflicts by the timestamp with the largest value."

Mini Application: Three-Process Trace by Hand

Work this trace on paper, filling in both Lamport and vector timestamps at every event.

Processes: P1, P2, P3. Events in real-time order:

1. a on P1 (local)
2. b on P2 (local)
3. P1 sends m1 to P2; receipt c on P2
4. d on P3 (local)
5. P2 sends m2 to P3; receipt e on P3
6. f on P1 (local)
7. P3 sends m3 to P1; receipt g on P1
8. h on P2 (local)

Deliverables:

• Lamport timestamp on each event.
• Vector timestamp on each event.
• A written list of every pair of concurrent events you can detect from the vector clocks but not from the Lamport clocks.

Clock Confusion Case Study

The following pseudo-code runs on every node in a multi-region service:

def write(key, value):
    ts = time.time()            # wall-clock seconds since epoch
    db.store(key, value, ts)
    log.append(f"{key} -> {value} at {ts}")

def resolve_conflict(v1, v2):
    return v1 if v1.ts > v2.ts else v2

Write a one-page analysis:

1. Name at least three distinct failure modes this code has.
2. For each, describe the user-visible symptom.
3. Propose a correct replacement that uses monotonic or logical time appropriately.

Total Order Via Lamport

Task: take the trace you worked above, and produce a total order over all 8 events using (L, pid) as the sort key. Then explain why this ordering is consistent with causality even though it is not the "real" order.

Evidence Check

This practice page is complete only if you can:

• Compute Lamport and vector timestamps for a 3-process trace without checking the rules.
• Explain, in sentences, why Lamport timestamps cannot detect concurrency but vector timestamps can.
• Identify at least three distinct bugs in a piece of code that uses wall-clock timestamps for ordering.
• Articulate when monotonic time is the right choice and when logical time is.