I'm not sure I understand what this slide is trying to express. Why can we say "10" and "00" are the only invalid outputs? If the (x) notation indicates the program order, isn't the program output deterministic? ie, shouldn't the only valid output be "01"?

As a corollary, why does the "happens-before" graph suggest that (1) must happen before (4)?

@matteosantamaria I think that the (x) notation does not indicate program order. The only order is that processors execute their own instructions sequentially, and instructions between the two processors are executed concurrently.

(1), (2), (3), (4) are just numbered statements so its easy to refer to "statement 1".

Keep in mind processor 0 is running a thread that executes (1) and (2). Processor 1 is running a thread that executes (3) and (4).

The arrows are "happens before" relationships.

• We know 1 happens before 2 because that's program order.
• We know 3 happens before 4 because that's program order.
• If "print B" emits 0, then (2) must have happened before (3).
• If "print B" emits 1, then (2) must have happened after (3).
• If "print A" emits 0, then (4) must have happened before (1).
• If "print A" emits 1, then (4) must have happened after (1).

If "print B" emits 0. Then (1) before (2) AND (2) before (3) AND (3) before (4) implies (1) before (4). Which implies "print A" must return 1.