Module 7: Time, Ordering, and Coordination

Start with one order

Checkout creates order O-17, Inventory reserves stock, and a worker updates shipping. We want three things: the reservation must refer to a created order, shipping must not move backward to “paid” when a late event arrives, and an old worker must not overwrite a new worker’s result. These are different problems. A timestamp alone cannot solve all three.

Required Preparation

Review request timeouts in Module 3, duplicates and delivery semantics in Module 5, and multiple worker replicas in Module 6. Know how to run a short Python 3 program; the examples use only the standard library. No broker or cluster is required.

For selected reading, focus on the happens-before definition and logical-clock rules in Lamport’s paper. Vector clocks and consensus below are optional.

1. Why physical time can mislead us

Checkout records “request sent” at 10:00:05. Inventory records “request received” at 10:00:02. If Inventory’s clock is behind Checkout’s, both logs can be honest. The receive still depends on the send.

Skew is the difference between clock readings at the same instant. Drift is a difference in how quickly clocks advance. Clock synchronization, such as NTP, reduces discrepancies but leaves uncertainty because network delay varies. Even close timestamps cannot reliably order events whose separation is smaller than that uncertainty. Clock corrections can also move wall time backward.

Short code: measure elapsed time

import time

start = time.monotonic()
time.sleep(0.02)  # stand-in for local work
elapsed = time.monotonic() - start
print(f"elapsed: {elapsed:.3f} seconds")

Expect roughly 0.020 seconds or more; scheduling affects the result. This measures a duration without relying on calendar time. Do not send start to another machine and subtract its clock reading. Across services, propagate a remaining timeout budget and account for transit time rather than resetting the full timeout at each hop. As in Module 3, a timeout does not prove that a remote write did not happen.

2. Happens-before: follow dependencies

Write a → b to mean a happens before b. There are three rules:

1. Within one sequential process, an earlier event happens before a later event.
2. Sending a message happens before receiving that same message.
3. The relationship is transitive: if a → b and b → c, then a → c.

If neither a → b nor b → a, the events are concurrent in the causal model. This means neither depends on the other, not necessarily that they occurred at the same physical instant. With multiple threads, include actual synchronization edges; do not infer dependencies merely from sharing a machine.

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

The order creation precedes the reservation. Analytics’ unrelated refresh can be concurrent with both. We have a partial order: some pairs are ordered, and some are not. This definition comes from Lamport’s paper.

Try it: draw an arrow from the report refresh to a message it sends to Checkout. Any later Checkout event that depends on receiving that message now has a causal path from the refresh.

3. Lamport clocks: count progress, not seconds

A Lamport clock is a local integer, initially zero. Increment it on each local or send event. Send the integer with the message. On receive, use max(local, received) + 1.

Short code: two services exchange one message

class Clock:
    def __init__(self):
        self.value = 0

    def tick(self):
        self.value += 1
        return self.value

    def receive(self, sent):
        self.value = max(self.value, sent) + 1
        return self.value

checkout, inventory = Clock(), Clock()
print("create:", checkout.tick())      # 1
sent = checkout.tick()                 # send event: 2
print("send:", sent)
print("receive:", inventory.receive(sent))  # 3
print("reserve:", inventory.tick())    # 4

Output is create: 1, send: 2, receive: 3, and reserve: 4. Inventory jumps forward so receiving is logically later than sending. Real messages must carry the counter, and each relevant event must update it.

Guarantee: if a → b, then L(a) < L(b). The converse is false: a counter of 2 on an unrelated service and a counter of 10 on Checkout do not prove a causal path. Lamport clocks do not measure seconds or detect all concurrent events.

Sorting by (counter, stable_process_id) breaks ties and creates a total order compatible with happens-before. It does not make all replicas agree on which messages exist, tell a consumer that no earlier message is still in flight, or enforce a business rule. Agreement needs more than a sort key.

4. Event ordering: choose a scope and a gap policy

Think of numbered pages in the history of order O-17: update 1 says paid, and update 2 says shipped. The order service assigns a new number for each change to that order. This update number is called a version. It is not a software release, timestamp, or broker offset. Order O-18 has its own separate numbering. Network delays and retries deliver 2, 1, 2. Applying arrival order blindly can move the order backward or repeat an effect.

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"]

For this example, one authoritative writer assigns contiguous versions for one order. If multiple writers invent versions independently, this assumption breaks. Kafka partition ordering also does not establish a global order across partitions; choose an entity key and understand the producer and consumer behavior.

Short code: buffer gaps and ignore replays

last = 0
pending = {}
state = "created"

for version, status in [(2, "shipped"), (1, "paid"), (2, "shipped")]:
    if version <= last:
        print("ignore replay", version)
        continue
    pending[version] = status
    while last + 1 in pending:
        last += 1
        state = pending.pop(last)
        print("apply", last, state)

print("final:", state, "pending:", pending)

Expected output:

apply 1 paid
apply 2 shipped
ignore replay 2
final: shipped pending: {}

This is a single-process teaching model, not a durable consumer. In a real implementation, persist the version and business update atomically, validate event identity and payload, bound the buffer, and recover missing versions through replay or an authoritative read. A duplicate version with a conflicting payload is an integrity problem; do not silently overwrite it. External effects need stable operation keys and reconciliation too.

Two valid policies: a full, authoritative snapshot can sometimes replace an older snapshot directly. A sequence of deltas, such as add 3 then subtract 1, generally needs every transition. Do not skip gaps unless the event contract makes it safe.

5. Coordination: protect a shared rule

Coordination means participants communicate to make a shared decision. For example, two shipping workers need a rule for who may update O-17. A lock or lease can help assign ownership; it does not make a slow or paused worker disappear.

A lease grants ownership for a limited period. Worker A can pause, lose its lease, and resume after B becomes owner. Checking the lease immediately before a write still leaves a pause window between the check and the write. This is why correctness must be enforced where the mutation happens.

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

A fencing token is an increasing ownership generation. The coordinator issues it safely; the protected resource atomically checks the token and performs the write, remembering the largest accepted token. Once token 42 has reached that resource, writes with token 41 are rejected. Token generation must remain safe across failover and restarts. See Kleppmann’s analysis for the pause scenario and resource-side enforcement.

Short code: reject the stale worker

highest = 0
value = None

def write(token, new_value):
    global highest, value
    if token < highest:
        return "rejected stale owner"
    highest, value = token, new_value
    return "accepted"

print(write(42, "shipped by B"))  # accepted
print(write(41, "old update by A"))  # rejected stale owner
print(value)  # shipped by B

The snippet simulates sequential calls. Production needs a durable, atomic check-and-write at the store, not these process-local variables. Equal tokens allow further writes by the same owner in this model; operation sequencing and deduplication are separate concerns.

Important boundary: if A’s token 41 arrives before the store has seen 42, this highest-seen rule can still accept it. Fencing is not a wall-clock lease-expiry test. If immediate revocation is required, the resource must validate current ownership through an appropriate atomic protocol. A downstream API that ignores tokens cannot be protected just by adding a token field to its requests.

A timeout is suspicion, not proof of death

A missed heartbeat can mean a crash, a network partition, overload, or a paused process. A replacement leader may be selected while the old process still runs. Safe ownership and resource enforcement prevent that uncertainty from becoming conflicting effects.

What coordination costs

A shared decision adds network round trips, storage work, and dependence on the coordinator’s availability. A quorum-based system can stop accepting coordinated writes on a partition without enough members. Scope coordination to the invariant: one active shipment owner may need it; independent analytics calculations often do not.

For an agent workflow, coordinate ownership of an approved proposal version. Fencing can protect your workflow store, but cannot prevent duplicate bookings at a provider that does not enforce it. Keep a stable booking operation key, verify approval for the exact proposal version, and reconcile unknown outcomes. A model-generated decision and an executor lease do not replace these checks.

Ordering and Stale-Worker Lab

Required practice, about 25 minutes. Save each Python block in its own file and run it with python3 FILE_NAME.py. These are local simulations with controlled inputs; they need no external services and perform no real payments or bookings.

Record the initial conditions, expected output, actual output, and one production limitation for each example. For a paper alternative, trace the counters, pending dictionary, and highest token by hand.

Project application: name one business invariant, its ordering scope, its authoritative writer or coordinator, its duplicate policy, and its recovery behavior after a missing reply. This is learning guidance; Canvas remains the official source for assessed requirements, deadlines, submissions, feedback, and grades.

These Concepts in an Agentic Workflow

Two agents helping the same traveler still face ordinary distributed failures. Agent A may book successfully and lose the reply; Agent B may resume the workflow before A stops. Record the proposal version, the approval of that exact version, the tool request, and the recovered outcome with stable workflow and operation IDs.

Use message dependencies to explain why a tool was called, proposal versions to reject outdated approval, and leases to assign temporary execution ownership. A workflow store that enforces fencing can reject an old executor after observing a newer token. The booking provider also needs duplicate handling using the same operation key across retries, or a lookup and reconciliation process for unknown outcomes. Fencing in your store alone cannot prevent a second external booking.

Walkthrough: proposal 3 is approved → A requests booking with key trip-17-v3 → the reply is lost → B takes over → B checks the stored approval and asks the provider about trip-17-v3 → B records the existing booking rather than creating another. This assumes the provider supports that lookup or operation-key contract; otherwise the workflow must keep the outcome unresolved and reconcile it before another booking attempt.

Optional Extension: Vector Clocks Detect Concurrency

A vector clock has one counter per participant. For two participants A and B, start at [0, 0]. Each increments its own component on a local or send event. On receive, take the componentwise maximum with the message vector, then increment the receiver’s component.

A creates an independent edit at [1, 0]; B creates another at [0, 1]. Neither vector is less than or equal to the other in every component, so the edits are concurrent. B then receives A’s edit: merge to [1, 1], increment B to [1, 2]. That receive is causally after both edits.

Vector clocks expose conflicts; they do not choose whether two document edits should merge or which booking proposal should win. Participant tracking and metadata growth also add complexity. Treat this as an extension, not a prerequisite for the lab.

Optional Extension: Consensus Agrees on Decisions

Logical clocks label events. Consensus lets participants agree on decisions despite some failures. Raft uses terms, leader election, and log replication to maintain a shared command order. In a fixed three-member cluster, a majority is two. A minority partition cannot independently commit new commands. Safety is intended to hold under the protocol’s assumptions even during delays; progress needs a communicating majority and sufficiently stable timing.

A leader replicating a current-term entry to a majority can commit it under Raft’s rules. “Any two copies of any entry” is not the complete commit rule; prior-term entries and leadership changes require the protocol’s restrictions. The Raft paper and visualization explain these details.

Consensus can back a coordinator or replicated store. It does not automatically make an external email, payment, or tool call happen exactly once. Keep external effect handling explicit.

Open-Source Tools to Try, by Slide

These are optional local exercises. Start with the Python snippets; use the linked official setup guides when trying infrastructure tools. No hosted account or real booking is required. The tools illustrate different responsibilities; installing one does not supply all the guarantees in this module.

Check Your Understanding