Causal reversibility in individual token interpretation of Petri Nets

• Autorzy: Benamira Adel

Identyfikatory

DOI

10.7494/csci.2020.21.4.3728

• Języki publikacji: EN

Abstrakty

EN

Causal reversibility in concurrent systems means that events that the origin of other events can only be undone after undoing its consequences. In opposition to backtracking, events that are independent of each other can be reversed in an arbitrary order; in other words, we have flexible reversibility with respect to a causality relationship. An implementation of individual token interpretation of Petri Nets (IPNs) has been proposed by Rob Van Glabbeek et al.; the present paper investigates a study of causal reversibility within IPNs. Given N as an IPN, by adding an intuitive firing rule to undo transitions according to the causality relationship, the coherence of N is assured; i.e., the set of all reachable states of N in the reversible version and that of the original one are identical. Furthermore, reversibility in N is flexible, and their initial state can be accessible in reverse from any state. In this paper, an approach for controlling causal-reversibility within IPNs is proposed.

Słowa kluczowe

EN

reversibility; concurrent systems; Petri Nets; causality

• Wydawca: Wydawnictwa AGH
• Czasopismo: Computer Science
• Rocznik: 2020
• Tom: T. 21 (4)
• Strony: 489--511
• Opis fizyczny: Bibliogr. 44 poz., rys.

Twórcy

autor

Benamira Adel

• 8 May 1945 Guelma University, Computer Science Department, BP-401, 24000, Guelma, Algeria

Bibliografia

• [1] Altenkirch T., Grattage J.: A functional quantum programming language. In: 20th IEEE Symposium on Logic in Computer Science (LICS 2005), 26–29 June 2005, Chicago, IL, USA, Proceedings, pp. 249–258, 2005. https://doi.org/10.110 9/LICS.2005.1.
• [2] Barylska K., Erofeev E., Koutny M., Mikulski L., Piątkowski M.: Reversing Transitions in Bounded Petri Nets, Fundamenta Informaticae, vol. 157(4), pp. 341– 357, 2018, https://doi.org/10.3233/FI-2018-1631.
• [3] Barylska K., Koutny M., Mikulski L., Piątkowski M.: Reversible Computation vs. Reversibility in Petri Nets. In: Devitt S., Lanese I. (eds.), Reversible Computation. RC 2016, Lecture Notes in Computer Science, vol. 9720, pp. 105–118, Springer, Cham, 2016. https://doi.org/10.1007/978-3-319-40578-0 7.
• [4] Barylska K., Koutny M., Mikulski L., Piątkowski M.: Reversible computation vs. reversibility in Petri nets, Science of Computer Programming, vol. 151, pp. 48–60, 2018. https://doi.org/10.1016/j.scico.2017.10.008.
• [5] Barylska K., Mikulski L., Piątkowski M., Koutny M., Erofeev E.: Reversing Transitions in Bounded Petri Nets. In: Proceedings of the 25th International Workshop on Concurrency, Specification and Programming, Rostock, Germany, September 28–30, 2016, pp. 74–85, 2016. http://ceur-ws.org/Vol-1698/CS&P2016 08 Baryl ska&Mikulski&Piatkowski&Koutny&Erofeev Reversing-Transitions-in-Bounde d-Petri-Nets.pdf.
• [6] Bednarczyk M.A.: Hereditary history preserving bisimulations or what is the power of the future perfect in program logics. Technical report, Institute of Computer Science, Polish Academy of Sciences, Gdansk, 1991.
• [7] Best E., Devillers R.R.: Sequential and concurrent behaviour in Petri net theory, Theoretical Computer Science, vol. 55(1), pp. 87–136, 1987, https://doi.org/10.1 016/0304-3975(87)90090-9.
• [8] Best E., Devillers R.R., Kiehn A., Pomello L.: Concurrent bisimulations in Petri nets, Acta Informatica, vol. 28(3), pp. 231–264, 1991, https://doi.org/10.1007/ BF01178506.
• [9] Cardelli L., Laneve C.: Reversible structures. In: CMSB’11: Proceedings of the 9th International Conference on Computational Methods in Systems Biology, pp. 131–140, 2011. https://doi.org/10.1145/2037509.2037529.
• [10] Clairambault P., Visme de M., Winskel G.: Concurrent Quantum Strategies. In: Thomsen M., Soeken M. (eds.), Reversible Computation. RC 2019, Lecture Notes in Computer Science, vol. 11497, pp. 3–19, Springer, Cham, 2019. https://doi.or g/10.1007/978-3-030-21500-2 1.
• [11] Clavel M., Duran F., Eker S., Lincoln P., Marti-Oliet N., Meseguer J., Quesada J.F.: Maude: specification and programming in rewriting logic, Theoretical Computer Science, vol. 285(2), pp. 187–243, 2002, https://doi.org/10.1016/S030 4-3975(01)00359-0.
• [12] Cook J.J.: Reverse Execution of Java Bytecode, The Computer Journal, vol. 45(6), pp. 608–619, 2002. https://doi.org/10.1093/comjnl/45.6.608.
• [13] Danos V., Krivine J.: Reversible Communicating Systems. In: Gardner P., Yoshida N. (eds.), CONCUR 2004 – Concurrency Theory. CONCUR 2004, Lecture Notes in Computer Science, vol. 3170, pp. 292–307, Springer, Berlin– Heidelberg, 2004. https://doi.org/10.1007/978-3-540-28644-8 19.
• [14] Danos V., Krivine J.: Transactions in RCCS. In: Abadi M., de Alfaro L. (eds.), CONCUR 2005 – Concurrency Theory. CONCUR 2005, Lecture Notes in Computer Science, vol. 3653, pp. 398–412, Springer, Berlin–Heidelberg, 2005. https: //doi.org/10.1007/11539452 31.
• [15] Danos V., Krivine J.: Formal Molecular Biology Done in CCS-R, Electronic Notes in Theoretical Computer Science, vol. 180(3), pp. 31–49, 2007, https://doi.org/ 10.1016/j.entcs.2004.01.040.
• [16] Danos V., Krivine J., Sobociński P.: General Reversibility, Electronic Notes in Theoretical Computer Science, vol. 175(3), pp. 75–86, 2007, https://doi.org/10.1 016/j.entcs.2006.07.036.
• [17] Danos V., Krivine J., Tarissan F.: Self-assembling Trees, Electronic Notes in Theoretical Computer Science, vol. 175(1), pp. 19–32, 2007, https://doi.org/10.1 016/j.entcs.2006.11.017.
• [18] Engelfriet J.: Branching processes of Petri nets, Acta Informatica, vol. 28(6), pp. 575–591, 1991, https://doi.org/10.1007/BF01463946.
• [19] Fecher H.: A completed hierarchy of true concurrent equivalences, Information Processing Letters, vol. 89(5), pp. 261–265, 2004, https://doi.org/10.1016/j.ipl. 2003.11.008.
• [20] Feldman S.I., Brown C.B.: IGOR: A system for program debugging via reversible execution, ACM SIGPLAN Notices, vol. 24(1), pp. 112–123, 1988. https://doi.or g/10.1145/68210.69226.
• [21] Frank M.P.: Physical Foundations of Landauer’s Principle. In: Kari J., Ulidowski I. (eds.), Reversible Computation. RC 2018, Lecture Notes in Computer Science, vol. 11106, pp. 3–33, Springer, Cham, 2018. https://doi.org/10.1 007/978-3-319-99498-7 1.
• [22] Glabbeek van R.J.: The Linear Time – Branching Time Spectrum I. In: Handbook of Process Algebra, pp. 3–99, 2001. https://doi.org/10.1016/b978-044482830-9/5 0019-9.
• [23] Glabbeek van R.J.: The Individual and Collective Token Interpretations of Petri Nets. In: Abadi M., de Alfaro L. (eds.), CONCUR 2005 – Concurrency Theory, Lecture Notes in Computer Science, vol. 3653, pp. 323–337, Springer, Berlin– Heidelberg, 2005. https://doi.org/10.1007/11539452 26.
• [24] Glabbeek van R.J., Goltz U., Schicke-Uffmann J.: On Distributability of Petri Nets. In: Birkedal L. (ed.), Foundations of Software Science and Computational Structures. FoSSaCS 2012, Lecture Notes in Computer Science, vol. 7213, pp. 331–345, Springer, Berlin–Heidelberg, 2012. https://doi.org/10.1007/978-3- 642-28729-9 22.
• [25] Goltz U., Reisig W.: The non-sequential behaviour of Petri nets, Information and Control, vol. 57(2–3), pp. 125–147, 1983. https://doi.org/10.1016/S0019-9958 (83)80040-0.
• [26] Hoey J., Ulidowski I.: Reversible Imperative Parallel Programs and Debugging. In: Thomsen M., Soeken M. (eds.), Reversible Computation. RC 2019, Lecture Notes in Computer Science, vol. 11497, pp. 108–127, Springer, Cham, 2019. https: //doi.org/10.1007/978-3-030-21500-2 7.
• [27] Krivine J.: A Verification Technique for Reversible Process Algebra. In: Reversible Computation, 4th International Workshop, RC 2012, Copenhagen, Denmark, July 2-3, 2012. Revised Papers, pp. 204–217, 2012. https://doi.org/10.1007/978-3-64 2-36315-3 17.
• [28] Landauer R.: Irreversibility and Heat Generation in the Computing Process, IBM Journal of Research and Development, vol. 5(3), pp. 183–191, 1961, https://doi. org/10.1147/rd.53.0183.
• [29] Lanese I., Lienhardt M., Mezzina C.A., Schmitt A., Stefani J.-B.: Concurrent Flexible Reversibility. In: Felleisen M., Gardner P. (eds.), Programming Languages and Systems. ESOP 2013. Lecture Notes in Computer Science, vol. 7792, pp. 370–390, Springer, Berlin, Heidelberg, 2013. https://doi.org/10.1007/978-3- 642-37036-6 21.
• [30] Lanese I., Mezzina C.A., Schmitt A., Stefani J.-B.: Controlling Reversibility in Higher-Order Pi. In: Katoen J.P., K¨onig B. (eds.), CONCUR 2011 – Concurrency Theory, Lecture Notes in Computer Science, vol. 6901, pp. 297–311, Springer, Berlin–Heidelberg, 2011. https://doi.org/10.1007/978-3-642-23217-6 20.
• [31] Lanese I., Mezzina C.A., Stefani J.-B.: Controlled Reversibility and Compensations. In: Gl¨uck R., Yokoyama T. (eds.), Reversible Computation. RC 2012, Lecture Notes in Computer Science, vol. 7581, pp. 233–240, Springer, Berlin– Heidelberg, 2012. https://doi.org/10.1007/978-3-642-36315-3 19.
• [32] Lanese I., Nishida N., Palacios A., Vidal G.: CauDEr: A Causal-Consistent Reversible Debugger for Erlang. In: Gallagher J., Sulzmann M. (eds.), Functional and Logic Programming. FLOPS 2018, Lecture Notes in Computer Science, vol. 10818, pp. 247–263, Springer, Cham, 2018. https://doi.org/10.1007/978- 3-319-90686-7 16.
• [33] Lanese I., Palacios A., Vidal G.: Causal-Consistent Replay Debugging for Message Passing Programs. In: P´erez J., Yoshida N. (eds.), Formal Techniques for Distributed Objects, Components, and Systems. FORTE 2019, Lecture Notes in Computer Science, vol. 11535, pp. 167–184, Springer, Cham, 2019. https: //doi.org/10.1007/978-3-030-21759-4 10.
• [34] Leeman G.B.: A formal approach to undo operations in programming languages, ACM Transactions on Programming Languages and Systems, vol. 8(1), pp. 50–87, 1986, https://doi.org/10.1145/5001.5005.
• [35] Mazurkiewicz A.W.: Trace theory. In: Brauer W., Reisig W., Rozenberg G. (eds.), Petri Nets: Applications and Relationships to Other Models of Concurrency. ACPN 1986, Lecture Notes in Computer Science, vol. 255, pp. 279–324, Springer, Berlin–Heidelberg, 1986. https://doi.org/10.1007/3-540-17906-2 30.
• [36] Mazurkiewicz A.W.: Basic notions of trace theory. In: de Bakker J.W., de Roever W.P., Rozenberg G. (eds.), Linear Time, Branching Time and Partial Order in Logics and Models for Concurrency. REX 1988, Lecture Notes in Computer Science, vol. 354, pp. 285–363, Springer, Berlin–Heidelberg, 1988. https://doi.or g/10.1007/BFb0013025.
• [37] Philippou A., Psara K., Siljak H.: Controlling Reversibility in Reversing Petri Nets with Application to Wireless Communications, CoRR, vol. abs/1905.11958, 2019. http://arxiv.org/abs/1905.11958.
• [38] Phillips I., Ulidowski I.: A Logic with Reverse Modalities for History-preserving Bisimulations. In: Proceedings 18th International Workshop on Expressiveness in Concurrency, EXPRESS 2011, Aachen, Germany, 5th September 2011, pp. 104–118, 2011. https://doi.org/10.4204/EPTCS.64.8.
• [39] Phillips I., Ulidowski I.: Reversibility and asymmetric conflict in event structures, The Journal of Logic and Algebraic Programming, vol. 84(6), pp. 781–805, 2015. https://doi.org/10.1016/j.jlamp.2015.07.004.
• [40] Phillips I., Ulidowski I., Yuen S.: A Reversible Process Calculus and the Modelling of the ERK Signalling Pathway. In: Gl¨uck R., Yokoyama T. (eds.), Reversible Computation. RC 2012, Lecture Notes in Computer Science, vol. 7581, pp. 218–232, Springer, Berlin–Heidelberg, 2012. https://doi.org/10.1007/978-3- 642-36315-3 18.
• [41] Phillips I., Ulidowski I.: Reversing algebraic process calculi, The Journal of Logic and Algebraic Programming, vol. 73(1–2), pp. 70–96, 2007. https://doi.org/10.1 016/j.jlap.2006.11.002.
• [42] Soloveichik D., Seelig G., Winfree E.: DNA as a universal substrate for chemical kinetics. In: Goel A., Simmel F.C., Sosik P (eds.), DNA Computing. DNA 2008, Lecture Notes in Computer Science, vol. 5347, pp. 57-69, Springer, Berlin-Heidelberg, pp. 57-69, 2008. https://doi.org/10.1007/978-3-642-03076-5-6.
• [43] Ulidowski I., Phillips I., Yuen S.: Concurrency and Reversibility. In: Yamashita S., Minato S. (eds.), Reversible Computation. RC 2014, Lecture Notes in Computer Science, vol. 8507, pp. 1–14, Springer, Cham, 2014. https://doi.org/10.1007/97 8-3-319-08494-7 1.
• [44] Zelkowitz M.V.: Reversible Execution, Communications of the ACM, vol. 16(9), p. 566, 1973. https://doi.org/10.1145/362342.362360.