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.2020.33
URN: urn:nbn:de:0030-drops-128457
URL: https://drops.dagstuhl.de/opus/volltexte/2020/12845/
Go to the corresponding LIPIcs Volume Portal


Lanese, Ivan ; Medić, Doriana

A General Approach to Derive Uncontrolled Reversible Semantics

pdf-format:
LIPIcs-CONCUR-2020-33.pdf (0.7 MB)


Abstract

Reversible computing is a paradigm where programs can execute backward as well as in the usual forward direction. Reversible computing is attracting interest due to its applications in areas as different as biochemical modelling, simulation, robotics and debugging, among others. In concurrent systems the main notion of reversible computing is called causal-consistent reversibility, and it allows one to undo an action if and only if its consequences, if any, have already been undone. This paper presents a general and automatic technique to define a causal-consistent reversible extension for given forward models. We support models defined using a reduction semantics in a specific format and consider a causality relation based on resources consumed and produced. The considered format is general enough to fit many formalisms studied in the literature on causal-consistent reversibility, notably Higher-Order π-calculus and Core Erlang, an intermediate language in the Erlang compilation. Reversible extensions of these models in the literature are ad hoc, while we build them using the same general technique. This also allows us to show in a uniform way that a number of relevant properties, causal-consistency in particular, hold in the reversible extensions we build. Our technique also allows us to go beyond the reversible models in the literature: we cover a larger fragment of Core Erlang, including remote error handling based on links, which has never been considered in the reversibility literature.

BibTeX - Entry

@InProceedings{lanese_et_al:LIPIcs:2020:12845,
  author =	{Ivan Lanese and Doriana Medić},
  title =	{{A General Approach to Derive Uncontrolled Reversible Semantics}},
  booktitle =	{31st International Conference on Concurrency Theory (CONCUR 2020)},
  pages =	{33:1--33:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-160-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{171},
  editor =	{Igor Konnov and Laura Kov{\'a}cs},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12845},
  URN =		{urn:nbn:de:0030-drops-128457},
  doi =		{10.4230/LIPIcs.CONCUR.2020.33},
  annote =	{Keywords: Reversible computing, causality, process calculi, Erlang}
}

Keywords: Reversible computing, causality, process calculi, Erlang
Collection: 31st International Conference on Concurrency Theory (CONCUR 2020)
Issue Date: 2020
Date of publication: 26.08.2020


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