@inproceedings{3764a622074943209b5426ffd19dbf65,
title = "Brief announcement: 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.",
keywords = "Concurrent object, Concurrent specification, Linearizability",
author = "{\'E}ric Goubault and J{\'e}r{\'e}my Ledent and Samuel Mimram",
note = "Publisher Copyright: {\textcopyright} {\'E}ric Goubault and J{\'e}r{\'e}my Ledent and Samuel Mimram; 32nd International Symposium on Distributed Computing, DISC 2018 ; Conference date: 15-10-2018 Through 19-10-2018",
year = "2018",
month = oct,
day = "1",
doi = "10.4230/LIPIcs.DISC.2018.50",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Ulrich Schmid and Josef Widder",
booktitle = "32nd International Symposium on Distributed Computing, DISC 2018",
}