Skip to content
Tutorials Center
My learning

Topics

Lesson 33 of 36 ยท Projects

Project: Causally Ordered Chat

Build a chat where replies never appear before the message they answer: vector clocks, a causal delivery buffer, an out-of-order network and convergence tests.

Picture a group chat that runs on a network which delivers messages in any order. Ana asks "Lunch at noon?", Ben answers "Yes!", and Cy's screen shows the answer first: "Yes!" ... "Lunch at noon?". Nothing was lost; the messages simply took different routes. But the conversation no longer makes sense.

Fixing this does not need a central server or a global clock. In this project you combine vector clocks with a delivery buffer to build causal broadcast: a message is shown only after every message it could depend on has been shown. You then test the result against a hostile, reordering network, and check that all participants end up with the same set of messages. If you need a refresher on why causality is the right notion here, see Lamport clocks and happens-before.

What causal order promises

Reply after question If you saw it before you wrote, everyone sees it before yours.
Own messages in order One sender's messages never swap.
Concurrent is free Unrelated messages may appear in different orders.

Causal order is weaker than one global order, and much cheaper.

1 / 2

The delivery rule

Each participant keeps a vector clock clock, where clock[x] is the number of messages from x that this participant has already shown. To send, you bump your own entry and stamp the message with a copy of your whole clock. The stamp says: "I had shown this many messages from everyone when I wrote this."

A receiver may show a message m from sender s only if both conditions hold:

  1. m.vc[s] == clock[s] + 1: it is the next message from s, with no gap.
  2. For every other participant n: m.vc[n] <= clock[n]: everything the sender had seen, the receiver has seen too.

If a message fails the test it stays in the buffer. Whenever something is delivered, the buffer is rescanned, because one delivery can unlock others.

sequenceDiagram
    participant A as Ana
    participant B as Ben
    participant C as Cy
    A->>B: m1 "Lunch at noon?" (vc 1,0,0)
    A-->>C: m1 (slow)
    B->>C: m2 "Yes!" (vc 1,1,0)
    Note over C: m2 needs m1 first, so it waits in the buffer
    A-->>C: m1 arrives
    Note over C: shows m1, then m2

Ben's reply overtakes Ana's question on the way to Cy, and the buffer repairs the order.

Step 1: one peer and a hand-made scenario

Python The out-of-order reply waits in the buffer

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the stamps. m2 carries ana: 1, which means "when I wrote this, I had seen Ana's first message." Cy has seen none of Ana's messages, so condition 2 fails and m2 waits. When m1 arrives it is delivered, and the rescan then releases m2.

Step 2: concurrent messages

What if Ana and Ben write at the same time, without seeing each other's message? Their stamps are incomparable: neither is <= the other. The rule lets every receiver deliver them in whichever order they arrive, because no order was promised. That is not a bug. Two receivers may show them in different orders, and that is correct as long as both orders respect causality.

If you need everybody to see the same order for concurrent messages too, you need a total order, which means agreement (see consensus) or a deterministic tie-break, such as sorting concurrent messages by sender name once everyone has them. Causal order alone never needs agreement, and that is why it works without a leader and survives partitions.

Step 3: a hostile network and tests

Now the real test. Four peers send messages at random times. Every message goes to every other peer with a random delay from 1 to 12 ticks, so messages overtake each other constantly. We run the same seeded scenario twice: with naive delivery (show on arrival) and with causal delivery (the buffer). Then we check:

  • Causality: in every peer's log, no message appears before a message it depends on.
  • Completeness: every peer eventually shows every message and its buffer is empty.
  • Convergence: all peers end with the same set of messages, though not necessarily the same order.
Python Naive vs causal delivery on a reordering network

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The result should read like this: naive delivery violates causality in all 100 runs, while causal delivery never does (0 of 100). Both modes are complete, because nothing is lost; the buffer only delays. In the causal runs, peers' logs still differ in order (also in all 100 runs), since concurrent messages are free to arrive in different orders. That is convergence of content, not of order: exactly what causal consistency promises.

Messages that are lost for good would make a causal buffer wait forever, because later messages depend on the missing one. Real systems pair causal delivery with retransmission, or with anti-entropy between peers, so gaps get filled.

Step 4: make all peers show the same order

If you want one agreed chat history without consensus, you can add a deterministic tie-break on top of causality: once a peer holds a batch of messages that are concurrent with each other, sort them by (sender, counter). Here is the idea in miniature: a function that turns any causally valid log into a canonical order by repeatedly picking, among the messages whose causes are already placed, the smallest id.

Python A canonical order that respects causality

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both views collapse into one sequence in which m1 still precedes m2 and m4. The catch: a message that arrives late can still slot in before messages you already displayed, so the screen would have to re-sort. Truly stable order (never changing once shown) needs agreement. That is the difference between causal order and total order.

Where to take it next

  • Compact stamps: a full vector grows with the number of participants. Large groups use dotted version vectors, or cluster-level sequence numbers.
  • Joining and leaving: vectors need a fixed membership; a real group chat needs a way to add and retire entries.
  • Persistence: the buffer and the clock must survive a restart, or a restarted peer would redeliver or stall.
  • Compare: CRDTs take this further by making the data itself merge without caring about delivery order.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. When may a receiver deliver message m from sender s?

    Both conditions are needed: no gap in the sender's own sequence, and all of the sender's dependencies already delivered.
  2. 2. What does the delivery buffer do?

    Early messages wait in the buffer, and the buffer is rescanned after every delivery.
  3. 3. Two users write at the same time without seeing each other's message. What does causal delivery promise?

    Concurrent messages have no causal order, so causal delivery allows any order. A common order for them needs a tie-break or consensus.
  4. 4. What happens to a causal buffer if a message is lost forever?

    Messages that depend on the missing one can never pass the delivery test, so real systems retransmit or run anti-entropy.

Summary

  • Causal broadcast shows a message only after all messages it depends on.
  • Stamp each message with a vector clock; deliver when it is the sender's next message and the receiver has seen all the sender's dependencies.
  • Early messages wait in a buffer, rescanned after each delivery.
  • Concurrent messages may appear in different orders at different peers; all peers still converge on the same set.
  • Test with a seeded, reordering network and check causality, completeness and convergence.
  • A stable common order for everything needs a tie-break plus agreement, which is stronger (and costlier) than causal order.

Next: Practice Exercises with Solutions.