On the Impossibility of Detecting Concurrency

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.
Complete list of metadatas

Cited literature [11 references]  Display  Hide  Download

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

File

LIPIcs-DISC-2018-50.pdf
Files produced by the author(s)

Identifiers

Données associées

Collections

Citation

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⟩

Share

Metrics

Record views

56

Files downloads

242