New proof shows causality in shared-memory systems is fundamentally limited

In a new paper on arXiv, Rodríguez, Castañeda, and Piña tackle a fundamental challenge in concurrent computing: determining whether one operation truly happened before another. They formalize the Causal Observability Problem (COP) as assigning timestamps to invocation and response events that respect real-time order. Their key result is a proof that no strongly consistent solution—one that is both complete (never misses a genuine precedence) and sound (never reports a spurious one)—can exist at the observable boundary. They show that the placement of instrumentation events relative to operation boundaries dictates what a monitor can guarantee: internal placement yields completeness, external placement yields soundness, and neither achieves both.

To ground the theory, the authors implement three non-blocking Causal Monitor objects: FAInc (centralized atomic counter), Striped (decentralized counter), and Collect (iterative register snapshot). FAInc and Striped are linearizable; Collect is only quiescently consistent. Despite these internal consistency differences, all three provide identical COP guarantees—placement alone determines observable behavior. Empirical tests on a 64-core NUMA architecture reveal that Striped matches Collect in throughput while preserving linearizability, eliminating the cache-contention bottleneck of FAInc at high thread counts. This work has direct implications for debugging, verification, and monitoring of concurrent systems.