Abstract : We identify a general principle of distributed computing: one cannot force two processes running in parallel to see each other. This principle is formally stated in the context of asynchronous processes communicating through shared objects, using trace-based semantics. We prove that it holds in a reasonable computational model, and then study the class of concurrent specifications which satisfy this property. This allows us to derive a Galois connection theorem for different variants of linearizability.
Eric Goubault, Jérémy Ledent, Samuel Mimram. On the Impossibility of Detecting Concurrency. 32nd International Symposium on Distributed Computing (DISC 2018), 2018, New Orleans, United States. ⟨10.4230/LIPIcs.DISC.2018.50⟩. ⟨hal-02155495⟩