Causal-Consistent Replay Reversible Semantics for Message Passing Concurrent Programs

• Autorzy: Lanese Ivan , Palacios Adrián , Vidal Germán

Identyfikatory

DOI

10.3233/FI-2021-2005

• Języki publikacji: EN

Abstrakty

EN

Causal-consistent reversible debugging is an innovative technique for debugging concurrent systems. It allows one to go back in the execution focusing on the actions that most likely caused a visible misbehavior. When such an action is selected, the debugger undoes it, including all and only its consequences. This operation is called a causal-consistent rollback. In this way, the user can avoid being distracted by the actions of other, unrelated processes. In this work, we introduce its dual notion: causal-consistent replay. We allow the user to record an execution of a running program and, in contrast to traditional replay debuggers, to reproduce a visible misbehavior inside the debugger including all and only its causes. Furthermore, we present a unified framework that combines both causal-consistent replay and causal-consistent rollback. Although most of the ideas that we present are rather general, we focus on a popular functional and concurrent programming language based on message passing: Erlang.

Słowa kluczowe

EN

concurrency; logging; causal consistent; debugging; reversible computing

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 178, nr 3
• Strony: 229--266
• Opis fizyczny: Bibliogr. 35 poz.

Twórcy

autor

Lanese Ivan

• Focus Team, University of Bologna/INRIA, Mura Anteo Zamboni, 7, Bologna, Italy

autor

Palacios Adrián

• MiST, VRAIN, Universitat Politècnica de València, Camino de Vera, S/N, 46022 Valencia, Spain

autor

Vidal Germán

• MiST, VRAIN, Universitat Politècnica de València, Camino de Vera, S/N, 46022 Valencia, Spain

Bibliografia

• [1] Undo Software. Increasing software development productivity with reversible debugging, 2014. URL https://undo.io/media/uploads/files/Undo_ReversibleDebugging_Whitepaper.pdf.
• [2] Britton T, Jeng L, Carver G, Cheak P, Katzenellenbogen T. Reversible Debugging software - Quantify the time and cost saved using reversible debuggers. http://www.roguewave.com, 2012.
• [3] Sutter H. The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software. Dr. Dobbs Journal, 2005. 30(3).
• [4] Huang J, Zhang C. Debugging Concurrent Software: Advances and Challenges. J. Comput. Sci. Technol., 2016. 31(5):861-868.
• [5] Giachino E, Lanese I, Mezzina CA. Causal-Consistent Reversible Debugging. In: Gnesi S, Rensink A (eds.), Proceedings of the 17th International Conference on Fundamental Approaches to Software Engineering (FASE 2014), volume 8411 of Lecture Notes in Computer Science. Springer, 2014 pp. 370-384.
• [6] Lanese I, Mezzina CA, Schmitt A, Stefani J. Controlling Reversibility in Higher-Order Pi. In: Katoen J, König B (eds.), Proceedings of the 22nd International Conference on Concurrency Theory (CONCUR 2011), volume 6901 of Lecture Notes in Computer Science. Springer, 2011 pp. 297-311.
• [7] Lanese I, Nishida N, Palacios A, Vidal G. CauDEr: A Causal-Consistent Reversible Debugger for Erlang (system description). In: Gallagher JP, Sulzmann M (eds.), Proceedings of the 14th International Symposium on Functional and Logic Programming (FLOPS’18), volume 10818 of Lecture Notes in Computer Science. Springer, 2018 pp. 247-263.
• [8] Cesarini F, Thompson S. Erlang Programming - A Concurrent Approach to Software Development. O’Reilly, 2009. ISBN 978-0-596-51818-9.
• [9] Letuchy E. Erlang at Facebook. http://www.erlang-factory.com/conference/SFBayAreaErlangFactory2009/speakers/EugeneLetuchy, 2009.
• [10] Lienhardt M, Lanese I, Mezzina CA, Stefani JB. A Reversible Abstract Machine and Its Space Overhead. In: Giese H, Rosu G (eds.), Proceedings of the Joint 14th IFIP WG International Conference on Formal Techniques for Distributed Systems (FMOODS 2012) and the 32nd IFIP WG 6.1 International Conference (FORTE 2012), volume 7273 of Lecture Notes in Computer Science. Springer, 2012 pp. 1-17.
• [11] Giachino E, Lanese I, Mezzina CA, Tiezzi F. Causal-consistent rollback in a tuple-based language. J. Log. Algebr. Meth. Program., 2017. 88:99-120.
• [12] Lanese I, Nishida N, Palacios A, Vidal G. A Theory of Reversibility for Erlang. Journal of Logical and Algebraic Methods in Programming, 2018. 100:71-97.
• [13] Svensson H, Fredlund LA, Earle CB. A unified semantics for future Erlang. In: 9th ACM SIGPLAN workshop on Erlang. ACM, 2010 pp. 23-32.
• [14] Nishida N, Palacios A, Vidal G. A Reversible Semantics for Erlang. In: Hermenegildo M, López-García P (eds.), Proceedings of the 26th International Symposium on Logic-Based Program Synthesis and Transformation (LOPSTR 2016), volume 10184 of Lecture Notes in Computer Science. Springer, 2017 pp. 259-274.
• [15] Carlsson R, Gustavsson B, Johansson E, Lindgren T, Nyström SO, Pettersson M, Virding R. Core Erlang 1.0.3. Language specification, 2004. Available from URL: https://www.it.uu.se/research/group/hipe/cerl/doc/core_erlang-1.0.3.pdf.
• [16] Lanese I, Palacios A, Vidal G. Causal-Consistent Replay Debugging for Message Passing Programs. In: Pérez JA, Yoshida N (eds.), Proceedings of the 39th IFIP WG 6.1 International Conference on Formal Techniques for Distributed Objects, Components, and Systems (FORTE 2019), volume 11535 of Lecture Notes in Computer Science. Springer, 2019 pp. 167-184.
• [17] Lanese I, Palacios A, Vidal G. Causal-Consistent Replay Reversible Semantics for Message Passing Concurrent Programs. Technical report, DSIC, Universitat Politècnica de València, 2019. URL http://personales.upv.es/~gvidal/german/fi/paper.pdf.
• [18] Frequently Asked Questions about Erlang. Available at http://erlang.org/faq/academic.html, 2018.
• [19] Netzer RH, Miller BP. Optimal tracing and replay for debugging message-passing parallel programs. The Journal of Supercomputing, 1995. 8(4):371-388.
• [20] Lamport L. Time, Clocks, and the Ordering of Events in a Distributed System. Commun. ACM, 1978. 21(7):558-565.
• [21] Mazurkiewicz AW. Trace Theory. In: Brauer W, Reisig W, Rozenberg G (eds.), Petri Nets: Central Models and Their Properties, Advances in Petri Nets 1986, Part II, Proceedings of an Advanced Course, 1986, volume 255 of Lecture Notes in Computer Science. Springer, 1987 pp. 279-324.
• [22] Lanese I, Mezzina CA, Tiezzi F. Causal-Consistent Reversibility. Bulletin of the EATCS, 2014. 114.
• [23] Landauer R. Irreversibility and heat generation in the computing process. IBM Journal of Research and Development, 1961. 5:183-191.
• [24] Matsuda K, Hu Z, Nakano K, Hamana M, Takeichi M. Bidirectionalization transformation based on automatic derivation of view complement functions. In: Hinze R, Ramsey N (eds.), Proc. of the 12th ACM SIGPLAN International Conference on Functional Programming, ICFP 2007. ACM, 2007 pp. 47-58.
• [25] Nishida N, Palacios A, Vidal G. Reversible Term Rewriting. In: Kesner D, Pientka B (eds.), Proceedings of the 1st International Conference on Formal Structures for Computation and Deduction (FSCD 2016), volume 52 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016 pp. 28:1-28:18.
• [26] Thomsen MK, Axelsen HB. Interpretation and programming of the reversible functional language RFUN. In: Proc. of the 27th International Symposium on Implementation and Application of Functional Languages (IFL 2015). ACM, 2016 pp. 8:1 - 8:13.
• [27] Danos V, Krivine J. Reversible Communicating Systems. In: CONCUR, volume 3170 of LNCS. Springer, 2004 pp. 292-307.
• [28] Lanese I, Nishida N, Palacios A, Vidal G. CauDEr website. URL: https://github.com/mistupv/cauder, 2018.
• [29] Shibanai K, Watanabe T. Actoverse: A Reversible Debugger for Actors. In: AGERE. ACM, 2017 pp. 50-57.
• [30] Aumayr D, Marr S, Béra C, Boix EG, Mössenböck H. Efficient and deterministic record & replay for actor languages. In: Tilevich E, Mössenböck H (eds.), Proceedings of the 15th International Conference on Managed Languages & Runtimes (ManLang 2018). ACM, 2018 pp. 15:1-15:14.
• [31] Chen Y, Zhang S, Guo Q, Li L, Wu R, Chen T. Deterministic Replay: A Survey. ACM Comput. Surv., 2015. 48(2):17:1-17:47.
• [32] Maruyama M, Tsumura T, Nakashima H. Parallel Program Debugging based on Data-Replay. In: Zheng SQ (ed.), Proceedings of the IASTED International Conference on Parallel and Distributed Computing and Systems (PDCS 2005). IASTED/ACTA Press, 2005 pp. 151-156.
• [33] Perera R, Garg D, Cheney J. Causally Consistent Dynamic Slicing. In: Desharnais J, Jagadeesan R (eds.), CONCUR, volume 59 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016 pp. 18:1-18:15.
• [34] Ziarek L, Schatz P, Jagannathan S. Stabilizers: a modular checkpointing abstraction for concurrent functional programs. In: Reppy JH, Lawall JL (eds.), Proceedings of the 11th ACM SIGPLAN International Conference on Functional Programming, ICFP 2006, Portland, Oregon, USA, September 16-21, 2006. ACM, 2006 pp. 136-147.
• [35] Field J, Varela CA. Transactors: a programming model for maintaining globally consistent distributed state in unreliable environments. In: Palsberg J, Abadi M(eds.), Proceedings of the 32nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL 2005). ACM, 2005 pp. 195-208.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).