Skip to Main content Skip to Navigation
Conference papers

Explicit Identifiers and Contexts in Reversible Concurrent Calculus

Clément Aubert 1 Doriana Medić 2 
2 FOCUS - Foundations of Component-based Ubiquitous Systems
CRISAM - Inria Sophia Antipolis - Méditerranée , DISI - Dipartimento di Informatica - Scienza e Ingegneria [Bologna]
Abstract : Existing formalisms for the algebraic specification and representation of networks of reversible agents suffer some shortcomings. Despite multiple attempts, reversible declensions of the Calculus of Communicating Systems (CCS) do not offer satisfactory adaptation of notions usual in "forward-only" process algebras, such as replication or context. Existing formalisms disallow the "hot-plugging" of processes during their execution in contexts with their own past. They also assume the existence of "eternally fresh" keys or identifiers that, if implemented poorly, could result in unnecessary bottlenecks and look-ups involving all the threads. In this paper, we begin investigating those issues, by first designing a process algebra endowed with a mechanism to generate identifiers without the need to consult with the other threads. We use this calculus to recast the possible representations of non-determinism in CCS, and as a byproduct establish a simple and straightforward definition of concurrency. Our reversible calculus is then proven to satisfy expected properties. We also observe that none of the reversible bisimulations defined thus far are congruences under our notion of "reversible" contexts.
Document type :
Conference papers
Complete list of metadata
Contributor : Doriana Medic Connect in order to contact the contributor
Submitted on : Tuesday, July 27, 2021 - 11:37:32 AM
Last modification on : Tuesday, February 15, 2022 - 5:11:39 PM
Long-term archiving on: : Thursday, October 28, 2021 - 6:20:20 PM


Files produced by the author(s)




Clément Aubert, Doriana Medić. Explicit Identifiers and Contexts in Reversible Concurrent Calculus. RC 2021 - 13th International Conference on Reversible Computation, Jul 2021, Nagoya / Virtual, Japan. ⟨10.1007/978-3-030-79837-6_9⟩. ⟨hal-03300726⟩



Record views


Files downloads