Causal Models of Concurrency
Every programmer who has debugged a race condition has met the same conceptual gap. The source code is sequential. The running programme is concurrent, and the source does not determine its behaviour. The behaviour is determined by the causal structure of the execution: which events produced data that other events consumed, which updates preceded which reads, which messages arrived before which operations. The source code specifies a set of possible causal structures. The bug exists in some of them and not in others. A debugging tool that shows only a single interleaved trace shows one path through that set and gives no guarantee that it is the path on which the bug occurs.
This article builds the mathematical apparatus for reasoning about causal structures of concurrent executions from first principles. §1–§3 construct the operational layer: labelled transition systems, the four principal concurrency models they capture and the bisimulation equivalence that identifies models with the same observable behaviour. §4 and §5 cross from the operational to the causal: the Mazurkiewicz independence quotient removes spurious interleaving order and event structures expose the causal and conflict structure directly. §6–§8 develop happens-before, logical clocks and a measurable observability coefficient. §9–§11 describe the artefact: a shared log format, a Python analyser for recovering causal structure from vector-clock-annotated traces and a catalogue of the defect classes the analyser detects. §12–§15 survey the ecosystem, place each concurrency paradigm on a comparison matrix and close with the implementation roadmap for a causal actor layer in Rust.
0. Problem
Consider a shared integer counter initialised to zero. Two threads each read the current value, add one, and write back. The intended outcome is two: each read sees the result of the preceding write, and the operations serialise into a coherent sequence. Without explicit synchronisation the following execution is possible on any machine, including a sequentially consistent one, because the read and the write are separate operations:
Thread A Thread B
read → 0
read → 0
write 1
write 1Both threads read zero, both write one, and the counter ends at one. One increment is lost. Both threads executed their logic correctly. The failure is causal: the write by thread A and the read by thread B are concurrent. Because neither precedes the other in the execution order thread B cannot see the result of thread A's write. The standard remedy of a mutex or an atomic compare-and-swap imposes a causal dependency that forces the operations to serialise. Why the remedy works and what property it restores requires a mathematical account of causal order.
The lost-update problem is one instance of a class of bugs that are invisible to sequential reasoning and visible only under a causal model. Others include the ABA problem in lock-free data structures, causally inconsistent snapshots in replicated databases, stale reads under weak memory models, and out-of-order message delivery in distributed actor systems. All of them share the same structure: an event that should have observed the result of a prior event instead observed an older state because the causal dependency between the two events was absent from the execution.
1. Labelled Transition Systems
1.1. Basic Definitions
The foundational operational model of a reactive system is the labelled transition system, the basis of Plotkin's structural operational semantics[1] and developed extensively in Milner's work on CCS.[2]
A labelled transition system (LTS) is a triple where is a set of states, is a set of actions (the alphabet), and is the transition relation. We write for . A distinguished initial state is usually assumed.
An action may be a read, a write, a lock acquisition, a message send or a message receive. The special action denotes an internal (silent) step that produces no observable effect on the environment. The trace of an execution is the sequence of non- actions performed along a run . Two LTSs are trace-equivalent if they generate the same set of traces; they are bisimilar if a single relation between their states matches every step of either system by an equally labelled step of the other (see §3).
1.2. Interleaving Parallel Composition
The parallel composition of two systems is the system in which either component may take a step at each moment, with the other remaining idle. This is the interleaving model of concurrency: the scheduler resolves nondeterminism by choosing which component acts next.
Given and with , their interleaving parallel composition is where is the smallest relation satisfying:
The first rule allows component 1 to act alone and the second allows component 2. Silent steps fall under the same two rules: each component performs its own independently and the two never move together. Communication needs a third rule. In CCS-style synchronisation on complementary channel names and (Milner[2]) a matched send and receive fire together as one silent step:
With this rule added the composition is the CCS parallel operator. Without it the two components run side by side and never interact.
The interleaving model orders actions that the underlying semantics leaves unordered. If two processes write to disjoint memory locations in parallel the interleaving semantics produces two distinct traces (one for each scheduling order) although the two writes are causally independent. This over-specification causes the combinatorial explosion in model checking and motivates the independence-theoretic refinements of §4.
1.3. Reference Workload
For the examples throughout this article we use a six-event reference workload. Three processes exchange three messages. Process sends a message to both and ; process receives from and sends a reply to ; process receives from both. The six events are:
The happens-before partial order on this workload (derived in §6) is the running example for the clock, observability and analyser sections.
2. Concurrency Models as LTSs
2.1. Shared Memory with Locks
The classic model of concurrent programming on shared-memory multiprocessors uses a global heap of typed memory locations together with mutual exclusion primitives. A mutex is an abstract resource with two actions: and . At most one thread owns at any point. Lock acquisition blocks until the resource is free.
In LTS terms, a mutex has two states and transitions and . The parallel composition of threads and a shared heap of locations under mutexes produces a state space of up to states, where is the value domain size and the number of local states of each thread. The heap state cross-products with the thread scheduling nondeterminism. This state-space explosion obstructs model checking of shared-memory programmes at scale.
A critical section is a sequence of actions bracketed by and . The causal discipline imposed by a mutex is exactly the serialisation of critical sections: the happens-before order includes the edge from the unlock of any critical section to the lock of the next critical section on the same mutex. This is the minimal causal structure that prevents two threads from simultaneously observing the shared state.
2.2. Lock-Free Atomics and Compare-and-Swap
Lock-free data structures replace mutex-based critical sections with atomic read-modify-write instructions. The core primitive is compare-and-swap (CAS): atomically reads location , compares the value to , and writes only if the comparison succeeds. The return value is a boolean that reports success.
CAS is susceptible to the ABA problem: between a read of value and the subsequent CAS expecting , another thread may have written and then written again. The CAS succeeds even though the location has been modified, because it observes only the current value. The standard remedy is a stamped reference: pair the value with a monotonically increasing version counter. Then and are distinct even when the values agree. The version counter makes the causal history partially observable in the data itself.
In LTS terms, CAS is a single atomic transition: the state in which transitions on action to the state in which and has no intermediate states in which other threads may observe the location. The action is indivisible in the interleaving semantics: no other thread's action can be interleaved with it.
Under weak memory models (x86 TSO, ARM, RISC-V RVWMO) a CAS with sequentially consistent ordering compiles to a full barrier: a locked instruction on x86 and acquire-release atomics with fences on ARM and RISC-V. In the C++ model a CAS that reads the value written by a release operation synchronises with that write and creates a happens-before edge from it to the CAS. The C++ memory_order annotations select which such edges an operation creates, and the compiler maps each ordering to instructions and fences.
2.3. Actors and Channels
The actor model, introduced by Hewitt, Bishop and Steiger in 1973[3] and formalised by Agha,[4] replaces shared mutable state with isolated processes that communicate by passing immutable messages. Each actor has a private mailbox. Sending is asynchronous and non-blocking. Receiving is the only point at which an actor observes the external world. There is no shared heap.
In LTS terms, an actor system is a parallel composition in which each actor is an LTS over the alphabet of message types it can send and receive. The synchronisation rule matches sends from one actor with receives at another. These are the synchronisation steps in the composed LTS. Because actors share no memory, the only causal dependencies between actors are the message-passing dependencies: a receive event is causally downstream of the matching send event.
Erlang and Elixir build their runtime on this model. BEAM (Bogdan's Erlang Abstract Machine) implements actors as lightweight processes scheduled across one scheduler thread per core, with process-level garbage collection and preemption based on reduction counts. The OTP supervision tree provides fault tolerance: supervisors restart failed actors under configurable strategies. The causal structure visible at the BEAM runtime level is the mailbox FIFO order within each actor: messages from a given sender arrive at a given receiver in the order sent. Between distinct sender-receiver pairs no ordering is guaranteed.
2.4. Async and Cooperative Scheduling
Modern async runtimes (Tokio in Rust, asyncio in Python, Node.js) implement cooperative multitasking on a single thread (asyncio, Node.js) or a thread pool (Tokio). A task is a Future that yields control at each await point and allows the scheduler to run other tasks. Unlike threads, tasks have no stack of their own: each await point is an explicit suspension, and the scheduler maintains a queue of runnable tasks.
The LTS of an async system has states that include the scheduler queue, the state of all parked futures and the shared heap. Transitions correspond to a task making progress until the next await, a task waking up after its awaited future resolves or an I/O event waking a parked task. The interleaving semantics is coarser-grained than for threads. On a given worker thread, task switches occur only at await points. On a single-threaded executor the code between two consecutive awaits in a task therefore runs without interleaving.
The causal structure of an async system is richer than it appears. An await on a channel receive creates a happens-before edge from the send to the receive; an await on a JoinHandle creates an edge from the spawned task's completion to the awaiting task; a Mutex::lock() in an async context creates the same causal serialisation as its synchronous counterpart. These edges are often implicit. Standard tracing tools report wall-clock timestamps and omit them.
3. Bisimulation and Expressiveness
3.1. Strong Bisimulation
Trace equivalence is too coarse an equivalence for concurrent systems: two LTSs may generate the same set of traces while behaving differently under composition with other systems. The correct notion of behavioural equivalence for reactive systems is bisimulation, introduced by Park[5] and developed by Milner.[2]
A relation on the states of a single LTS (or relating states of two LTSs over the same alphabet) is a strong bisimulation if, whenever :
(i) for every , there exists with ; and
(ii) for every , there exists with .
Two states are strongly bisimilar, written , if there exists a strong bisimulation containing .
Strong bisimilarity is a congruence: if then for any context . Trace equivalence is also preserved by parallel composition but ignores branching. The processes and have the same traces. In a context that offers only after , the second can deadlock and the first cannot. Bisimilarity distinguishes the two.
Weak bisimulation (Milner, 1989)[2] abstracts over silent steps. Write for the weak transition that performs any number of -steps, then an -step, then any number of -steps. A weak bisimulation requires: for every , there exists with the states bisimilar (for the matching move may be zero -steps); and symmetrically. Weak bisimilarity, written , equates any two systems that have the same observable behaviour up to internal computation.
3.2. Expressiveness and Inter-encodings
A classical question in concurrency theory is whether the different models are expressively equivalent: can shared-memory concurrency simulate the actor model, and vice versa? The answer depends on the synchronisation primitives available.
Shared memory with CAS can simulate any actor system: represent each actor's mailbox as a lock-free queue, implement send as an enqueue, and implement receive as a dequeue. The simulation introduces a spin on empty mailboxes absent from the actor model and is still observationally equivalent. Actor systems can simulate shared-memory systems: represent a shared location as a dedicated actor that receives read and write requests and serialises them through its mailbox. Both simulations are faithful in the sense of weak bisimulation.
The simulations have different complexity profiles. The shared-memory simulation of actors introduces queue data structures with contention. The actor simulation of shared memory introduces a message round-trip for every memory access. These overheads reflect the different primitives of each paradigm. Inter-encodability does not imply practical equivalence.
4. Independence and Mazurkiewicz Traces
4.1. Independence Relation
The interleaving model imposes a total order on concurrent actions. The Mazurkiewicz trace theory[6] developed in the 1970s and 1980s removes this over-specification by quotienting out the spurious order: two sequences of actions are declared equivalent if one can be obtained from the other by swapping adjacent independent actions.
Given an alphabet , an independence relation is a symmetric, irreflexive relation . The dependence relation is its complement restricted to : . Actions with may be swapped freely; actions with are ordered and may not.
The standard independence relation for shared-memory systems declares two actions independent if and only if they access disjoint sets of memory locations or both are reads (reads cannot conflict with each other). Two writes to the same location are always dependent; a read and a write to the same location are dependent. For message-passing systems a send and a receive on different channels are independent; a send and the matching receive on the same channel are dependent.
4.2. Trace Monoids and Trace Equivalence
Given an independence relation , the trace equivalence on is the smallest congruence (with respect to concatenation) satisfying whenever . A trace is an equivalence class . The trace monoid is under concatenation of representatives.
Every trace in has a unique representative in Foata normal form: a sequence of steps where each step is a set of mutually independent actions, and every action in depends on at least one action in . This form is the direct algebraic precursor to the Hasse diagram of §6.
A property of a concurrent system stated as a predicate on traces is invariant under if and only if it does not depend on the order of independent actions. Such properties can be verified on a single representative of each equivalence class. One checks a single representative trace in place of all interleavings of independent actions. This is the basis for partial-order reduction in model checkers.
5. Event Structures and the Bridge Theorem
5.1. Prime Event Structures
A trace captures the sequential possibilities of a concurrent computation. An event structure captures the concurrent structure directly, without choosing a representative interleaving.
A prime event structure (introduced as an event structure by Nielsen, Plotkin and Winskel, 1981)[20] is a triple where:
- is a countable set of events;
- is the causality relation: a partial order with finite causes ( is finite for every );
- is the conflict relation: irreflexive and symmetric, and conflict-hereditary: if and then .
Winskel's 1987 account[7] states the prime case with a consistency predicate on finite sets of events in place of . The binary form above is the special case in which a finite set is consistent exactly when it contains no conflicting pair.
Two events with stand in the causal order: can only occur if has already occurred. Two events are in conflict: at most one of them can occur in any single execution. Events that are neither causally ordered nor in conflict are concurrent.
A configuration of is a finite subset that is:
- conflict-free: no two events in are in conflict;
- downward-closed (causally closed): if and then .
Dropping the finiteness requirement, the set of all configurations ordered by inclusion forms a prime algebraic domain whose compact elements are the finite configurations.
The configurations of an event structure represent the partial executions of the system. Adding an event to a configuration yields a larger configuration whenever is enabled: all causal predecessors of are already in , and is not in conflict with any event already in .
5.2. Bridge Theorem
The trace model and the event structure model describe the same mathematical object from two perspectives. The following construction is the bridge between them.
Let be a deterministic LTS with alphabet , let be its prefix-closed set of action sequences, and let be an independence relation such that is closed under and coherent (if and then ). Define the event structure as follows: events are the prime traces, the classes with that have a single maximal occurrence; causality is the prefix order on traces; two events are in conflict when no sequence in has both as prefixes. Then the configurations of ordered by inclusion are isomorphic to the traces ordered by prefix.[7]
By the bridge theorem the happens-before partial order on the events of a single execution is the restriction of the causality relation of the underlying event structure to the events that occurred in that execution. The events of an execution form a configuration of the system's event structure, and the Hasse diagram of its happens-before order is the transitive reduction of causality restricted to that configuration.
6. Happens-Before and Logical Clocks
6.1. Lamport's Happens-Before
In his 1978 paper "Time, Clocks, and the Ordering of Events in a Distributed System,"[8] Leslie Lamport defined the happens-before relation for distributed systems in terms of three axioms: process order, message order and transitivity.
Let be the set of events in a distributed execution, partitioned into process-local sequences . The happens-before relation is the smallest transitive relation satisfying:
- Process order: if and are events in the same process and precedes in the process's execution sequence, then ;
- Message order: if and for the same message , then .
Two events with and are concurrent, written .
The happens-before relation is a strict partial order on : it is irreflexive (no event precedes itself) and transitive by definition. Concurrent events are incomparable. The Hasse diagram of is the transitive reduction: the graph obtained by removing all edges for which a path exists through an intermediate event .
6.2. Lamport Scalar Clocks
A Lamport clock is a function that is consistent with the happens-before order: implies . Lamport gave an algorithm for computing such a clock in a distributed system without shared memory:
- Each process maintains a local counter, initialised to zero.
- On every event, the counter is incremented.
- On sending a message, the current counter value is included in the message.
- On receiving a message with timestamp , the local counter is set to .
The Lamport clock satisfies . The converse fails: does not imply . Two concurrent events may receive different clock values. This gap makes Lamport clocks insufficient for recovering the full happens-before order from a log. Scalar timestamps cannot distinguish a causal dependency from a coincidental ordering of concurrent events.
6.3. Vector Clocks
Fidge[9] and Mattern[10] independently developed vector clocks. These close the gap by satisfying both directions of the implication.
A vector clock for a system of processes is a function . Write for componentwise comparison: for all . Write if and . The vector clock is maintained as follows:
- Each process initialises its vector to .
- On each event at process , increment by one.
- On sending a message, include the current vector in the message.
- On receiving a message with vector , set for all , then increment .
Under the vector clock assignment above, for any two events and :
That is, event happens before event if and only if the vector clock of is strictly dominated componentwise by the vector clock of . Two events are concurrent if and only if their vectors are incomparable.
This characterisation means that a log of events annotated with vector clocks contains complete causal information: the happens-before partial order is recoverable exactly from the clock values, without any additional communication or synchronisation. The overhead is proportional to : each message includes a vector of integers, where is the number of processes. For large distributed systems with hundreds of processes this overhead matters. Interval tree clocks give compact exact representations for systems in which processes are created and retired dynamically. Plausible clocks use constant size and order some concurrent events.
6.4. Order Theory of Logical Time
The happens-before partial order on a finite execution is a finite poset. The order theory of finite posets connects the causal structure of executions to combinatorial and lattice-theoretic results.
Every partial order has at least one linear extension: a total order consistent with the partial order. More precisely, if is a partial order and and (that is, and are incomparable), then there exists a total order on such that for all , and either or .[11]
The Szpilrajn theorem is the foundation of the linearisability notion in §7: a concurrent execution is linearisable if there exists a linear extension of the real-time precedence order on its operations that satisfies the sequential specification of the data structure.
In any finite poset, the minimum number of chains needed to partition the poset equals the maximum size of an antichain.[12]
For concurrent executions Dilworth's theorem says that the minimum number of sequential threads needed to explain the execution equals the maximum number of pairwise concurrent events. An execution with a wide antichain (many pairwise concurrent events) cannot be explained by a single sequential process.
Counting the number of linear extensions of a finite partial order is -complete.[13]
The number of distinct interleavings consistent with a given causal structure can grow exponentially in the number of events once the width exceeds one, and counting them exactly is intractable. Deterministic replay re-executes a single interleaving. Identifying that interleaving requires the causal structure.
For any finite distributive lattice , there is a unique (up to isomorphism) finite poset such that , the lattice of order ideals of ordered by inclusion.[14]
For a finite conflict-free event structure, such as the events of a single execution, the configurations ordered by inclusion are the order ideals of and form a distributive lattice. Birkhoff's theorem says that this lattice determines the causal poset: is recovered as the poset of join-irreducible configurations.
The happens-before partial order of a distributed system is structurally identical to the causal order of relativistic spacetime events. Malament's theorem (1977),[15] with the earlier result of Hawking, King and McCarthy (1976), proves that for past- and future-distinguishing spacetimes the causal partial order determines the conformal structure: the metric up to a positive scaling factor. This underlies the causal set programme for discrete quantum gravity, which proposes that spacetime is a locally finite poset and that the causal order is the fundamental physical structure. Both are instances of the same mathematical object: a locally finite partial order on a set of events.
6.5. Hybrid Logical Clocks
In production systems wall-clock time is a useful annotation although it is causally unreliable (NTP skew, leap seconds, clock drift). The hybrid logical clock (HLC) introduced by Kulkarni, Demirbas, Madappa, Avva and Leone (2014)[16] combines the causality guarantee of Lamport clocks with a best-effort approximation of wall-clock time.
An HLC timestamp is a pair where tracks the maximum physical time observed and is a counter that breaks ties when multiple events share the same . The update rules ensure that implies the HLC of is strictly less than the HLC of in the lexicographic order on , and that stays close to physical time. HLC timestamps suit systems where debugging requires correlating causal logs with external time series (metrics, alerts) because they give a causally valid ordering that is also approximately temporally interpretable.
7. Correctness as Predicates over Pomsets
7.1. Partially Ordered Multisets
A pomset (partially ordered multiset) is the natural data type for a concurrent execution: a finite set of event occurrences labelled by actions and partially ordered by the happens-before relation.
A pomset is a triple where is a finite set of event occurrences, is a partial order on , and is a labelling function. The labelling assigns to each occurrence the action it performs (a read of value from location , a write of value to location , a send of message , etc.).
A correctness condition for a concurrent data structure or system is a predicate on the pomset of its executions. The major correctness conditions form a hierarchy of decreasing strength.
7.2. Linearisability
Linearisability is the standard correctness condition for shared-memory concurrent objects and was introduced by Herlihy and Wing (1990).[17] It requires that every concurrent execution appear as if the operations were executed atomically in some sequential order consistent with their real-time overlap.
A history of operations on a concurrent object is linearisable if there exists a sequential history such that:
- is a legal sequential execution of the object (it satisfies the object's sequential specification);
- is consistent with the real-time order of : if operation completes before operation begins in , then precedes in .
The sequential history assigns each operation a linearisation point: an instant within its execution interval at which it appears to take effect atomically.
Linearisability is a local property: a system of linearisable objects is itself linearisable. This compositionality suits library-level concurrent data structures. The single-element operations of the java.util.concurrent queues and maps are linearisable; their iterators and bulk operations are documented as weakly consistent.
7.3. Sequential Consistency
Lamport (1979)[18] defined sequential consistency as the correctness condition for shared-memory multiprocessors. It is strictly weaker than linearisability: it requires a valid sequential order consistent with each process's local order and ignores the real-time order between processes.
An execution is sequentially consistent if there exists a total order on all operations that:
- is consistent with the program order of each individual process (each process's operations appear in execution order); and
- the value returned by each read is the value written by the most recent write to the same location in the total order.
Sequential consistency does not compose: a system of sequentially consistent components is not necessarily sequentially consistent as a whole. This non-compositionality was one of Herlihy and Wing's motivations for defining linearisability.
7.4. Causal Consistency
Causal consistency (Ahamad, Neiger, Burns, Kohli and Hutto, 1995)[19] is the consistency model appropriate for geo-distributed systems where linearisability and sequential consistency are difficult to enforce across wide-area networks. It requires only that causally related writes be seen in the same order by all processes. Concurrent writes may be seen in different orders at different replicas.
An execution is causally consistent if, for any two writes and (to any locations) such that (w1 causally precedes w2), every process sees before . Concurrent writes (writes with ) may be seen in any order by different processes.
The strictness hierarchy for shared data is: linearisability implies sequential consistency implies causal consistency. Eventual consistency is a convergence guarantee and sits outside this chain. Gilbert and Lynch proved the CAP theorem for the strongest condition:[21] in an asynchronous network no read/write object that answers every request during a partition can be linearisable. Causal and eventual consistency admit implementations that stay available under partition. The appropriate choice depends on the application: a bank balance requires linearisability; a social media feed can tolerate causal consistency; a CDN serving static assets needs only eventual consistency.
8. Observability Coefficient
8.1. Definition
The observability coefficient measures how much of the true causal structure of an execution is recoverable from the instrumentation applied to it. It is defined as the recall of the true Hasse diagram of the happens-before order under the chosen instrumentation regime.
Let be the true happens-before partial order of an execution, and let be its Hasse diagram (transitive reduction). Under instrumentation regime , let be the set of Hasse edges recoverable from the log produced by regime . The observability coefficient is:
When (no two events are causally related, as in a single-event execution), define .
Three instrumentation regimes are of practical interest:
No instrumentation (): the log contains only wall-clock timestamps and actor identifiers. No Hasse edges are recoverable because wall-clock order is unreliable and does not imply causal order. Thus .
Program order only (): the log includes a per-actor sequence number. This recovers the within-actor Hasse edges (adjacent events in the same process's execution sequence) and misses the inter-actor message edges. Thus where is the set of within-actor Hasse edges.
Vector clock (): the log includes a full vector clock for every event. By the characterisation theorem of §6.3, this recovers the complete happens-before order.
Under vector-clock instrumentation : the complete Hasse diagram of the happens-before order is recoverable from the log.
The proof is immediate from the characterisation theorem: . Hence the transitive reduction can be computed from the vector clocks by the hasse() algorithm of §10.
8.2. Observability in BEAM Systems
BEAM-based systems (Erlang, Elixir) offer runtime observability through native primitives: :sys.get_state/1 for inspecting any process's state, Process.info/2 for memory, message queue length and link topology, and recon_trace from the recon library for attaching lightweight function-call tracers to running production processes without restart. The dbg and ttb tracers extend tracing across the nodes of a distributed Erlang cluster.
These tools expose the operational layer. :sys.trace reveals the sequence of messages an actor received, in the order they were delivered to its mailbox. It does not reveal the vector clock of each message, the happens-before structure relating messages across actors, or whether a particular read causally depended on a particular earlier write. The observability coefficient of a production BEAM system with default instrumentation is determined by the mailbox FIFO property: within a single sender-receiver pair messages arrive in order and the within-pair causal edges are partly recoverable. Across pairs without vector clocks .
A Rust actor system instrumented with vector clocks has against in all but the trivial case. The observability coefficient is a quantitative criterion for comparing instrumentation strategies across runtimes.
9. Shared Log Format
9.1. Schema
The analyser ingests a newline-delimited JSON log (NDJSON): one JSON object per line, one line per event. The schema is:
{
"id": "string (globally unique event identifier, by convention actor#seq)",
"actor": "string (process or thread name)",
"seq": "integer (monotone within the actor, 0-indexed)",
"op": "emit | recv | compute | report | drop",
"vclock": {"actor_name": integer, ...},
"lamport": "integer (scalar Lamport timestamp, for exposition)",
"msg_id": "string or null (links an emit to its matching recv)",
"src": "string or null (sender, on recv)",
"dst": "string or null (receiver, on emit and drop)",
"value": "number or null (payload value)",
"payload_hash": "string or null (hash of the payload as seen by this event)"
}The vclock field is the authoritative causal annotation. The lamport field is for exposition: the analyser recovers order from vclock alone. The seq field encodes program order within the actor and is sufficient for the program_order regime. A msg_id is unique across the whole log, and the analyser pairs each recv with its emit through it.
9.2. POSIX Clock Caveat
Wall-clock time from CLOCK_REALTIME (or SystemTime::now() in Rust, time.time() in Python) is subject to NTP adjustments, leap-second handling and clock skew between nodes. It is not monotone across events on different machines and may not be monotone within a single machine if the system clock is stepped backward. Using wall-clock order as a proxy for causal order is a source of heisenbugs: the log appears causally ordered in testing (where the clock skew is small and NTP is stable) and appears out of order in production (where nodes diverge under load). The log format has no wall-clock field for this reason. A deployment that wants wall-clock correlation with external time series can attach it in the export layer, outside the fields the analyser reads.
10. Analyser
10.1. Happens-Before from Vector Clocks
The Python analyser in concurrency-causality/analyzer/ implements the causal analysis pipeline. The core computations are in two modules: order.py for the causal order and Hasse diagram, and observability.py for the observability coefficient.
The happens_before function implements the vector clock characterisation theorem directly:
def vc_leq(a: dict[str, int], b: dict[str, int]) -> bool:
for k in a.keys() | b.keys():
if a.get(k, 0) > b.get(k, 0):
return False
return True
def happens_before(e: Event, f: Event) -> bool:
if e.vclock == f.vclock:
return False
return vc_leq(e.vclock, f.vclock)The vc_leq function is the componentwise comparison on maps with missing keys interpreted as zero. Two events are ordered if and only if vc_leq returns true and their clocks differ. The function implements the characterisation .
10.2. Hasse Diagram
The hasse function computes the transitive reduction of the happens-before order:
def hasse(events: list[Event]) -> set[tuple[str, str]]:
index = {e.id: e for e in events}
ids = list(index)
order: set[tuple[str, str]] = set()
for a in ids:
for b in ids:
if a != b and happens_before(index[a], index[b]):
order.add((a, b))
reduced = set(order)
for a, c in order:
for b in ids:
if b != a and b != c and (a, b) in order and (b, c) in order:
reduced.discard((a, c))
break
return reducedThe algorithm is in the number of events: quadratic to build the full order, cubic to remove transitive edges. For typical trace sizes in debugging sessions (hundreds to low thousands of events) this is fast enough for interactive use. Traces with millions of events call for a sparse algorithm based on depth-first search.
10.3. Observability Coefficient in Code
The omega function in observability.py implements the three instrumentation regimes:
def omega(events: list[Event], regime: str) -> float:
true_hasse = hasse(events)
if not true_hasse:
return 1.0
if regime == "none":
recovered: set[tuple[str, str]] = set()
elif regime == "vclock":
recovered = set(true_hasse)
elif regime == "program_order":
by_actor: dict[str, list[Event]] = {}
for e in events:
by_actor.setdefault(e.actor, []).append(e)
recovered = set()
for actor_events in by_actor.values():
ordered = sorted(actor_events, key=lambda e: e.seq)
for a, b in zip(ordered, ordered[1:]):
edge = (a.id, b.id)
if edge in true_hasse:
recovered.add(edge)
return len(recovered) / len(true_hasse)The program_order regime recovers within-actor adjacent edges: pairs of consecutive events in the same actor's sequence that are also in the Hasse diagram. Not every pair of consecutive events at the same actor is a Hasse edge. If sends a request and the next event at the same actor receives the reply, the path through the other actor makes transitive and the reduction removes it.
11. Failure Mode Detection
The detect_defects function in defects.py reports five classes of defect from the log. The detectors are independent and may report the same fault twice: a partitioned edge also yields one lost message per unmatched send.
Lost message. An emit has no recv with the same msg_id and no drop record. The message left the sender and never arrived.
Overflow. A drop event records that a producer discarded a message, as a full ring buffer does.
Deserialisation break. A matched emit and recv have different payload_hash values. The receiver decoded something other than what the sender encoded.
Partition. A directed edge from one actor to another has at least two sends and no receives.
Clock regression. An event's vector clock breaks the update protocol: it fails to dominate the clock of the previous event at the same actor, or a receive event's clock fails to dominate the clock stamped on the matching send. Either a component drops the max step on receive or messages are replayed out of order. Detection: walk each actor's events in seq order and check that with the actor's own component increased by exactly one (the previous clock of the first event is zero), and check on every receive that .
Defects on shared memory, such as stale reads and concurrent writes to one location, need read and write events keyed by location. The log format records messages and local steps only. Detecting them needs a location field in the schema.
12. Rust Ecosystem and Three-Layer Design
12.1. Actor Runtimes in Rust
The Rust async ecosystem has several actor frameworks, each with a different design philosophy.
kameo is a Tokio-native async actor library with typed messages: each actor declares its message types via a Message trait implementation, and the compiler statically verifies that only the declared message types are sent to each actor. Messages are processed one at a time from the actor's inbox. Access to the actor's state is therefore single-threaded. kameo supports supervision, remote actors over network transports and graceful shutdown. Its async-native design means a parked actor occupies no OS thread.
ractor is an OTP-influenced actor framework that supports both synchronous and asynchronous message handling. It defines an Actor trait with pre_start, handle and post_stop lifecycle hooks that mirror the Erlang gen_server callback model. ractor actors can form supervision hierarchies, and the companion ractor-supervisor crate provides OTP's one_for_one, one_for_all and rest_for_one restart strategies.
actix and actix-web were the dominant Rust actor frameworks in the 2019–2021 era. actix-web now uses Tokio directly for its HTTP runtime and has moved away from the actor model for request handling. The actor abstraction remains for compatibility and is no longer the primary abstraction.
Other crates of interest in this space: thingbuf for lock-free MPSC ring buffers with async support; rtrb for wait-free SPSC; shuttle for randomised, seed-replayable schedule exploration; madsim for seeded deterministic Tokio simulation with mocked I/O; and turmoil for single-thread network simulation. The OpenTelemetry Rust SDK provides the sink layer for causal metadata export described in §12.2.
Neither kameo nor ractor natively instruments its messages with causal clocks. Message delivery preserves the FIFO order within a channel but no vector clock is attached to messages and no Hasse diagram is recoverable from a default log. The observability coefficient of a production Rust actor system under these frameworks is : within-actor ordering is observable and inter-actor causal structure is hidden.
12.2. Three-Layer Causal Instrumentation Design
The gap between the theoretical observability achievable with vector clocks and the practical observability of current Rust actor frameworks motivates a three-layer instrumentation design.
Transport layer. The actor runtime (kameo, ractor or a custom implementation) handles message delivery, scheduling and lifecycle and is left unmodified. At this layer messages are delivered in FIFO order per channel and the actor's state is accessible only from within the actor's message handler.
Clock envelope layer. Every outgoing message is wrapped in a CausalEnvelope<M>:
struct CausalEnvelope<M> {
vclock: HashMap<ActorId, u64>,
payload: M,
}The actor maintains a local vector clock as an Arc<Mutex<HashMap<ActorId, u64>>>. On every send the local clock is incremented and stamped into the envelope. On every receive the local clock is updated by max with the envelope's clock and then incremented. The rules are the vector clock update protocol of §6.3.
OpenTelemetry sink layer. After processing each message the actor emits an OpenTelemetry span with the causal metadata: actor ID, sequence number, vector clock snapshot, and a description of the action. The OTel span is exported to a collector that stores events sorted by the sum of their vector clock components. Since implies and hence a strictly smaller sum, the sorted order is a topological sort of the happens-before partial order, and the analyser of §10 can reconstruct the full Hasse diagram from the collector's output.
The design decouples causal instrumentation from the actor runtime: any actor framework that delivers messages can be wrapped with the clock envelope layer without modifying the framework's internals. The overhead is one increment per send, one pass over the vector clock per receive (the max update) and the OTel span emission, which can be asynchronous.
12.3. BEAM Contrast in Depth
Erlang and Elixir's runtime observability tools give a different kind of visibility from vector clocks.
:sys.get_state/1 suspends the target process and returns its internal state. The introspection is synchronous: the observer sees a consistent snapshot of the actor's state after a brief pause. No Rust equivalent works without modifying the actor because Rust's ownership model prevents external code from accessing an actor's state while the actor has a mutable reference to it.
recon_trace attaches a trace to running production processes based on function name patterns, sampling rate and a maximum message count without restarting the process. Live tracing works because BEAM compiles to a bytecode that includes source metadata and the VM has its trace infrastructure built in. Rust's compiled native binaries have no analogous built-in tracing API. The closest analogues are perf probes and DTrace USDT probes, which require symbol table information and root access.
The BEAM tools excel at operational observability: what is the actor doing right now, how full is its mailbox, what messages has it received recently. They are weaker at causal observability: which message caused which side effect, whether a read observed the value written by a causally prior write, whether two concurrent writes produced a conflict. The three-layer design complements BEAM's operational tools and adds causal structure that both ecosystems currently lack.
13. Comparison Table
The five major concurrency paradigms considered in this article differ on six causal-observability axes:
| Paradigm | Causal model | Compositionality | Default | Max | Replay | Formalised |
|---|---|---|---|---|---|---|
| Shared memory / mutex | Serialised critical sections | Yes (linearisability) | 0 | 1 (VC on mutex ops) | Scheduler control | RustBelt, C++ memory model |
| Lock-free atomics (CAS) | Acquire-release fences | Yes (linearisability) | 0 | 1 (VC on sync ops) | Hard (requires hardware replay) | C++ memory model, LLVM IR |
| Actors (BEAM) | Mailbox FIFO per pair | Partial (OTP supervision) | 1 (add VC to messages) | Possible (record mailbox order) | Operational semantics (process calculus) | |
| Actors (Rust: kameo, ractor) | Channel FIFO | Partial (typed messages) | 1 (three-layer design) | Possible (record channel order) | None (in progress) | |
| Async cooperative (Tokio) | Await-point boundaries | Yes (task-level) | 0 | 1 (VC on channel ops) | Possible (deterministic scheduler) | None (in progress) |
Here denotes the program-order observability coefficient: the fraction of Hasse edges that are within-actor adjacent edges, which varies by execution and is strictly less than 1 whenever inter-actor causal edges are present in the Hasse diagram.
The formalisation status column reflects the current state of the field. Shared-memory concurrency under C++ memory model semantics is formalised and has machine-checked proofs (RustBelt, the Iris framework). The BEAM actor model has operational semantics in process-calculus style but no formalisation of causal observability. Rust actor frameworks and async runtimes have no published formal account of their causal semantics.
14. Interactive Exploration
The following widget renders the happens-before Hasse diagram for four predefined execution scenarios (the §1.3 reference workload, the lost-update race, a mutex-serialised execution and an actor chain), with the observability coefficient computed live for each instrumentation regime. The computation runs in a Rust/WASM module compiled into this page.
15. Coda
The programme laid out in this article connects three levels: the operational level of labelled transition systems and their bisimulation equivalences, the trace-algebraic level of Mazurkiewicz independence and event structures, and the causal level of happens-before partial orders and logical clocks. These are three presentations of the same structure related by the bridge theorem of §5.2 and the vector clock characterisation of §6.3.
The observability coefficient is a single number that quantifies how much causal structure an instrumentation regime recovers. No causal structure is visible without instrumentation, the within-actor structure under program-order instrumentation and the complete structure under vector-clock instrumentation. The three-layer actor design in §12.2 implements vector-clock instrumentation in Rust and the analyser in §10 computes the coefficient and detects causal defects from the resulting logs.
Several directions remain open. First a Lean 4 formalisation of the bridge theorem (§5.2) and the vector clock characterisation theorem (§6.3) would give machine-checked proofs of the results on which the analyser correctness depends. Second the three-layer design is a library specification and the causal_actor crate is its planned Rust implementation for publication on crates.io. Third cross-language trace correlation: a system in which a Rust service calls a Python subprocess which calls an Erlang node would benefit from a shared NDJSON log format that spans all three runtimes with a common vector clock namespace keyed by actor string identifiers. The format of §9 is designed with this in mind.
References
- G. D. Plotkin, "A Structural Approach to Operational Semantics," Report DAIMI FN-19, Aarhus University, 1981.
- R. Milner, Communication and Concurrency. Prentice Hall, 1989.
- C. Hewitt, P. Bishop, and R. Steiger, "A Universal Modular ACTOR Formalism for Artificial Intelligence," in Proc. 3rd IJCAI, 1973, pp. 235–245.
- G. Agha, Actors: A Model of Concurrent Computation in Distributed Systems. MIT Press, 1986.
- D. Park, "Concurrency and Automata on Infinite Sequences," in Theoretical Computer Science, Lecture Notes in Computer Science, vol. 104. Springer, 1981, pp. 167–183. doi:10.1007/BFb0017309
- A. Mazurkiewicz, "Trace Theory," in Advances in Petri Nets 1986, Lecture Notes in Computer Science, vol. 255. Springer, 1987, pp. 279–324. doi:10.1007/3-540-17906-2_30
- G. Winskel, "Event Structures," in Advances in Petri Nets 1986, Lecture Notes in Computer Science, vol. 255. Springer, 1987, pp. 325–392. doi:10.1007/3-540-17906-2_31
- L. Lamport, "Time, Clocks, and the Ordering of Events in a Distributed System," Commun. ACM, vol. 21, no. 7, pp. 558–565, July 1978. doi:10.1145/359545.359563
- C. J. Fidge, "Timestamps in Message-Passing Systems That Preserve the Partial Ordering," in Proc. 11th Australian Computer Science Conf., 1988, pp. 56–66.
- F. Mattern, "Virtual Time and Global States of Distributed Systems," in Parallel and Distributed Algorithms. North-Holland, 1989, pp. 215–226.
- E. Szpilrajn, "Sur l'extension de l'ordre partiel," Fundamenta Mathematicae, vol. 16, pp. 386–389, 1930.
- R. P. Dilworth, "A Decomposition Theorem for Partially Ordered Sets," Ann. Math., vol. 51, no. 1, pp. 161–166, 1950. doi:10.2307/1969503
- G. Brightwell and P. Winkler, "Counting Linear Extensions," Order, vol. 8, no. 3, pp. 225–242, 1991. doi:10.1007/BF00383444
- G. Birkhoff, "Rings of Sets," Duke Math. J., vol. 3, no. 3, pp. 443–454, 1937. doi:10.1215/S0012-7094-37-00334-X
- D. Malament, "The Class of Continuous Timelike Curves Determines the Topology of Spacetime," J. Math. Phys., vol. 18, no. 7, pp. 1399–1404, 1977. doi:10.1063/1.523436
- S. S. Kulkarni, M. Demirbas, D. Madappa, B. Avva, and M. Leone, "Logical Physical Clocks," in Principles of Distributed Systems (OPODIS 2014), Lecture Notes in Computer Science, vol. 8878. Springer, 2014, pp. 17–32. doi:10.1007/978-3-319-14472-6_2
- M. Herlihy and J. M. Wing, "Linearizability: A Correctness Condition for Concurrent Objects," ACM Trans. Program. Lang. Syst., vol. 12, no. 3, pp. 463–492, July 1990. doi:10.1145/78969.78972
- L. Lamport, "How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs," IEEE Trans. Comput., vol. C-28, no. 9, pp. 690–691, Sept. 1979. doi:10.1109/TC.1979.1675439
- M. Ahamad, G. Neiger, J. E. Burns, P. Kohli, and P. W. Hutto, "Causal Memory: Definitions, Implementation, and Programming," Distrib. Comput., vol. 9, no. 1, pp. 37–49, 1995. doi:10.1007/BF01784241
- M. Nielsen, G. Plotkin, and G. Winskel, "Petri Nets, Event Structures and Domains, Part I," Theoret. Comput. Sci., vol. 13, no. 1, pp. 85–108, 1981. doi:10.1016/0304-3975(81)90112-2
- S. Gilbert and N. Lynch, "Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services," ACM SIGACT News, vol. 33, no. 2, pp. 51–59, 2002. doi:10.1145/564585.564601