Concurrency, Causality, Reversibility

Irek Ulidowsky (Leicester)

We present several models of concurrent computation including process calculi, which belong to interleaving models, and events structures, which are an example of the so-called true concurrency models. A particular attention is paid to representing such phenomena as causality and conflict, and how they are represented in different models. We then introduce the notion of reversing a computation, discuss briefly its history, motivation, and list main application areas of reversible computation. We demonstrate that reversibility bridges a "gap" between the interleaving and true concurrency models. On the one hand we show that, for example, true concurrency equivalences can be characterised naturally by interleaving bisimulations or modal logics provided that we have reversibility in the interleaving model. On the other hand, we can talk directly about, for example, true concurrency's causality in the interleaving models again if we have reversibility. We look also at reachability in computation where processes execute both forwards and in reverse.

References

1. Irek Ulidowski, MGS 2014 Lecture Slides: Part 1 and Part 2. Also, Part 1 handouts and Part 2 handouts.
2. Iain Phillips and Irek Ulidowski, An Event Identifier Logic. Mathematical Structures in Computer Science. doi:10.1017/S0960129513000510
3. Iain Phillips and Irek Ulidowski, Reversibility and asymmetric conflict in event structures. Proceedings of CONCUR 2013, LNCS, volume 8052, pp. 303-318. Springer, 2013. doi:10.1007/978-3-642-40184-8_22
4. Iain Phillips , Irek Ulidowski and Shoji Yuen, Modelling of bonding with processes and events. Proceedings, Reversible Computation 2013, LNCS, volume 7948, pp. 141-154. Springer, 2013.
5. Iain Phillips and Irek Ulidowski, A Hierarchy of Reverse Bisimulations on Stable Configuration Structures. Mathematical Structures in Computer Science, 22, pp 333-372, 2012. doi: 10.1017/S0960129511000429.
6. Iain Phillips and Irek Ulidowski, A Logic with Reverse Modalities for Hierarchy-preserving Bisimulations. Proceedings, 18th International Workshop on Expressiveness of Concurrency, EXPRESS'11, Aachen, Germany, September 2011. EPTCS, volume 64, 2011, pp. 104-118. doi:10.4204/EPTCS.64.8.
7. I. Phillips and I. Ulidowski, Reversing Algebraic Process Calculi. The Journal of Logic and Algebraic Programming, 73, pp 70-96, 2007. doi:10.1016/j.jlap.2006.11.002