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.
https://hal.inria.fr/hal-02155495
Contributor : Samuel Mimram
<>
Submitted on : Thursday, June 13, 2019 - 4:08:29 PM
Last modification on : Saturday, June 15, 2019 - 1:17:57 AM
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⟩
