Top

Published in:

2020 | OriginalPaper | Chapter

Towards Bridging Time and Causal Reversibility

Authors : Marco Bernardo, Claudio Antares Mezzina

Published in: Formal Techniques for Distributed Objects, Components, and Systems

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Causal consistent reversibility blends causality and reversibility. For a concurrent system, it says that an action can be undone provided this has no consequences, thereby making it possible to bring the system back to a past consistent state. Time reversibility is considered instead in the performance evaluation field. A continuous-time Markov chain is time reversible if its behavior remains the same when the direction of time is reversed. We try to bridge these two theories by showing the conditions under which both causal consistent reversibility and time reversibility can be achieved in the setting of a stochastic process algebra.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Strategy Synthesis for Autonomous Driving in a Moving Block Railway System with Uppaal Stratego

next chapter Defining and Verifying Durable Opacity: Correctness for Persistent Software Transactional Memory

Baeten, J.C.M., Verhoef, C.: A congruence theorem for structured operational semantics with predicates. In: Best, E. (ed.) CONCUR 1993. LNCS, vol. 715, pp. 477–492. Springer, Heidelberg (1993). https://doi.org/10.1007/3-540-57208-2_33CrossRef

Barylska, K., Koutny, M., Mikulski, L., Piatkowski, M.: Reversible computation vs. reversibility in Petri nets. Sci. Comput. Program. 151, 48–60 (2018)CrossRef

Bennett, C.H.: Logical reversibility of computations. IBM J. Res. Dev. 17, 525–532 (1973)MathSciNetCrossRef

Cristescu, I., Krivine, J., Varacca, D.: A compositional semantics for the reversible \(\pi \)-calculus. In: Proceedings of LICS 2013, pp. 388–397. IEEE-CS Press (2013)

Danos, V., Krivine, J.: Reversible communicating systems. In: Gardner, P., Yoshida, N. (eds.) CONCUR 2004. LNCS, vol. 3170, pp. 292–307. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-28644-8_19CrossRef

Danos, V., Krivine, J.: Transactions in RCCS. In: Abadi, M., de Alfaro, L. (eds.) CONCUR 2005. LNCS, vol. 3653, pp. 398–412. Springer, Heidelberg (2005). https://doi.org/10.1007/11539452_31CrossRef

Giachino, E., Lanese, I., Mezzina, C.A.: Causal-consistent reversible debugging. In: Gnesi, S., Rensink, A. (eds.) FASE 2014. LNCS, vol. 8411, pp. 370–384. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-54804-8_26CrossRef

Harrison, P.G.: Turning back time in Markovian process algebra. Theoret. Comput. Sci. 290(3), 1947–1986 (2003)MathSciNetCrossRef

Hillston, J.: The nature of synchronisation. In: Proceedings of PAPM 1994, pp. 51–70. University of Erlangen, Technical Report 27–4 (1994)

10.

Hillston, J.: A Compositional Approach to Performance Modelling. Cambridge University Press, Cambridge (1996)CrossRef

11.

Hoare, C.A.R.: Communicating Sequential Processes. Prentice Hall, Upper Saddle River (1985)MATH

12.

Jackson, J.R.: Jobshop-like queueing systems. Manage. Sci. 10(1), 131–142 (1963)CrossRef

13.

Kelly, F.P.: Reversibility and Stochastic Networks. Wiley, Chichester (1979)MATH

14.

Kemeny, J.G., Snell, J.L.: Finite Markov Chains. Van Nostrand, New York (1960)MATH

15.

Kleinrock, L.: Queueing Systems. Wiley, New York (1975)MATH

16.

Landauer, R.: Irreversibility and heat generated in the computing process. IBM J. Res. Dev. 5, 183–191 (1961)CrossRef

17.

Lanese, I., Lienhardt, M., Mezzina, C.A., Schmitt, A., Stefani, J.-B.: Concurrent flexible reversibility. In: Felleisen, M., Gardner, P. (eds.) ESOP 2013. LNCS, vol. 7792, pp. 370–390. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-37036-6_21CrossRef

18.

Lanese, I., Medić, D., Mezzina, C.A.: Static versus dynamic reversibility in CCS. Acta Informatica (2019)

19.

Lanese, I., Mezzina, C.A., Stefani, J.-B.: Reversing higher-order \(\pi \). In: Gastin, P., Laroussinie, F. (eds.) CONCUR 2010. LNCS, vol. 6269, pp. 478–493. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15375-4_33CrossRef

20.

Lanese, I., Nishida, N., Palacios, A., Vidal, G.: CauDEr: a causal-consistent reversible debugger for erlang. In: Gallagher, J.P., Sulzmann, M. (eds.) FLOPS 2018. LNCS, vol. 10818, pp. 247–263. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-90686-7_16CrossRef

21.

Lanese, I., Nishida, N., Palacios, A., Vidal, G.: A theory of reversibility for Erlang. J. Log. Algeb. Meth. Program. 100, 71–97 (2018)MathSciNetCrossRef

22.

Laursen, J.S., Ellekilde, L.P., Schultz, U.P.: Modelling reversible execution of robotic assembly. Robotica 36(5), 625–654 (2018)CrossRef

23.

Lévy, J.J.: An algebraic interpretation of the \(\lambda \beta \)K-calculus; and an application of a labelled \(\lambda \)-calculus. Theoret. Comput. Sci. 2(1), 97–114 (1976)MathSciNetCrossRef

24.

Lienhardt, M., Lanese, I., Mezzina, C.A., Stefani, J.-B.: A reversible abstract machine and its space overhead. In: Giese, H., Rosu, G. (eds.) FMOODS/FORTE -2012. LNCS, vol. 7273, pp. 1–17. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-30793-5_1CrossRef

25.

Marin, A., Rossi, S.: Quantitative analysis of concurrent reversible computations. In: Sankaranarayanan, S., Vicario, E. (eds.) FORMATS 2015. LNCS, vol. 9268, pp. 206–221. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-22975-1_14CrossRefMATH

26.

Milner, R.: Communication and Concurrency. Prentice Hall, Upper Saddle River (1989)MATH

27.

Perumalla, K.S., Park, A.J.: Reverse computation for rollback-based fault tolerance in large parallel systems - evaluating the potential gains and systems effects. Cluster Comput. 17(2), 303–313 (2014)CrossRef

28.

Phillips, I.C.C., Ulidowski, I.: Reversing algebraic process calculi. J. Logic Algeb. Program. 73(1–2), 70–96 (2007)MathSciNetCrossRef

29.

Phillips, I., Ulidowski, I., Yuen, S.: A reversible process calculus and the modelling of the ERK signalling pathway. In: Glück, R., Yokoyama, T. (eds.) RC 2012. LNCS, vol. 7581, pp. 218–232. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36315-3_18CrossRefMATH

30.

Michele Pinna, G.: Reversing steps in membrane systems computations. In: Gheorghe, M., Rozenberg, G., Salomaa, A., Zandron, C. (eds.) CMC 2017. LNCS, vol. 10725, pp. 245–261. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-73359-3_16CrossRefMATH

31.

Plateau, B.: On the stochastic structure of parallelism and synchronization models for distributed algorithms. In: Proceedings of SIGMETRICS 1985, pp. 147–154. ACM Press (1985)

32.

Schordan, M., Oppelstrup, T., Jefferson, D.R., Barnes Jr., P.D.: Generation of reversible C++ code for optimistic parallel discrete event simulation. New Gener. Comput. 36(3), 257–280 (2018)CrossRef

33.

Siljak, H., Psara, K., Philippou, A.: Distributed antenna selection for massive MIMO using reversing Petri nets. IEEE Wirel. Commun. Lett. 8(5), 1427–1430 (2019)CrossRef

34.

Stewart, W.J.: Introduction to the Numerical Solution of Markov Chains. Princeton University Press, Princeton (1994)MATH

35.

Vassor, M., Stefani, J.-B.: Checkpoint/rollback vs causally-consistent reversibility. In: Kari, J., Ulidowski, I. (eds.) RC 2018. LNCS, vol. 11106, pp. 286–303. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-99498-7_20CrossRef

36.

de Vries, E., Koutavas, V., Hennessy, M.: Communicating transactions. In: Gastin, P., Laroussinie, F. (eds.) CONCUR 2010. LNCS, vol. 6269, pp. 569–583. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15375-4_39CrossRef

Title: Towards Bridging Time and Causal Reversibility
Authors: Marco Bernardo
Claudio Antares Mezzina
Publisher: Springer International Publishing
Book: Formal Techniques for Distributed Objects, Components, and Systems
Print ISBN: 978-3-030-50085-6

Electronic ISBN: 978-3-030-50086-3

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-50086-3_2

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner