License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2016.32
URN: urn:nbn:de:0030-drops-61620
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6162/
Go to the corresponding LIPIcs Volume Portal

Castellan, Simon ; Clairambault, Pierre

Causality vs. Interleavings in Concurrent Game Semantics

pdf-format:
LIPIcs-CONCUR-2016-32.pdf (0.6 MB)

Abstract

We investigate relationships between interleaving and causal notions of game semantics for concurrent programming languages, focusing on the existence of canonical compact causal representations of the interleaving game semantics of programs.
We perform our study on an affine variant of Idealized Parallel Algol (IPA), for which we present two games model: and interleaving model (an adaptation of Ghica and Murawski’s fully abstract games model for IPA up to may-testing), and a causal model (a variant of Rideau and Winskel’s games on event structures). Both models are sound and adequate for affine IPA. Then, we relate the two models. First we give a causality-forgetting operation mapping functorially the causal model to the interleaving one. We show that from an interleaving strategy we can reconstruct a causal strategy, from which it follows that the interleaving model is the observational quotient of the causal one. Then, we investigate several reconstructions of causal strategies from interleaving ones, showing finally that there are programs which are inherently causally ambiguous, with several distinct minimal causal representations.

BibTeX - Entry

@InProceedings{castellan_et_al:LIPIcs:2016:6162,
  author =	{Simon Castellan and Pierre Clairambault},
  title =	{{Causality vs. Interleavings in Concurrent Game Semantics}},
  booktitle =	{27th International Conference on Concurrency Theory (CONCUR 2016)},
  pages =	{32:1--32:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-017-0},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{59},
  editor =	{Jos{\'e}e Desharnais and Radha Jagadeesan},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6162},
  URN =		{urn:nbn:de:0030-drops-61620},
  doi =		{10.4230/LIPIcs.CONCUR.2016.32},
  annote =	{Keywords: Game semantics, concurrency, causality, event structures}
}

Keywords: Game semantics, concurrency, causality, event structures
Collection: 27th International Conference on Concurrency Theory (CONCUR 2016)
Issue Date: 2016
Date of publication: 24.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI