262,379 research outputs found
Static vs Dynamic SAGAs
No full textSAGAs calculi (or simply SAGAs) have been proposed by Bruni et al. as a model for long-running transactions. The approach therein can be considered static, while a dynamic approach has been proposed by Lanese and Zavattaro. In this paper we first extend both static SAGAs (in the centralized interruption policy) and dynamic SAGAs to deal with nesting, then we compare the two approaches
Forward-reverse observational equivalences in CCSK
No full textIn the context of CCSK, a reversible extension of CCS, we study observational equivalences that distinguish forward moves from backward ones. We present a refinement of the notion of forward-reverse bisimilarity and show that it coincides with a notion of forward-reverse barbed congruence. We also show a set of sound axioms allowing one to reason equationally on process equivalences
Mapping fusion and synchronized hyperedge replacement into logic programming
No full textIn this paper we compare three different formalisms that can be used in the area of models for distributed, concurrent and mobile systems. In particular we analyze the relationships between a process calculus, the Fusion Calculus, graph transformations in the Synchronized Hyperedge Replacement with Hoare synchronization (HSHR) approach and logic programming. We present a translation from Fusion Calculus into HSHR (whereas Fusion Calculus uses Milner synchronization) and prove a correspondence between the reduction semantics of Fusion Calculus and HSHR transitions. We also present a mapping from HSHR into a transactional version of logic programming and prove that there is a full correspondence between the two formalisms. The resulting mapping from Fusion Calculus to logic programming is interesting since it shows the tight analogies between the two formalisms, in particular for handling name generation and mobility. The intermediate step in terms of HSHR is convenient since graph transformations allow for multiple, remote synchronizations, as required by Fusion Calculus semantics
Parametric synchronizations in mobile nominal calculi
No full textWe present and compare P-PRISMA and F-PRISMA, two parametric calculi that can be instantiated with different interaction policies, defined as synchronization algebras with mobility of names (SAMs). In particular, P-PRISMA is based on name transmission (P-SAM), like pi-calculus, and thus exploits directional (input-output) communication only, while F-PRISMA is based on name fusion (F-SAM), like Fusion calculus, and thus exploits a more symmetric form of communication. However, P-PRISMA and F-PRISMA can easily accommodate many other high-level synchronization mechanisms than the basic ones available in pi-calculus and Fusion, hence allowing for the development of a general meta-theory of mobile calculi. We define for both the labeled operational semantics and a form of strong bisimilarity, showing that the latter is compositional for any SAM. We also discuss reduction semantics and weak bisimilarity. We give several examples based on heterogeneous SAMs, we investigate the case studies of pi-calculus and Fusion calculus giving correspondence theorems, and we show how P-PRISMA can be encoded in F-PRISMA. Finally, we show that basic categorical tools can help to relate and to compose SAMs and PRISMA processes in an elegant way
Tallulah, a Tool to Support the Axiomatic Approach to Causal-Consistent Reversibility
No full textThe axiomatic approach to causal-consistent reversibility allows one to prove relevant properties of concurrent reversible formalisms, such as causal consistency, causal safety and causal liveness, by checking a few simple axioms. The approach works on Labeled Transition Systems equipped with a notion of Independence (LTSIs). Even if the axioms are quite simple, verifying them on non-trivial LTSIs is time consuming and involves a few subtleties. We present Tallulah, a tool which allows one to automatically verify various axioms on concrete LTSIs, suggests how to patch the LTSI when some axiom does not hold, and colors the transitions to highlight when they belong to the same event
A general approach to derive uncontrolled reversible semantics
No full textReversible 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
Reversible Debugging of Erlang Programs in CauDEr
No full textThis talk presents the notion of causal-consistent reversible debugging and its instance on Erlang provided by CauDEr. Reversible debugging allows us to explore an execution back and forth looking for a bug. Causal-consistent debugging tailors this approach to concurrent systems so that actions can be undone in any order as long as their consequences, if any, are undone first
Reversible Computing in Debugging of Erlang Programs
No full textReversible computation is a computing paradigm where execution can progress backward as well as in the usual, forward direction. It has found applications in many areas of computer science, such as circuit design, programing languages, simulation, modeling of biochemical reactions, debugging, and robotics. In this article, we give an overview of reversible computation focusing on its use in reversible debugging of concurrent programs written in the Erlang programing language
Reversible Execution for Robustness in Embodied AI and Industrial Robots
No full textReversible computation is a computing paradigm where execution can progress backward as well as in the usual, forward direction. It has found applications in many areas of computer science, such as circuit design, programming languages, simulation, modeling of chemical reactions, debugging, and robotics. In this article, we give an overview of reversible computation focusing on its use in robotics. We present an example of programming industrial robots for assembly operations where we combine classical AI planning with reversibility and embodied AI to increase the robustness and versatility of industrial robots
PRISMA: A mobile calculus with parameterized synchronization
No full textWe present PRISMA, a parametric calculus that can be instantiated with different interaction policies, defined as synchronization algebras with mobility of names (SAMs). We define both operational semantics and observational semantics of PRISMA, showing that the second one is compositional for any SAM. We give examples based on heterogeneous SAMs, a case study on Fusion Calculus and some simple applications. Finally, we show that basic categorical tools can help to relate and to compose SAMs and PRISMA processes in an elegant way
- …
