On the Limits of Causal Observation in Shared-Memory Systems
This work provides a fundamental impossibility result and practical guidance for designing monitoring systems in concurrent computing, clarifying the trade-off between completeness and soundness for causal observation.
The paper formalizes the Causal Observability Problem (COP) for shared-memory systems, proving that no timestamping scheme can be both complete and sound at the observable boundary. It demonstrates that instrumentation placement alone determines COP guarantees, independent of consistency models, and validates this with three implementations on a 64-core NUMA machine, showing that a decentralized counter (Striped) achieves high throughput while preserving linearizability.
Determining whether one concurrent operation completed before another began is a fundamental prerequisite for reasoning about the correctness of concurrent systems. We formalize this challenge as the Causal Observability Problem (COP): assign timestamps to the observable boundary events of a concurrent execution, invocations and responses, that faithfully reflect real-time operation order. A solution is complete if it never misses a genuine precedence, and sound if it never reports a spurious one. We prove that a strongly consistent solution, one that is simultaneously complete and sound, is unachievable at the observable boundary. We then show that the placement of instrumentation events relative to operation boundaries deterministically governs what a monitor can guarantee: internal placement yields completeness, external placement yields soundness, and neither achieves both. This dichotomy holds independently of the underlying timestamp mechanism. We instantiate this framework with three non-blocking implementations of a Causal Monitor object: FAInc (centralized atomic counter), Striped (decentralized counter), and Collect (iterative register snapshot). FAInc and Striped are linearizable; Collect is only quiescently consistent. Despite this internal consistency gap, we prove that all three provide identical COP guarantees: placement alone determines observable behavior. We validate these claims empirically on a 64-core NUMA architecture, showing that Striped matches Collect in throughput while preserving linearizability, resolving the cache-contention bottleneck of FAInc at high thread counts.