On the Limits of Causal Observation in Shared-Memory Systems

arXiv:2606.14093v2 Announce Type: replace Abstract: Reasoning about concurrent system correctness requires detecting real-time operation precedence (<_h in asynchronous shared-memory systems real-time precedence and information-flow causality diverge rendering causality-tracking techniques like vector clocks incapable of recovering an external monitor observing operation boundaries faces inherent limitation: it must either miss genuine precedences or report spurious we formalize this challenge as the causal observability problem prove that strong consistency---achieving both soundness completeness simultaneously---is unachievable at observable boundary. then establish a tight placement dichotomy: instrumenting externally guarantees whereas internally independently timestamping algorithm. to construct sound monitors analyze three non-blocking implementations: fainc centralized counter striped decentralized collect iterative process snapshot are linearizable fails all standard object consistency models---satisfying neither linearizability sequential nor quiescent consistency. crucially invariance result: implementations provide identical cop under placement. demonstrates fundamental theoretical decoupling---observational operates pairwise interval does not require global witness demands. empirical evaluation numa system shows matches high throughput scalability while preserving eliminating central contention.>