A parametric framework for reversible pi-calculi
File(s)ReversibleFramework.pdf (785.12 KB)
Accepted version
Author(s)
Medic, Doriana
Mezzina, Claudio Antares
Phillips, Iain
Yoshida, Nobuko
Type
Journal Article
Abstract
This paper presents a study of causality in a reversible, concurrent setting. There exist various notions of causality inπ-calculus, which differ in the treatment of parallel extrusions of the same name. Hence, by using a parametric way of bookkeeping the order and the dependencies among extruders it is possible to map different causal semantics into the same framework. Starting from this simple observation, we present a uniform framework forreversibleπ-calculi that is parametric with respect to a data structure that stores information about the extrusion of a name. Different data structures yield different approaches to the parallel extrusion problem. We map three well-known causal semantics into our framework. We prove causal-consistency for the three instances of our framework. Furthermore, we prove a causal correspondence between the appropriate instances of the framework and the Boreale-Sangiorgi semantics and an operational correspondence with the reversibleπ-calculus causal semantics.
Date Issued
2020-12-01
Date Acceptance
2020-10-30
Citation
Information and Computation, 2020, 275 (10)
ISSN
0890-5401
Publisher
Elsevier
Journal / Book Title
Information and Computation
Volume
275
Issue
10
Copyright Statement
© 2020 Elsevier Inc. All rights reserved. This manuscript is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International Licence http://creativecommons.org/licenses/by-nc-nd/4.0/
Sponsor
Engineering & Physical Science Research Council (E
Engineering & Physical Science Research Council (EPSRC)
Engineering & Physical Science Research Council (E
Engineering and Physical Sciences Research Council
Engineering & Physical Science Research Council (EPSRC)
Engineering & Physical Science Research Council (E
Engineering & Physical Science Research Council (EPSRC)
Engineering & Physical Science Research Council (EPSRC)
Engineering and Physical Sciences Research Council
Engineering & Physical Science Research Council (E
Grant Number
ERI 025567 (EP/K034413/1)
EP/K011715/1
PO 20131167
EP/L00058X/1, PO 20131167
EP/N027833/1
20103649
EP/T014709/1
EP/T006544/1
EP/V000462/1
EP/V000462/1
Subjects
Science & Technology
Technology
Physical Sciences
Computer Science, Theory & Methods
Mathematics, Applied
Computer Science
Mathematics
Causal semantics
pi-Calculus
Causally-consistent reversibility
SEMANTICS
Computation Theory & Mathematics
08 Information and Computing Sciences
Publication Status
Published
Article Number
ARTN 104644
Date Publish Online
2020-11-12