Reversible Computation in Petri Nets

Abstract

Reversible computation is an unconventional form of computing where any executed sequence of operations can be executed in reverse at any point during computation. In this paper we propose a reversible approach to Petri nets by introducing machinery and associated operational semantics to tackle the challenges of the three main forms of reversibility, namely, backtracking, causal reversing and out-of-causal-order reversing. Our proposal concerns a variation of Petri nets where tokens are persistent and are distinguished from each other by an identity. Our design decisions are influenced by applications in biochemistry but the methodology can be applied to a wide range of problems that feature reversibility. We demonstrate the applicability of our approach with an example of a biochemical system and an example of a transaction-processing system both featuring reversible behaviour.