Causality from event edges

What this concept is

The event graph connects consecutive events on each process and each send to its matching receive. Reachability defines happened-before; two distinct events are concurrent if neither can reach the other. The input list is a convenient processing order, not an extra communication channel.

Why it matters here

A global trace often interleaves unrelated processes. Treating adjacent trace entries as causal edges manufactures dependencies. Before assigning clocks, draw the graph and state what observations it actually includes.

Concrete example

Process A sends m, then performs local event b. Process B performs local event c, then receives m at d. Send precedes both b and d, and c precedes d. There is no path from b to d or d to b. Moving c before the send in the input list preserves this graph as long as local and message orders remain intact.

Common confusion / misconception

Earlier in a file is not necessarily happened-before. Concurrent does not mean events occurred at precisely the same physical instant. It means this event graph contains no causal path between them.

How to use it

Write process lanes, link local successors and match message IDs. Compute ancestors with a graph method before looking at clock output. Reject duplicate event IDs and receives with no earlier matching send. For this lab, a send has at most one receive and must cross processes; multicast and repeated delivery need another contract.

Check yourself

Does an undelivered send create an edge on another process? Why can two valid topological enumerations describe the same computation?

Mini drill or application

Draw the four-event example and classify every pair. Add a second message from B after d to A, then identify exactly which new paths appear.

Read this only if stuck

Use Distributed Systems: Concepts and Design on logical time and Lamport’s original paper on partial ordering. Read the event-relation definition, then reconstruct your own graph.