Project P099
Message timeline
Three people send messages, each stamping events with a clock of their own: the events put back in order by wall clock, by a Lamport counter and by vector clocks; cause-and-effect pairs each order gets backwards; and for any two events, whether one could have caused the other, with the chain of steps.
2 modules · 2 recorded sessionstext-menu UI in the terminalupdated 2026-10-15
Every screen below was recorded under CPython. When this page was built, the EML interpreter replayed each session from the same input and printed the same bytes.
About
Three people, A, B and C, send each other messages, and each stamps events with a clock of their own. The program puts the events back in order three ways: by wall clock, by a Lamport counter, and by vector clocks. Only the vector clocks can say what could have caused what. It starts with 11 events; B's clock is 5 ms slow and C's 3 ms fast.
main.eml- the menu, the timeline, the orderings, and questions about two eventscausal.eml- reading events, the clocks, happened-before, chains, orderings and what they get backwards
How each part works:
- Events are typed in the order they happen: - A. - something happens to A; - A>B - A sends to B; - B<A - B receives the oldest message from A still waiting for it.
One event happens every 4 ms of true time. Each person's clock reads the true time plus that clock's skew. - Sorting by wall clock, as in the corpus case event-order-without-clock, can put a receive before its send when the receiver's clock is behind. The program counts the cause-and-effect pairs that such an order puts backwards. - A Lamport counter: each event counts one more than that person's last count, and a receive first takes the larger of its own count and the message's. A cause always gets the smaller count, so the Lamport order never puts a cause after its effect. But a smaller count does not make a cause. Concurrent events get counts too, and the order puts them one after the other. - Vector clocks: each person counts their own events, and on a receive takes the larger of each count. One event happened before another exactly when none of its counts is larger. When each has a count larger than the other's, they are concurrent. For a pair that is cause and effect, the program shows a shortest chain of steps from one to the other. A step is the same person's next event, or a message.
What is checked: menu choices 1 to 6; two different event numbers in range; events of the three forms, nobody sending to themselves, a receive only of a message that is waiting, and 2 to 30 events; clocks from -50 to 50 ms. An empty answer cancels.
Sessions: sessions/basic.in gives: - the timeline with its clocks; - the orderings: by wall clock, one message is received 1 ms before it was sent; - five pairs: - a message and its receive; - the first event and the last, with a chain of 5; - two concurrent events; - two concurrent events with equal Lamport counts; - a pair asked the other way round; - the clocks set right, with no pair backwards; then B 20 ms slow and C 15 ms fast, with 7 pairs backwards, 2 of them messages; - new events in which one message is never received, with their timeline and orderings.
sessions/bad-input.in gives: - menu choices 0 and x; - pairs: a cancel, one number, the same number twice, 0, letters, and 12; - the events A, D., A>A, B<A with nothing waiting, a single event, a second receive with nothing waiting, A.B, and 31 events; a cancel; - clocks 51 and x, a cancel after A; then +5, -50 and 50, and the timeline with them.
Built on the verified corpus case event-order-without-clock (a skewed clock orders most pairs right and inverts the ones that matter; a Lamport counter keeps every cause before its effect).
Recorded sessions
What the screen shows while someone uses the program. Each typed line appears after its prompt, the way a terminal shows it.
bad-input
interpreter: byte-equal== Message timeline ==
Three people, three clocks: putting their events back in order, and what could have caused what.
1) timeline 2) orderings 3) two events 4) new events 5) clocks 6) quit
choice> 0
Pick a number from 1 to 6.
1) timeline 2) orderings 3) two events 4) new events 5) clocks 6) quit
choice> x
Pick a number from 1 to 6.
1) timeline 2) orderings 3) two events 4) new events 5) clocks 6) quit
choice> 3
Two events by number, 1 to 11, for example 2 6.
events>
Cancelled.
1) timeline 2) orderings 3) two events 4) new events 5) clocks 6) quit
choice> 3
Two events by number, 1 to 11, for example 2 6.
events> 1
Type two different numbers from 1 to 11.
1) timeline 2) orderings 3) two events 4) new events 5) clocks 6) quit
choice> 3
Two events by number, 1 to 11, for example 2 6.
events> 1 1
Type two different numbers from 1 to 11.
1) timeline 2) orderings 3) two events 4) new events 5) clocks 6) quit
choice> 3
Two events by number, 1 to 11, for example 2 6.
events> 0 5
Type two different numbers from 1 to 11.
1) timeline 2) orderings 3) two events 4) new events 5) clocks 6) quit
choice> 3
Two events by number, 1 to 11, for example 2 6.
events> a b
Type two different numbers from 1 to 11.
1) timeline 2) orderings 3) two events 4) new events 5) clocks 6) quit
choice> 3
Two events by number, 1 to 11, for example 2 6.
events> 1 12
Type two different numbers from 1 to 11.
1) timeline 2) orderings 3) two events 4) new events 5) clocks 6) quit
choice> 4
Events, in the order they happen: A. (something happens to A), A>B (A sends to B), B<A (B receives the oldest message from A waiting for it). Persons A, B and C.
events> A
Not taken: A is not an event.
1) timeline 2) orderings 3) two events 4) new events 5) clocks 6) quit
choice> 4
Events, in the order they happen: A. (something happens to A), A>B (A sends to B), B<A (B receives the oldest message from A waiting for it). Persons A, B and C.
events> D.
Not taken: D. is not an event.
1) timeline 2) orderings 3) two events 4) new events 5) clocks 6) quit
choice> 4
Events, in the order they happen: A. (something happens to A), A>B (A sends to B), B<A (B receives the oldest message from A waiting for it). Persons A, B and C.
events> A>A
Not taken: A>A: nobody sends to themselves.
1) timeline 2) orderings 3) two events 4) new events 5) clocks 6) quit
choice> 4
Events, in the order they happen: A. (something happens to A), A>B (A sends to B), B<A (B receives the oldest message from A waiting for it). Persons A, B and C.
events> B<A
Not taken: B<A: no message from A is waiting for B.
1) timeline 2) orderings 3) two events 4) new events 5) clocks 6) quit
choice> 4
Events, in the order they happen: A. (something happens to A), A>B (A sends to B), B<A (B receives the oldest message from A waiting for it). Persons A, B and C.
events> A.
Not taken: a timeline has 2 to 30 events.
1) timeline 2) orderings 3) two events 4) new events 5) clocks 6) quit
choice> 4
Events, in the order they happen: A. (something happens to A), A>B (A sends to B), B<A (B receives the oldest message from A waiting for it). Persons A, B and C.
events> A>B B<A B<A
Not taken: B<A: no message from A is waiting for B.
1) timeline 2) orderings 3) two events 4) new events 5) clocks 6) quit
choice> 4
Events, in the order they happen: A. (something happens to A), A>B (A sends to B), B<A (B receives the oldest message from A waiting for it). Persons A, B and C.
events> A.B C.
Not taken: A.B is not an event.
1) timeline 2) orderings 3) two events 4) new events 5) clocks 6) quit
choice> 4
Events, in the order they happen: A. (something happens to A), A>B (A sends to B), B<A (B receives the oldest message from A waiting for it). Persons A, B and C.
events> A. A. A. A. A. A. A. A. A. A. A. A. A. A. A. A. A. A. A. A. A. A. A. A. A. A. A. A. A. A. A.
Not taken: a timeline has 2 to 30 events.
1) timeline 2) orderings 3) two events 4) new events 5) clocks 6) quit
choice> 4
Events, in the order they happen: A. (something happens to A), A>B (A sends to B), B<A (B receives the oldest message from A waiting for it). Persons A, B and C.
events>
Cancelled.
1) timeline 2) orderings 3) two events 4) new events 5) clocks 6) quit
choice> 5
How far each clock is from the true time, in ms, -50 to 50.
A (ms)> 51
Type a whole number from -50 to 50.
1) timeline 2) orderings 3) two events 4) new events 5) clocks 6) quit
choice> 5
How far each clock is from the true time, in ms, -50 to 50.
A (ms)> x
Type a whole number from -50 to 50.
1) timeline 2) orderings 3) two events 4) new events 5) clocks 6) quit
choice> 5
How far each clock is from the true time, in ms, -50 to 50.
A (ms)> -5
B (ms)>
Cancelled.
1) timeline 2) orderings 3) two events 4) new events 5) clocks 6) quit
choice> 5
How far each clock is from the true time, in ms, -50 to 50.
A (ms)> +5
B (ms)> -50
C (ms)> 50
Clocks: A +5, B -50, C +50 ms.
1) timeline 2) orderings 3) two events 4) new events 5) clocks 6) quit
choice> 1
Clocks: A +5 ms, B -50 ms, C +50 ms from the true time; one event every 4 ms.
event what true wall Lamport vector
A1 something happens 4 9 1 (1,0,0)
A2 sends m1 to B 8 13 2 (2,0,0)
B3 receives m1 from A 12 -38 3 (2,1,0)
B4 sends m2 to C 16 -34 4 (2,2,0)
C5 something happens 20 70 1 (0,0,1)
C6 receives m2 from B 24 74 5 (2,2,2)
C7 sends m3 to A 28 78 6 (2,2,3)
B8 something happens 32 -18 5 (2,3,0)
A9 receives m3 from C 36 41 7 (3,2,3)
A10 sends m4 to C 40 45 8 (4,2,3)
C11 receives m4 from A 44 94 9 (4,2,4)
Lamport: one more than the last count; a receive first takes the larger of its own count and the message's.
Vector: each person counts their own events and, on a receive, takes the larger of each count.
1) timeline 2) orderings 3) two events 4) new events 5) clocks 6) quit
choice> 6
Bye.
What was typed (45 lines)
0
x
3
3
1
3
1 1
3
0 5
3
a b
3
1 12
4
A
4
D.
4
A>A
4
B<A
4
A.
4
A>B B<A B<A
4
A.B C.
4
A. A. A. A. A. A. A. A. A. A. A. A. A. A. A. A. A. A. A. A. A. A. A. A. A. A. A. A. A. A. A.
4
5
51
5
x
5
-5
5
+5
-50
50
1
6
basic
interpreter: byte-equal== Message timeline ==
Three people, three clocks: putting their events back in order, and what could have caused what.
1) timeline 2) orderings 3) two events 4) new events 5) clocks 6) quit
choice> 1
Clocks: A 0 ms, B -5 ms, C +3 ms from the true time; one event every 4 ms.
event what true wall Lamport vector
A1 something happens 4 4 1 (1,0,0)
A2 sends m1 to B 8 8 2 (2,0,0)
B3 receives m1 from A 12 7 3 (2,1,0)
B4 sends m2 to C 16 11 4 (2,2,0)
C5 something happens 20 23 1 (0,0,1)
C6 receives m2 from B 24 27 5 (2,2,2)
C7 sends m3 to A 28 31 6 (2,2,3)
B8 something happens 32 27 5 (2,3,0)
A9 receives m3 from C 36 36 7 (3,2,3)
A10 sends m4 to C 40 40 8 (4,2,3)
C11 receives m4 from A 44 47 9 (4,2,4)
Lamport: one more than the last count; a receive first takes the larger of its own count and the message's.
Vector: each person counts their own events and, on a receive, takes the larger of each count.
1) timeline 2) orderings 3) two events 4) new events 5) clocks 6) quit
choice> 2
true order A1 A2 B3 B4 C5 C6 C7 B8 A9 A10 C11
by wall clock A1 B3 A2 B4 C5 B8 C6 C7 A9 A10 C11 (ties by person)
by Lamport A1 C5 A2 B3 B4 B8 C6 C7 A9 A10 C11 (ties by person)
11 events: of the 55 pairs, 45 are cause and effect - one could have led to the other - and 10 are concurrent.
By wall clock, 1 cause-and-effect pair comes out backwards; 1 is a message received before it was sent.
By Lamport, 0 come out backwards: a cause always gets the smaller count. But the order puts each of the 10 concurrent pairs one after the other too, as if one came first; only the vector clocks show which pairs are concurrent.
1) timeline 2) orderings 3) two events 4) new events 5) clocks 6) quit
choice> 3
Two events by number, 1 to 11, for example 2 6.
events> 2 3
Vector clocks: A2 (2,0,0) happened before B3 (2,1,0): none of its counts is larger, so it could have caused it.
The chain: A2 -> B3.
Lamport: 2 and 3. The smaller count may belong to a cause, or the two may be concurrent; Lamport alone cannot tell which.
Wall clocks: A2 at 8 ms, B3 at 7 ms (true 8 and 12).
The wall clocks have this pair the wrong way round.
1) timeline 2) orderings 3) two events 4) new events 5) clocks 6) quit
choice> 3
Two events by number, 1 to 11, for example 2 6.
events> 1 11
Vector clocks: A1 (1,0,0) happened before C11 (4,2,4): none of its counts is larger, so it could have caused it.
The chain: A1 -> A2 -> A9 -> A10 -> C11.
Lamport: 1 and 9. The smaller count may belong to a cause, or the two may be concurrent; Lamport alone cannot tell which.
Wall clocks: A1 at 4 ms, C11 at 47 ms (true 4 and 44).
1) timeline 2) orderings 3) two events 4) new events 5) clocks 6) quit
choice> 3
Two events by number, 1 to 11, for example 2 6.
events> 5 8
Vector clocks: C5 (0,0,1) and B8 (2,3,0) are concurrent: each has a count larger than the other's, so neither could have led to the other.
Lamport: 1 and 5. The smaller count may belong to a cause, or the two may be concurrent; Lamport alone cannot tell which.
Wall clocks: C5 at 23 ms, B8 at 27 ms (true 20 and 32).
1) timeline 2) orderings 3) two events 4) new events 5) clocks 6) quit
choice> 3
Two events by number, 1 to 11, for example 2 6.
events> 1 5
Vector clocks: A1 (1,0,0) and C5 (0,0,1) are concurrent: each has a count larger than the other's, so neither could have led to the other.
Lamport: both 1, so they are concurrent: a cause always gets the smaller count.
Wall clocks: A1 at 4 ms, C5 at 23 ms (true 4 and 20).
1) timeline 2) orderings 3) two events 4) new events 5) clocks 6) quit
choice> 3
Two events by number, 1 to 11, for example 2 6.
events> 6 5
Vector clocks: C6 (2,2,2) happened after C5 (0,0,1), so it could not have caused it.
Lamport: 5 and 1. The smaller count may belong to a cause, or the two may be concurrent; Lamport alone cannot tell which.
Wall clocks: C6 at 27 ms, C5 at 23 ms (true 24 and 20).
1) timeline 2) orderings 3) two events 4) new events 5) clocks 6) quit
choice> 5
How far each clock is from the true time, in ms, -50 to 50.
A (ms)> 0
B (ms)> 0
C (ms)> 0
Clocks: A 0, B 0, C 0 ms.
1) timeline 2) orderings 3) two events 4) new events 5) clocks 6) quit
choice> 2
true order A1 A2 B3 B4 C5 C6 C7 B8 A9 A10 C11
by wall clock A1 A2 B3 B4 C5 C6 C7 B8 A9 A10 C11 (ties by person)
by Lamport A1 C5 A2 B3 B4 B8 C6 C7 A9 A10 C11 (ties by person)
11 events: of the 55 pairs, 45 are cause and effect - one could have led to the other - and 10 are concurrent.
By wall clock, no cause-and-effect pair comes out backwards.
By Lamport, 0 come out backwards: a cause always gets the smaller count. But the order puts each of the 10 concurrent pairs one after the other too, as if one came first; only the vector clocks show which pairs are concurrent.
1) timeline 2) orderings 3) two events 4) new events 5) clocks 6) quit
choice> 5
How far each clock is from the true time, in ms, -50 to 50.
A (ms)> 0
B (ms)> -20
C (ms)> 15
Clocks: A 0, B -20, C +15 ms.
1) timeline 2) orderings 3) two events 4) new events 5) clocks 6) quit
choice> 2
true order A1 A2 B3 B4 C5 C6 C7 B8 A9 A10 C11
by wall clock B3 B4 A1 A2 B8 C5 A9 C6 A10 C7 C11 (ties by person)
by Lamport A1 C5 A2 B3 B4 B8 C6 C7 A9 A10 C11 (ties by person)
11 events: of the 55 pairs, 45 are cause and effect - one could have led to the other - and 10 are concurrent.
By wall clock, 7 cause-and-effect pairs come out backwards; 2 are messages received before they were sent.
By Lamport, 0 come out backwards: a cause always gets the smaller count. But the order puts each of the 10 concurrent pairs one after the other too, as if one came first; only the vector clocks show which pairs are concurrent.
1) timeline 2) orderings 3) two events 4) new events 5) clocks 6) quit
choice> 4
Events, in the order they happen: A. (something happens to A), A>B (A sends to B), B<A (B receives the oldest message from A waiting for it). Persons A, B and C.
events> A>B C>A A<C B. A>C C<A B<A C>B
8 events.
1 message is never received.
1) timeline 2) orderings 3) two events 4) new events 5) clocks 6) quit
choice> 1
Clocks: A 0 ms, B -20 ms, C +15 ms from the true time; one event every 4 ms.
event what true wall Lamport vector
A1 sends m1 to B 4 4 1 (1,0,0)
C2 sends m2 to A 8 23 1 (0,0,1)
A3 receives m2 from C 12 12 2 (2,0,1)
B4 something happens 16 -4 1 (0,1,0)
A5 sends m3 to C 20 20 3 (3,0,1)
C6 receives m3 from A 24 39 4 (3,0,2)
B7 receives m1 from A 28 8 2 (1,2,0)
C8 sends m4 to B 32 47 5 (3,0,3)
Lamport: one more than the last count; a receive first takes the larger of its own count and the message's.
Vector: each person counts their own events and, on a receive, takes the larger of each count.
1) timeline 2) orderings 3) two events 4) new events 5) clocks 6) quit
choice> 2
true order A1 C2 A3 B4 A5 C6 B7 C8
by wall clock B4 A1 B7 A3 A5 C2 C6 C8 (ties by person)
by Lamport A1 B4 C2 A3 B7 A5 C6 C8 (ties by person)
8 events: of the 28 pairs, 16 are cause and effect - one could have led to the other - and 12 are concurrent.
By wall clock, 2 cause-and-effect pairs come out backwards; 1 is a message received before it was sent.
By Lamport, 0 come out backwards: a cause always gets the smaller count. But the order puts each of the 12 concurrent pairs one after the other too, as if one came first; only the vector clocks show which pairs are concurrent.
1) timeline 2) orderings 3) two events 4) new events 5) clocks 6) quit
choice> 6
Bye.
What was typed (27 lines)
1
2
3
2 3
3
1 11
3
5 8
3
1 5
3
6 5
5
0
0
0
2
5
0
-20
15
2
4
A>B C>A A<C B. A>C C<A B<A C>B
1
2
6
Modules
The program as written, entry module first. Each module transpiles to its own Python file, which is what eml project run executes.
main.eml(entry)
eml# P099 message timeline: three people send messages, each stamping events
# with their own clock. Wall clocks, a Lamport counter and vector clocks
# put the events in order - and only one of them can say what could have
# caused what.
import causal
def plain(s):
0 => i
len(s) => j
while i < j and s[i] == " ":
i + 1 => i
while j > i and s[j - 1] == " ":
j - 1 => j
return s[i:j]
def number(s, most):
if len(s) == 0 or len(s) > most:
return -1
0 => n
for c in s:
if not (c >= "0" and c <= "9"):
return -1
n * 10 + int(c) => n
return n
def pad(s, n):
while len(s) < n:
s + " " => s
return s
def lpad(s, n):
while len(s) < n:
" " + s => s
return s
def label(events, i):
return causal.letter(events[i][0]) + str(i + 1)
def what(e):
if e[1] == ".":
return "something happens"
if e[1] == ">":
return "sends m" + str(e[3]) + " to " + causal.letter(e[2])
return "receives m" + str(e[3]) + " from " + causal.letter(e[2])
def vec(v):
return "(" + str(v[0]) + "," + str(v[1]) + "," + str(v[2]) + ")"
def signed(n):
if n > 0:
return "+" + str(n)
return str(n)
def timeline(events, skew):
causal.stamps(events, skew, 4) => st
("Clocks: A " + signed(skew[0]) + " ms, B " + signed(skew[1]) + " ms, C " + signed(skew[2]) + " ms from the true time; one event every 4 ms.") ^0
" event what true wall Lamport vector" ^0
for i in [0:len(events) - 1]:
(" " + pad(label(events, i), 7) + pad(what(events[i]), 22) + lpad(str(st[i][0]), 4) + lpad(str(st[i][1]), 6) + lpad(str(st[i][2]), 9) + " " + vec(st[i][3])) ^0
"Lamport: one more than the last count; a receive first takes the larger of its own count and the message's." ^0
"Vector: each person counts their own events and, on a receive, takes the larger of each count." ^0
def show_order(events, st, order):
"" => line
for i in order:
if line != "":
line + " " => line
line + label(events, i) => line
return line
def received(n):
if n == 0:
return "none is a message received before it was sent."
if n == 1:
return "1 is a message received before it was sent."
return str(n) + " are messages received before they were sent."
def orderings(events, skew):
causal.stamps(events, skew, 4) => st
0 => causal_pairs
0 => apart
for a in [0:len(events) - 1]:
for b in [a + 1:len(events) - 1]:
if causal.before(st[a][3], st[b][3]) or causal.before(st[b][3], st[a][3]):
causal_pairs + 1 => causal_pairs
else:
apart + 1 => apart
[] => truth
for i in [0:len(events) - 1]:
truth + [i] => truth
(" true order " + show_order(events, st, truth)) ^0
causal.order_by(events, st, 1) => by_wall
(" by wall clock " + show_order(events, st, by_wall) + " (ties by person)") ^0
causal.order_by(events, st, 2) => by_lamport
(" by Lamport " + show_order(events, st, by_lamport) + " (ties by person)") ^0
causal.inversions(events, st, by_wall) => w
causal.inversions(events, st, by_lamport) => l
(str(len(events)) + " events: of the " + str(causal_pairs + apart) + " pairs, " + str(causal_pairs) + " are cause and effect - one could have led to the other - and " + str(apart) + " are concurrent.") ^0
if w[0] == 0:
"By wall clock, no cause-and-effect pair comes out backwards." ^0
elif w[0] == 1:
("By wall clock, 1 cause-and-effect pair comes out backwards; " + received(w[1])) ^0
else:
("By wall clock, " + str(w[0]) + " cause-and-effect pairs come out backwards; " + received(w[1])) ^0
("By Lamport, " + str(l[0]) + " come out backwards: a cause always gets the smaller count. But the order puts each of the " + str(apart) + " concurrent pairs one after the other too, as if one came first; only the vector clocks show which pairs are concurrent.") ^0
def ask(events, skew):
("Two events by number, 1 to " + str(len(events)) + ", for example 2 6.") ^0
plain(input("events> ")) => t
if t == "":
"Cancelled." ^0
return
[] => nums
"" => w
True => ok
for c in t + " ":
if c == " ":
if w != "":
number(w, 2) => v
if v < 1 or v > len(events):
False => ok
nums + [v - 1] => nums
"" => w
else:
w + c => w
if not ok or len(nums) != 2 or nums[0] == nums[1]:
("Type two different numbers from 1 to " + str(len(events)) + ".") ^0
return
causal.stamps(events, skew, 4) => st
nums[0] => a
nums[1] => b
label(events, a) => la
label(events, b) => lb
if causal.before(st[a][3], st[b][3]):
("Vector clocks: " + la + " " + vec(st[a][3]) + " happened before " + lb + " " + vec(st[b][3]) + ": none of its counts is larger, so it could have caused it.") ^0
"" => line
for i in causal.chain(events, a, b):
if line != "":
line + " -> " => line
line + label(events, i) => line
(" The chain: " + line + ".") ^0
elif causal.before(st[b][3], st[a][3]):
("Vector clocks: " + la + " " + vec(st[a][3]) + " happened after " + lb + " " + vec(st[b][3]) + ", so it could not have caused it.") ^0
else:
("Vector clocks: " + la + " " + vec(st[a][3]) + " and " + lb + " " + vec(st[b][3]) + " are concurrent: each has a count larger than the other's, so neither could have led to the other.") ^0
if st[a][2] == st[b][2]:
("Lamport: both " + str(st[a][2]) + ", so they are concurrent: a cause always gets the smaller count.") ^0
else:
("Lamport: " + str(st[a][2]) + " and " + str(st[b][2]) + ". The smaller count may belong to a cause, or the two may be concurrent; Lamport alone cannot tell which.") ^0
("Wall clocks: " + la + " at " + str(st[a][1]) + " ms, " + lb + " at " + str(st[b][1]) + " ms (true " + str(st[a][0]) + " and " + str(st[b][0]) + ").") ^0
if (st[a][1] - st[b][1]) * (st[a][0] - st[b][0]) < 0:
"The wall clocks have this pair the wrong way round." ^0
elif st[a][1] == st[b][1]:
"The wall clocks cannot tell this pair apart." ^0
def script(events):
"Events, in the order they happen: A. (something happens to A), A>B (A sends to B), B<A (B receives the oldest message from A waiting for it). Persons A, B and C." ^0
plain(input("events> ")) => t
if t == "":
"Cancelled." ^0
return events
causal.build(t) => r
if r[1] != "":
("Not taken: " + r[1] + ".") ^0
return events
0 => waiting
{} => got
for e in r[0]:
if e[1] == "<":
True => got[e[3]]
for e in r[0]:
if e[1] == ">" and not (e[3] in got):
waiting + 1 => waiting
(str(len(r[0])) + " events.") ^0
if waiting == 1:
"1 message is never received." ^0
elif waiting > 1:
(str(waiting) + " messages are never received.") ^0
return r[0]
def clocks(skew):
"How far each clock is from the true time, in ms, -50 to 50." ^0
[] => out
for n in [0:2]:
plain(input(causal.letter(n) + " (ms)> ")) => t
if t == "":
"Cancelled." ^0
return skew
1 => sign
if len(t) > 0 and t[0] == "-":
0 - 1 => sign
t[1:len(t)] => t
elif len(t) > 0 and t[0] == "+":
t[1:len(t)] => t
number(t, 2) => v
if v < 0 or v > 50:
"Type a whole number from -50 to 50." ^0
return skew
out + [sign * v] => out
("Clocks: A " + signed(out[0]) + ", B " + signed(out[1]) + ", C " + signed(out[2]) + " ms.") ^0
return out
causal.build("A. A>B B<A B>C C. C<B C>A B. A<C A>C C<A")[0] => events
[0, 0 - 5, 3] => skew
"== Message timeline ==" ^0
"Three people, three clocks: putting their events back in order, and what could have caused what." ^0
True => running
while running:
"" ^0
"1) timeline 2) orderings 3) two events 4) new events 5) clocks 6) quit" ^0
plain(input("choice> ")) => choice
if choice == "1":
timeline(events, skew)
elif choice == "2":
orderings(events, skew)
elif choice == "3":
ask(events, skew)
elif choice == "4":
script(events) => events
elif choice == "5":
clocks(skew) => skew
elif choice == "6":
False => running
else:
"Pick a number from 1 to 6." ^0
"Bye." ^0
Python projection (main.py)
import causal
def plain(s):
i = 0
j = len(s)
while i < j and s[i] == " ":
i = i + 1
while j > i and s[j - 1] == " ":
j = j - 1
return s[i:j]
def number(s, most):
if len(s) == 0 or len(s) > most:
return -1
n = 0
for c in s:
if not (c >= "0" and c <= "9"):
return -1
n = n * 10 + int(c)
return n
def pad(s, n):
while len(s) < n:
s = s + " "
return s
def lpad(s, n):
while len(s) < n:
s = " " + s
return s
def label(events, i):
return causal.letter(events[i][0]) + str(i + 1)
def what(e):
if e[1] == ".":
return "something happens"
if e[1] == ">":
return "sends m" + str(e[3]) + " to " + causal.letter(e[2])
return "receives m" + str(e[3]) + " from " + causal.letter(e[2])
def vec(v):
return "(" + str(v[0]) + "," + str(v[1]) + "," + str(v[2]) + ")"
def signed(n):
if n > 0:
return "+" + str(n)
return str(n)
def timeline(events, skew):
st = causal.stamps(events, skew, 4)
print("Clocks: A " + signed(skew[0]) + " ms, B " + signed(skew[1]) + " ms, C " + signed(skew[2]) + " ms from the true time; one event every 4 ms.")
print(" event what true wall Lamport vector")
for i in range(0, len(events)):
print(" " + pad(label(events, i), 7) + pad(what(events[i]), 22) + lpad(str(st[i][0]), 4) + lpad(str(st[i][1]), 6) + lpad(str(st[i][2]), 9) + " " + vec(st[i][3]))
print("Lamport: one more than the last count; a receive first takes the larger of its own count and the message's.")
print("Vector: each person counts their own events and, on a receive, takes the larger of each count.")
def show_order(events, st, order):
line = ""
for i in order:
if line != "":
line = line + " "
line = line + label(events, i)
return line
def received(n):
if n == 0:
return "none is a message received before it was sent."
if n == 1:
return "1 is a message received before it was sent."
return str(n) + " are messages received before they were sent."
def orderings(events, skew):
st = causal.stamps(events, skew, 4)
causal_pairs = 0
apart = 0
for a in range(0, len(events)):
for b in range(a + 1, len(events)):
if causal.before(st[a][3], st[b][3]) or causal.before(st[b][3], st[a][3]):
causal_pairs = causal_pairs + 1
else:
apart = apart + 1
truth = []
for i in range(0, len(events)):
truth = truth + [i]
print(" true order " + show_order(events, st, truth))
by_wall = causal.order_by(events, st, 1)
print(" by wall clock " + show_order(events, st, by_wall) + " (ties by person)")
by_lamport = causal.order_by(events, st, 2)
print(" by Lamport " + show_order(events, st, by_lamport) + " (ties by person)")
w = causal.inversions(events, st, by_wall)
l = causal.inversions(events, st, by_lamport)
print(str(len(events)) + " events: of the " + str(causal_pairs + apart) + " pairs, " + str(causal_pairs) + " are cause and effect - one could have led to the other - and " + str(apart) + " are concurrent.")
if w[0] == 0:
print("By wall clock, no cause-and-effect pair comes out backwards.")
elif w[0] == 1:
print("By wall clock, 1 cause-and-effect pair comes out backwards; " + received(w[1]))
else:
print("By wall clock, " + str(w[0]) + " cause-and-effect pairs come out backwards; " + received(w[1]))
print("By Lamport, " + str(l[0]) + " come out backwards: a cause always gets the smaller count. But the order puts each of the " + str(apart) + " concurrent pairs one after the other too, as if one came first; only the vector clocks show which pairs are concurrent.")
def ask(events, skew):
print("Two events by number, 1 to " + str(len(events)) + ", for example 2 6.")
t = plain(input("events> "))
if t == "":
print("Cancelled.")
return
nums = []
w = ""
ok = True
for c in t + " ":
if c == " ":
if w != "":
v = number(w, 2)
if v < 1 or v > len(events):
ok = False
nums = nums + [v - 1]
w = ""
else:
w = w + c
if not ok or len(nums) != 2 or nums[0] == nums[1]:
print("Type two different numbers from 1 to " + str(len(events)) + ".")
return
st = causal.stamps(events, skew, 4)
a = nums[0]
b = nums[1]
la = label(events, a)
lb = label(events, b)
if causal.before(st[a][3], st[b][3]):
print("Vector clocks: " + la + " " + vec(st[a][3]) + " happened before " + lb + " " + vec(st[b][3]) + ": none of its counts is larger, so it could have caused it.")
line = ""
for i in causal.chain(events, a, b):
if line != "":
line = line + " -> "
line = line + label(events, i)
print(" The chain: " + line + ".")
elif causal.before(st[b][3], st[a][3]):
print("Vector clocks: " + la + " " + vec(st[a][3]) + " happened after " + lb + " " + vec(st[b][3]) + ", so it could not have caused it.")
else:
print("Vector clocks: " + la + " " + vec(st[a][3]) + " and " + lb + " " + vec(st[b][3]) + " are concurrent: each has a count larger than the other's, so neither could have led to the other.")
if st[a][2] == st[b][2]:
print("Lamport: both " + str(st[a][2]) + ", so they are concurrent: a cause always gets the smaller count.")
else:
print("Lamport: " + str(st[a][2]) + " and " + str(st[b][2]) + ". The smaller count may belong to a cause, or the two may be concurrent; Lamport alone cannot tell which.")
print("Wall clocks: " + la + " at " + str(st[a][1]) + " ms, " + lb + " at " + str(st[b][1]) + " ms (true " + str(st[a][0]) + " and " + str(st[b][0]) + ").")
if (st[a][1] - st[b][1]) * (st[a][0] - st[b][0]) < 0:
print("The wall clocks have this pair the wrong way round.")
elif st[a][1] == st[b][1]:
print("The wall clocks cannot tell this pair apart.")
def script(events):
print("Events, in the order they happen: A. (something happens to A), A>B (A sends to B), B<A (B receives the oldest message from A waiting for it). Persons A, B and C.")
t = plain(input("events> "))
if t == "":
print("Cancelled.")
return events
r = causal.build(t)
if r[1] != "":
print("Not taken: " + r[1] + ".")
return events
waiting = 0
got = {}
for e in r[0]:
if e[1] == "<":
got[e[3]] = True
for e in r[0]:
if e[1] == ">" and not e[3] in got:
waiting = waiting + 1
print(str(len(r[0])) + " events.")
if waiting == 1:
print("1 message is never received.")
elif waiting > 1:
print(str(waiting) + " messages are never received.")
return r[0]
def clocks(skew):
print("How far each clock is from the true time, in ms, -50 to 50.")
out = []
for n in range(0, 3):
t = plain(input(causal.letter(n) + " (ms)> "))
if t == "":
print("Cancelled.")
return skew
sign = 1
if len(t) > 0 and t[0] == "-":
sign = 0 - 1
t = t[1:len(t)]
elif len(t) > 0 and t[0] == "+":
t = t[1:len(t)]
v = number(t, 2)
if v < 0 or v > 50:
print("Type a whole number from -50 to 50.")
return skew
out = out + [sign * v]
print("Clocks: A " + signed(out[0]) + ", B " + signed(out[1]) + ", C " + signed(out[2]) + " ms.")
return out
events = causal.build("A. A>B B<A B>C C. C<B C>A B. A<C A>C C<A")[0]
skew = [0, 0 - 5, 3]
print("== Message timeline ==")
print("Three people, three clocks: putting their events back in order, and what could have caused what.")
running = True
while running:
print("")
print("1) timeline 2) orderings 3) two events 4) new events 5) clocks 6) quit")
choice = plain(input("choice> "))
if choice == "1":
timeline(events, skew)
elif choice == "2":
orderings(events, skew)
elif choice == "3":
ask(events, skew)
elif choice == "4":
events = script(events)
elif choice == "5":
skew = clocks(skew)
elif choice == "6":
running = False
else:
print("Pick a number from 1 to 6.")
print("Bye.")
causal.eml
eml# P099 message timeline - three people, A, B and C, each with a clock of
# their own, sending messages. Putting the events back in order by wall
# clock can put a reply before its message, as in the corpus case
# event-order-without-clock; a Lamport counter keeps every cause before its
# effect but cannot tell "before" from "at the same time"; vector clocks
# can.
#
# An event is [node, kind, other, message]: node and other 0, 1, 2 for A,
# B, C; kind "." (something happens), ">" (sends to other) or "<"
# (receives from other); message is the message's number from 1, or 0.
def letter(n):
return ["A", "B", "C"][n]
def node_of(c):
if c == "A":
return 0
if c == "B":
return 1
if c == "C":
return 2
return -1
def build(text):
# "A. A>B B<A": [events, ""] or [[], why]. A receive takes the oldest
# message from that sender still waiting for this node.
[] => events
[] => waiting
0 => sent
"" => w
for c in text + " ":
if c == " ":
if w != "":
if len(w) < 2 or len(w) > 3 or node_of(w[0]) == -1:
return [[], w + " is not an event"]
node_of(w[0]) => n
if w == w[0] + ".":
events + [[n, ".", -1, 0]] => events
elif len(w) == 3 and (w[1] == ">" or w[1] == "<") and node_of(w[2]) != -1:
node_of(w[2]) => o
if o == n:
return [[], w + ": nobody sends to themselves"]
if w[1] == ">":
sent + 1 => sent
events + [[n, ">", o, sent]] => events
waiting + [[n, o, sent]] => waiting
else:
-1 => found
for i in [0:len(waiting) - 1]:
if found == -1 and waiting[i][0] == o and waiting[i][1] == n:
i => found
if found == -1:
return [[], w + ": no message from " + w[2] + " is waiting for " + w[0]]
events + [[n, "<", o, waiting[found][2]]] => events
[] => rest
for i in [0:len(waiting) - 1]:
if i != found:
rest + [waiting[i]] => rest
rest => waiting
else:
return [[], w + " is not an event"]
"" => w
else:
w + c => w
if len(events) < 2 or len(events) > 30:
return [[], "a timeline has 2 to 30 events"]
return [events, ""]
def stamps(events, skew, step):
# For each event: [true time, wall clock, Lamport, vector]. Event i
# happens at true time step x (i + 1); a node's clock reads true time
# plus its skew.
[0, 0, 0] => lamport
[[0, 0, 0], [0, 0, 0], [0, 0, 0]] => vector
{} => carried
[] => out
for i in [0:len(events) - 1]:
events[i] => e
e[0] => n
if e[1] == "<":
carried[e[3]] => m
if m[0] > lamport[n]:
m[0] => lamport[n]
for k in [0:2]:
if m[1][k] > vector[n][k]:
m[1][k] => vector[n][k]
lamport[n] + 1 => lamport[n]
vector[n][n] + 1 => vector[n][n]
[vector[n][0], vector[n][1], vector[n][2]] => v
if e[1] == ">":
[lamport[n], v] => carried[e[3]]
step * (i + 1) => t
out + [[t, t + skew[n], lamport[n], v]] => out
return out
def before(u, v):
# u happened before v: no part of u is later than v, and they differ
return u[0] <= v[0] and u[1] <= v[1] and u[2] <= v[2] and (u[0] != v[0] or u[1] != v[1] or u[2] != v[2])
def chain(events, a, b):
# A shortest chain of steps from event a to event b - the next event of
# the same person, or a message from its send to its receive - or [].
[] => prev
for i in [0:len(events) - 1]:
prev + [-1] => prev
[a] => queue
0 => head
a => prev[a]
while head < len(queue):
queue[head] => i
head + 1 => head
[] => nexts
-1 => same
for j in [i + 1:len(events) - 1]:
if same == -1 and events[j][0] == events[i][0]:
j => same
if same != -1:
nexts + [same] => nexts
if events[i][1] == ">":
for j in [i + 1:len(events) - 1]:
if events[j][1] == "<" and events[j][3] == events[i][3]:
nexts + [j] => nexts
for j in nexts:
if prev[j] == -1:
i => prev[j]
queue + [j] => queue
if prev[b] == -1 or a == b:
return []
[b] => back
b => j
while j != a:
prev[j] => j
back + [j] => back
[] => out
for k in [0:len(back) - 1]:
out + [back[len(back) - 1 - k]] => out
return out
def order_by(events, st, key):
# Event numbers sorted by wall clock (key 1) or Lamport (key 2), ties
# by person, then by number.
[] => out
for i in [0:len(events) - 1]:
out + [i] => out
for i in [1:len(out) - 1]:
i => j
while j > 0 and later(events, st, key, out[j - 1], out[j]):
out[j] => x
out[j - 1] => out[j]
x => out[j - 1]
j - 1 => j
return out
def later(events, st, key, a, b):
if st[a][key] != st[b][key]:
return st[a][key] > st[b][key]
if events[a][0] != events[b][0]:
return events[a][0] > events[b][0]
return a > b
def inversions(events, st, order):
# [pairs where one happened before the other but comes after it,
# receives placed before their own send]
{} => pos
for k in [0:len(order) - 1]:
k => pos[order[k]]
0 => bad
0 => replies
for a in [0:len(events) - 1]:
for b in [0:len(events) - 1]:
if before(st[a][3], st[b][3]) and pos[b] < pos[a]:
bad + 1 => bad
if events[a][1] == ">" and events[b][1] == "<" and events[b][3] == events[a][3]:
replies + 1 => replies
return [bad, replies]
Python projection (causal.py)
def letter(n):
return ["A", "B", "C"][n]
def node_of(c):
if c == "A":
return 0
if c == "B":
return 1
if c == "C":
return 2
return -1
def build(text):
events = []
waiting = []
sent = 0
w = ""
for c in text + " ":
if c == " ":
if w != "":
if len(w) < 2 or len(w) > 3 or node_of(w[0]) == -1:
return [[], w + " is not an event"]
n = node_of(w[0])
if w == w[0] + ".":
events = events + [[n, ".", -1, 0]]
elif len(w) == 3 and (w[1] == ">" or w[1] == "<") and node_of(w[2]) != -1:
o = node_of(w[2])
if o == n:
return [[], w + ": nobody sends to themselves"]
if w[1] == ">":
sent = sent + 1
events = events + [[n, ">", o, sent]]
waiting = waiting + [[n, o, sent]]
else:
found = -1
for i in range(0, len(waiting)):
if found == -1 and waiting[i][0] == o and waiting[i][1] == n:
found = i
if found == -1:
return [[], w + ": no message from " + w[2] + " is waiting for " + w[0]]
events = events + [[n, "<", o, waiting[found][2]]]
rest = []
for i in range(0, len(waiting)):
if i != found:
rest = rest + [waiting[i]]
waiting = rest
else:
return [[], w + " is not an event"]
w = ""
else:
w = w + c
if len(events) < 2 or len(events) > 30:
return [[], "a timeline has 2 to 30 events"]
return [events, ""]
def stamps(events, skew, step):
lamport = [0, 0, 0]
vector = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
carried = {}
out = []
for i in range(0, len(events)):
e = events[i]
n = e[0]
if e[1] == "<":
m = carried[e[3]]
if m[0] > lamport[n]:
lamport[n] = m[0]
for k in range(0, 3):
if m[1][k] > vector[n][k]:
vector[n][k] = m[1][k]
lamport[n] = lamport[n] + 1
vector[n][n] = vector[n][n] + 1
v = [vector[n][0], vector[n][1], vector[n][2]]
if e[1] == ">":
carried[e[3]] = [lamport[n], v]
t = step * (i + 1)
out = out + [[t, t + skew[n], lamport[n], v]]
return out
def before(u, v):
return u[0] <= v[0] and u[1] <= v[1] and u[2] <= v[2] and (u[0] != v[0] or u[1] != v[1] or u[2] != v[2])
def chain(events, a, b):
prev = []
for i in range(0, len(events)):
prev = prev + [-1]
queue = [a]
head = 0
prev[a] = a
while head < len(queue):
i = queue[head]
head = head + 1
nexts = []
same = -1
for j in range(i + 1, len(events)):
if same == -1 and events[j][0] == events[i][0]:
same = j
if same != -1:
nexts = nexts + [same]
if events[i][1] == ">":
for j in range(i + 1, len(events)):
if events[j][1] == "<" and events[j][3] == events[i][3]:
nexts = nexts + [j]
for j in nexts:
if prev[j] == -1:
prev[j] = i
queue = queue + [j]
if prev[b] == -1 or a == b:
return []
back = [b]
j = b
while j != a:
j = prev[j]
back = back + [j]
out = []
for k in range(0, len(back)):
out = out + [back[len(back) - 1 - k]]
return out
def order_by(events, st, key):
out = []
for i in range(0, len(events)):
out = out + [i]
for i in range(1, len(out)):
j = i
while j > 0 and later(events, st, key, out[j - 1], out[j]):
x = out[j]
out[j] = out[j - 1]
out[j - 1] = x
j = j - 1
return out
def later(events, st, key, a, b):
if st[a][key] != st[b][key]:
return st[a][key] > st[b][key]
if events[a][0] != events[b][0]:
return events[a][0] > events[b][0]
return a > b
def inversions(events, st, order):
pos = {}
for k in range(0, len(order)):
pos[order[k]] = k
bad = 0
replies = 0
for a in range(0, len(events)):
for b in range(0, len(events)):
if before(st[a][3], st[b][3]) and pos[b] < pos[a]:
bad = bad + 1
if events[a][1] == ">" and events[b][1] == "<" and events[b][3] == events[a][3]:
replies = replies + 1
return [bad, replies]