CMPE273 · Module 7

Time, Ordering, and Coordination

Follow an order through skewed clocks, delayed messages, logical timestamps, and competing workers. Learn when ordering is enough and when shared decisions need coordination.

Learning Objectives

  1. Explain why wall-clock timestamps and message arrival order do not prove causality.
  2. Use a monotonic clock to measure local elapsed time.
  3. Trace happens-before relationships and compute Lamport timestamps.
  4. Handle delayed and duplicate events using explicit per-order versions.
  5. Explain lease expiry, stale workers, and resource-enforced fencing tokens.
  6. Identify the cost and scope of a coordinated decision.

Core Concepts

Clock skew

Two machines report different wall times at the same real instant.

Happens-before

A causal relationship established by local event order, message delivery, and transitivity.

Logical clock

A counter that tracks causal progress rather than seconds.

Lease

Time-limited permission to act, which a paused worker may outlive.

Fencing token

An increasing ownership generation checked by the protected resource to reject older owners.

Diagrams

Create the order, request stock, receive confirmation

sequenceDiagram
  participant C as Checkout
  participant I as Inventory
  participant A as Analytics
  C->>C: a - create order
  C->>I: b - send reserve request
  A->>A: x - refresh unrelated report
  I->>I: c - receive request
  I->>I: d - reserve stock
  I-->>C: e - send confirmation
  C->>C: f - receive confirmation

Follow local steps and message arrows from a to f. That dependency is called happens-before. The unrelated report has no message path to the order here, so it is concurrent in this model; its position on the drawing does not prove when it happened.

Update 2 arrives first — wait for update 1

flowchart LR
  A["Arrives: update 2<br/>SHIPPED<br/>Hold it for now"] --> B["Arrives: update 1<br/>PAID<br/>Apply 1, then held 2"]
  B --> C["Update 2 arrives again<br/>Already applied<br/>Ignore the replay"]

The number answers “which change of O-17 is this?” It is not a time, software release, or Kafka offset. Apply update 1 before update 2 so the order ends as shipped. Another order has its own numbering. If 1 never arrives, recover the missing update rather than wait forever.

Reject a worker whose turn has passed

sequenceDiagram
  participant A as Worker A
  participant L as Task coordinator
  participant B as Worker B
  participant S as Shipping store
  A->>L: Request a 30-second turn
  L-->>A: Lease and ownership number 41
  Note over A: Pauses beyond 30 seconds
  B->>L: Request turn after A expires
  L-->>B: Lease and ownership number 42
  B->>S: Update with number 42
  S-->>B: Accept and remember 42
  A->>S: Resume and update with 41
  S-->>A: Reject older owner

The coordinator assigns temporary ownership. Each new turn gets a larger ownership number, called a fencing token. The store atomically checks that number with the update. After accepting 42, it rejects 41. Expiry cannot stop a paused worker from resuming; the store protects the data. This example assumes safely issued, increasing tokens.

Examples, Discussions, and Project Ideas

Slide 2: Use a clock for dates and a stopwatch for waiting

At a restaurant, the clock tells you when you ordered. A stopwatch tells you how long you have waited. Software needs both kinds of time.

  • Wall-clock time is a calendar reading, such as 6:05 PM. Use it to label an order or a log.
  • If the restaurant corrects its clock backward by five minutes, your waiting time should not become negative.
  • A monotonic clock is a local stopwatch that does not move backward when calendar time is corrected. Python uses time.monotonic().
  • A checkout waiting three seconds for payment should measure a local duration. No reply means the outcome is unknown; payment may still have succeeded.
Open-source tools to try (1)

Slide 3: Follow the request to see what came first

Inventory can reserve this order only after receiving its request. An unrelated report refresh has no such dependency.

Discuss: Can the reservation happen before the request arrives? Does the report refresh need to wait?

Open-source tools to try (2)
  • OpenTelemetry — instrument request paths

    Try the Python getting-started sample and propagate trace context across a request. Parent and child spans help reconstruct dependencies; clock labels alone are insufficient.

  • Jaeger — inspect a trace

    Try the local getting-started demo and inspect one request’s spans. Tracing is evidence, not an ordering or agreement protocol.

Slide 4: Lamport clocks count steps instead of seconds

Checkout creates an order at counter 1 and sends a request at counter 2. Inventory receives 2, advances its counter to 3, and reserves stock at 4.

  • A Lamport clock is a local event counter, initially zero; it is not calendar time.
  • For a local or send event, add one. Attach that counter to the message.
  • On receive, use max(local counter, message counter) + 1. If Inventory was already at 7, receiving 2 would produce 8.
  • A cause gets a smaller counter than its consequence. Smaller counters alone do not prove a dependency between unrelated events.
Open-source tools to try (1)
  • Lamport’s Bakery Algorithm — Python code

    Optional related example — inspect bakery_algorithm.py to see numbered turns for mutual exclusion (one process at a time in a shared critical section). This demonstrates Lamport’s Bakery Algorithm, a different algorithm from the logical clocks on this slide. Use the Clock snippet in Study Mode for logical-clock practice.

Read Lamport’s original paper

Slide 5: Read order updates in the right sequence

Think of numbered pages for order O-17. Update 1 says paid; update 2 says shipped. The order service assigns these numbers, called versions, to successive changes of that one order.

Discuss: If the paid message arrives late, why should the customer’s status still end as shipped?

Slide 6: A lease gives a worker a temporary turn

A lease is permission to own a task for a limited time. Worker A gets 30 seconds to update shipping; after expiry, Worker B can take over. A might still resume later.

Discuss: If A wakes up late, which service must prevent its old update from overwriting B’s?

Open-source tools to try (2)
  • etcd — leases and coordination

    On a disposable local etcd, grant a short lease, attach a key, stop keepalive, and observe expiry. Lease expiry removes the key; it cannot stop an old worker or fence an external store by itself.

  • PostgreSQL — enforce a stored ownership rule

    Try a row storing highest_token and status; use one conditional UPDATE that accepts only tokens at least as large as the stored token. Try 42, then 41. This check needs safe token issuance and does not detect expiry by itself.

Slide 7: Try delayed messages and a late worker

Run the four short Python examples, then change delivery order and worker ownership.

  • Predict the event counters before running the Lamport example.
  • Deliver shipped before paid, then replay shipped. Check the final order state.
  • Resume the older worker after the newer worker writes. Check which update is rejected.

Open the practice lab

Slide 8: When do services need to agree?

Two workers can each calculate a sales report. But two buyers cannot both receive the last available seat. The business rule decides where agreement is needed.

  • Coordination means communicating to make a shared decision. The seat store must atomically accept one buyer and reject the other.
  • Reports can often run independently; assigning the last seat requires a shared rule enforced at the store.
  • Agreement adds communication and waiting. If the deciding service cannot be reached, checkout may need to pause rather than promise the same seat twice.
  • Lamport counters label dependencies; they do not decide who gets the seat. Optional consensus protocols such as Raft can help replicas agree on stored decisions.

Discuss: In your project, what is the equivalent of the last seat, and where is the rule enforced?

Open-source tools to try (2)
  • PostgreSQL — protect the last seat

    In two local database sessions, try UPDATE seats SET remaining = remaining - 1 WHERE id = 1 AND remaining > 0 RETURNING remaining. Starting from one seat, only one session should return a row; commit the transactions.

  • etcd — see Raft-backed agreement

    Optional: use a disposable three-member cluster and inspect leader status. Stop one member, then a second; compare progress with and without a majority. This does not make external effects exactly once.

Slide 9: Two AI agents must not book the same trip twice

A traveler approves proposal version 3. Agent A calls the booking tool, but its reply is lost. Agent B takes over while A may still be running.

  • Record dependencies — proposal created, version 3 approved, booking requested — with workflow IDs and message links. Clock time alone cannot explain why a tool ran.
  • Number proposal updates. A delayed approval for version 2 must not authorize booking version 3.
  • Give the executor a temporary turn using a lease. Use fencing at the workflow store to reject an older executor after the new ownership number is accepted.
  • Retry the booking with the same operation key if the provider supports deduplication, or look up the outcome. A missing reply does not mean no booking exists.
  • Coordination protects approved state; provider-side duplicate handling protects the external booking. An AI model does not replace either mechanism.

Discuss: Agent A’s reply is missing. What must Agent B check before trying to book again?

Open-source tools to try (2)

Canvas remains the official source for project requirements, deadlines, submissions, and grading.

Key Takeaways

Lab Links