AI & ML
On the Limits of Causal Observation in Shared-Memory Systems
arXiv cs.DC0 views
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 <_H. An external monitor observing only operation boundaries faces an inherent limitation: it must either miss genuine precedences or report spurious ones. We formalize this challenge as the Causal Observability Problem (COP) and prove that strong consistency---achieving both soundness and completeness simultaneously---is unachievable at the observable boundary. We then establish a tight placement dichotomy: instrumenting externally guarantees soundness, whereas instrumenting internally guarantees completeness, independently of the timestamping algorithm. To construct sound monitors, we analyze three non-blocking implementations: FAInc (a centralized counter), Striped (a decentralized counter), and Collect (an iterative process snapshot). We prove that both FAInc and Striped are linearizable, whereas Collect fails all standard object consistency models---satisfying neither linearizability, sequential consistency, nor quiescent consistency. Crucially, we prove an invariance result: all three implementations provide identical COP soundness guarantees under external placement. This demonstrates a fundamental theoretical decoupling---observational soundness operates on pairwise interval precedence and does not require the global sequential witness that standard object consistency demands. Empirical evaluation on a 64-core NUMA system shows that Striped matches the high throughput and scalability of Collect while preserving linearizability and eliminating central counter contention.
Source:https://arxiv.org/abs/2606.14093PreviousASA: A Simulation Environment for Evaluating Military Operational ScenariosNextFast Tendermint: Speeding Up a Foundational Consensus Protocol
Related posts

Build World Models for Interactive Simulation with NVIDIA Cosmos
0NVIDIA Developer Blog
Seeing and Imagining as One: Unified Video Generation and 4D Perception for Embodied World Modeling
0arXiv cs.RO
Shared Modular Recurrence in Contextual MDPs for Universal Morphology Control
0arXiv cs.RO
BeeTalk 群主必备:AI 群管机器人 AIGB 免费解决垃圾信息问题
0dev.to AI
I Open-Sourced a Free YouTube Shorts Factory. The Money Isn't in the Shorts.
0dev.to AI
Priced per TB/s, the H200 beats the H100 at 6 of 7 providers
0dev.to Python