Nothing Special   »   [go: up one dir, main page]

skip to main content
research-article
Open access

Reasoning about distributed reconfigurable systems

Published: 31 October 2022 Publication History

Abstract

This paper presents a Hoare-style calculus for formal reasoning about reconfiguration programs of distributed systems. Such programs create and delete components and/or interactions (connectors) while the system components change state according to their internal behaviour. Our proof calculus uses a resource logic, in the spirit of Separation Logic, to give local specifications of reconfiguration actions. Moreover, distributed systems with an unbounded number of components are described using inductively defined predicates. The correctness of reconfiguration programs relies on havoc invariants, that are assertions about the ongoing interactions in a part of the system that is not affected by the structural change caused by the reconfiguration. We present a proof system for such invariants in an assume/rely-guarantee style. We illustrate the feasibility of our approach by proving the correctness of real-life distributed systems with reconfigurable (self-adjustable) tree architectures.

References

[1]
Parosh Aziz Abdulla, Giorgio Delzanno, Noomene Ben Henda, and Ahmed Rezine. 2007. Regular Model Checking Without Transducers (On Efficient Verification of Parameterized Systems). In Tools and Algorithms for the Construction and Analysis of Systems, 13th International Conference, TACAS 2007, Orna Grumberg and Michael Huth (Eds.) (LNCS, Vol. 4424). Springer, 721–736.
[2]
C. Aiswarya, Benedikt Bollig, and Paul Gastin. 2015. An Automata-Theoretic Approach to the Verification of Distributed Algorithms. In 26th International Conference on Concurrency Theory, CONCUR 2015, Madrid, Spain, September 1.4, 2015, Luca Aceto and David de Frutos-Escrig (Eds.) (LIPIcs, Vol. 42). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 340–353. https://doi.org/10.4230/LIPIcs.CONCUR.2015.340
[3]
C. I. Arad. 2013. Programming Model and Protocols for Reconfigurable Distributed Systems. Ph.D. Dissertation. KTH Royal Institute of Technology.
[4]
Farhad Arbab. 2004. Reo: A Channel-Based Coordination Model for Component Composition. Mathematical. Structures in Comp. Sci., 14, 3 (2004), June, 329–366. issn:0960-1295 https://doi.org/10.1017/S0960129504004153
[5]
Yehoshua Bar-Hillel, Micha Perles, and Eli Shamir. 1961. On Formal Properties of Simple Phrase Structure Grammars. Sprachtypologie und Universalienforschung, 14 (1961), 143–172.
[6]
Ananda Basu, Marius Bozga, and Joseph Sifakis. 2006. Modeling Heterogeneous Real-time Components in BIP. In Fourth IEEE International Conference on Software Engineering and Formal Methods (SEFM 2006). IEEE Computer Society, 3–12.
[7]
Roderick Bloem, Swen Jacobs, Ayrat Khalimov, Igor Konnov, Sasha Rubin, Helmut Veith, and Josef Widder. 2015. Decidability of Parameterized Verification. Morgan & Claypool Publishers.
[8]
Benedikt Bollig, Patricia Bouyer, and Fabian Reiter. 2019. Identifiers in Registers. In Foundations of Software Science and Computation Structures, Mikoł aj Bojańczyk and Alex Simpson (Eds.). 11425, Springer International Publishing, Cham. 115–132. isbn:978-3-030-17127-8
[9]
Marius Bozga, Lucas Bueri, and Radu Iosif. 2022. Decision Problems in a Logic for Reasoning about Reconfigurable Distributed Systems. In International Joint Conference on Automated Reasoning (IJCAR 2022), to appear.
[10]
Marius Bozga, Lucas Bueri, and Radu Iosif. 2022. On an Invariance Problem for Parameterized Concurrent Systems. In 33rd International Conference on Concurrency Theory (CONCUR 2022), to appear.
[11]
Marius Bozga, Javier Esparza, Radu Iosif, Joseph Sifakis, and Christoph Welzel. 2020. Structural Invariants for the Verification of Systems with Parameterized Architectures. In Tools and Algorithms for the Construction and Analysis of Systems - 26th International Conference, TACAS 2020 (LNCS, Vol. 12078). Springer, 228–246.
[12]
Marius Bozga and Radu Iosif. 2021. Specification and Safety Verification of Parametric Hierarchical Distributed Systems. In Formal Aspects of Component Software - 17th International Conference, FACS 2021, Virtual Event, October 28-29, 2021, Proceedings (Lecture Notes in Computer Science, Vol. 13077). Springer, 95–114.
[13]
Marius Bozga, Radu Iosif, and Joseph Sifakis. 2021. Verification of Component-based Systems with Recursive Architectures. CoRR, abs/2112.08292 (2021), arXiv:2112.08292. arxiv:2112.08292
[14]
Jeremy S. Bradbury, James R. Cordy, Juergen Dingel, and Michel Wermelinger. 2004. A survey of self-management in dynamic software architecture specifications. In Proceedings of the 1st ACM SIGSOFT workshop on Self-managed systems. 28–33.
[15]
Stephen Brookes and Peter W. O’Hearn. 2016. Concurrent Separation Logic. ACM SIGLOG News, 3, 3 (2016), Aug., 47–65.
[16]
James Brotherston and Alex Simpson. 2011. Sequent calculi for induction and infinite descent. J. Log. Comput., 21, 6 (2011), 1177–1216.
[17]
Antonio Bucchiarone and Juan P. Galeotti. 2008. Dynamic Software Architectures Verification using DynAlloy. Electron. Commun. Eur. Assoc. Softw. Sci. Technol., 10 (2008).
[18]
Arvid Butting, Robert Heim, Oliver Kautz, Jan Oliver Ringert, Bernhard Rumpe, and Andreas Wortmann. 2017. A Classification of Dynamic Reconfiguration in Component and Connector Architecture Description. In Proceedings of MODELS 2017 Satellite Event: Workshops (ModComp) (CEUR Workshop Proceedings, Vol. 2019). CEUR-WS.org, 10–16.
[19]
Cristiano Calcagno, Dino Distefano, Peter W. O’Hearn, and Hongseok Yang. 2011. Compositional Shape Analysis by Means of Bi-Abduction. J. ACM, 58, 6 (2011), Article 26, Dec., 66 pages. issn:0004-5411 https://doi.org/10.1145/2049697.2049700
[20]
Cristiano Calcagno, Peter W. O’Hearn, and Hongseok Yang. 2007. Local Action and Abstract Separation Logic. In 22nd IEEE Symposium on Logic in Computer Science (LICS 2007), 10-12 July 2007, Wroclaw, Poland, Proceedings. IEEE Computer Society, 366–378. https://doi.org/10.1109/LICS.2007.30
[21]
Jiannong Cao, Alvin T. S. Chan, and Yudong Sun. 2005. GOP: A Graph-Oriented Programming Model for Parallel and Distributed Systems. Springer US, Boston, MA. 21–36. isbn:978-0-387-28967-0 https://doi.org/10.1007/0-387-28967-4_2
[22]
Everton Cavalcante, Thaís Vasconcelos Batista, and Flávio Oquendo. 2015. Supporting Dynamic Software Architectures: From Architectural Description to Implementation. In 12th Working IEEE/IFIP Conference on Software Architecture, WICSA 2015, Len Bass, Patricia Lago, and Philippe Kruchten (Eds.). IEEE Computer Society, 31–40.
[23]
Ernest Chang and Rosemary Roberts. 1979. An Improved Algorithm for Decentralized Extrema-Finding in Circular Configurations of Processes. Commun. ACM, 22, 5 (1979), may, 281–283. issn:0001-0782 https://doi.org/10.1145/359104.359108
[24]
Yu-Fang Chen, Chih-Duo Hong, Anthony W. Lin, and Philipp Rümmer. 2017. Learning to prove safety over parameterised concurrent systems. In 2017 Formal Methods in Computer Aided Design, FMCAD 2017, Daryl Stewart and Georg Weissenbacher (Eds.). IEEE, 76–83.
[25]
Chris Chilton, Bengt Jonsson, and Marta Z. Kwiatkowska. 2014. Compositional assume-guarantee reasoning for input/output component theories. Sci. Comput. Program., 91 (2014), 115–137. https://doi.org/10.1016/j.scico.2013.12.010
[26]
Dave Clarke. 2008. A Basic Logic for Reasoning about Connector Reconfiguration. Fundam. Inf., 82, 4 (2008), Feb., 361–390. issn:0169-2968
[27]
Loris D’Antoni and Margus Veanes. 2021. Automata modulo theories. Commun. ACM, 64, 5 (2021), 86–95.
[28]
Luca de Alfaro and Thomas A. Henzinger. 2001. Interface Automata. In Proceedings of the 8th European Software Engineering Conference Held Jointly with 9th ACM SIGSOFT International Symposium on Foundations of Software Engineering (ESEC/FSE-9). Association for Computing Machinery, New York, NY, USA. 109–120. isbn:1581133901 https://doi.org/10.1145/503209.503226
[29]
Stéphane Demri, Étienne Lozes, and Alessio Mansutti. 2018. The Effects of Adding Reachability Predicates in Propositional Separation Logic. In FOSSACS 2018, Proceedings (Lecture Notes in Computer Science, Vol. 10803). Springer, 476–493. https://doi.org/10.1007/978-3-319-89366-2_26
[30]
Thomas Dinsdale-Young, Lars Birkedal, Philippa Gardner, Matthew Parkinson, and Hongseok Yang. 2013. Views: Compositional Reasoning for Concurrent Programs. SIGPLAN Not., 48, 1 (2013), Jan., 287–300.
[31]
Thomas Dinsdale-Young, Mike Dodds, Philippa Gardner, Matthew J. Parkinson, and Viktor Vafeiadis. 2010. Concurrent Abstract Predicates. In ECOOP 2010 – Object-Oriented Programming. 6183, Springer Berlin Heidelberg, Berlin, Heidelberg. 504–528.
[32]
Danny Dolev, Maria Klawe, and Michael Rodeh. 1982. An O(n log n) unidirectional distributed algorithm for extrema finding in a circle. Journal of Algorithms, 3, 3 (1982), 245–260. issn:0196-6774 https://doi.org/10.1016/0196-6774(82)90023-2
[33]
Julien Dormoy, Olga Kouchnarenko, and Arnaud Lanoix. 2010. Using Temporal Logic for Dynamic Reconfigurations of Components. In Formal Aspects of Component Software - 7th International Workshop, FACS 2010, Luís Soares Barbosa and Markus Lumpe (Eds.) (Lecture Notes in Computer Science, Vol. 6921). Springer, 200–217.
[34]
Mnacho Echenim, Radu Iosif, and Nicolas Peltier. 2020. Entailment Checking in Separation Logic with Inductive Definitions is 2-EXPTIME hard. In LPAR 2020: 23rd International Conference on Logic for Programming, Artificial Intelligence and Reasoning, Alicante, Spain, May 22-27, 2020 (EPiC Series in Computing, Vol. 73). EasyChair, 191–211. https://easychair.org/publications/paper/DdNg
[35]
Rim El-Ballouli, Saddek Bensalem, Marius Bozga, and Joseph Sifakis. 2021. Programming Dynamic Reconfigurable Systems. International Journal on Software Tools for Technology Transfer, January.
[36]
Antoine El-Hokayem, Marius Bozga, and Joseph Sifakis. 2021. A temporal configuration logic for dynamic reconfigurable systems. In SAC ’21: The 36th ACM/SIGAPP Symposium on Applied Computing, Virtual Event, Republic of Korea, March 22-26, 2021, Chih-Cheng Hung, Jiman Hong, Alessio Bechini, and Eunjee Song (Eds.). ACM, 1419–1428. https://doi.org/10.1145/3412841.3442017
[37]
František Farka, Aleksandar Nanevski, Anindya Banerjee, Germán Andrés Delbianco, and Ignacio Fábregas. 2021. On Algebraic Abstractions for Concurrent Separation Logics. Proc. ACM Program. Lang., 5, POPL (2021), Article 5, Jan.
[38]
Xinyu Feng, Rodrigo Ferreira, and Zhong Shao. 2007. On the Relationship Between Concurrent Separation Logic and Assume-Guarantee Reasoning. In Programming Languages and Systems. 4421, Springer Berlin Heidelberg, 173–188.
[39]
Klaus-Tycho Foerster and Stefan Schmid. 2019. Survey of Reconfigurable Data Center Networks: Enablers, Algorithms, Complexity. SIGACT News, 50, 2 (2019), 62–79. https://doi.org/10.1145/3351452.3351464
[40]
Ian Foster. 2002. What is the Grid? A Three Point Checklist. GRID today, 1 (2002), 01, 32–36.
[41]
Dominik Gall, Riko Jacob, Andrea Richa, Christian Scheideler, Stefan Schmid, and Hanjo Taeubig. 2014. A Note on the Parallel Runtime of Self-Stabilizing Graph Linearization. Theory of Computing Systems (TOCS).
[42]
Nikos Gorogiannis, Max I. Kanovich, and Peter W. O’Hearn. 2011. The Complexity of Abduction for Separated Heap Abstractions. In Static Analysis - 18th International Symposium, SAS 2011, Venice, Italy, September 14-16, 2011. Proceedings, Eran Yahav (Ed.) (Lecture Notes in Computer Science, Vol. 6887). Springer, 25–42. https://doi.org/10.1007/978-3-642-23702-7_7
[43]
Dan Hirsch, Paolo Inverardi, and Ugo Montanari. 1998. Graph Grammars and Constraint Solving for Software Architecture Styles. In Proceedings of the Third International Workshop on Software Architecture (ISAW ’98). Association for Computing Machinery, New York, NY, USA. 69–72. isbn:1581130813 https://doi.org/10.1145/288408.288426
[44]
Radu Iosif and Florian Zuleger. 2022. On the Expressiveness of a Logic of Separated Relations. https://doi.org/10.48550/ARXIV.2208.01520
[45]
Daniel Jackson. 2002. Alloy: a lightweight object modelling notation. ACM Trans. Softw. Eng. Methodol., 11, 2 (2002), 256–290.
[46]
Cliff B. Jones. 1981. Developing methods for computer programs including a notion of interference. Ph.D. Dissertation. University of Oxford, UK.
[47]
Jens Katelaan and Florian Zuleger. 2020. Beyond Symbolic Heaps: Deciding Separation Logic With Inductive Definitions. In LPAR 2020: 23rd International Conference on Logic for Programming, Artificial Intelligence and Reasoning, Alicante, Spain, May 22-27, 2020 (EPiC Series in Computing, Vol. 73). EasyChair, 390–408. https://easychair.org/publications/paper/VTGk
[48]
Igor V. Konnov, Tomer Kotek, Qiang Wang, Helmut Veith, Simon Bliudze, and Joseph Sifakis. 2016. Parameterized Systems in BIP: Design and Model Checking. In 27th International Conference on Concurrency Theory, CONCUR 2016 (LIPIcs, Vol. 59). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 30:1–30:16.
[49]
Christian Krause, Ziyan Maraikar, Alexander Lazovik, and Farhad Arbab. 2011. Modeling dynamic reconfigurations in Reo using high-level replacement systems. Sci. Comput. Program., 76, 1 (2011), 23–36. https://doi.org/10.1016/j.scico.2009.10.006
[50]
Joseph B. Kruskal. 1956. On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. Proc. Amer. Math. Soc., 7, 1 (1956), 48–50. issn:00029939, 10886826 http://www.jstor.org/stable/2033241
[51]
Leslie Lamport. 1998. The Part-Time Parliament. ACM Trans. Comput. Syst., 16, 2 (1998), may, 133–169. issn:0734-2071 https://doi.org/10.1145/279227.279229
[52]
Leslie Lamport, Robert Shostak, and Marshall Pease. 1982. The Byzantine Generals Problem. ACM Trans. Program. Lang. Syst., 4, 3 (1982), jul, 382–401. issn:0164-0925 https://doi.org/10.1145/357172.357176
[53]
Arnaud Lanoix, Julien Dormoy, and Olga Kouchnarenko. 2011. Combining Proof and Model-checking to Validate Reconfigurable Architectures. Electron. Notes Theor. Comput. Sci., 279, 2 (2011), 43–57.
[54]
D. Le Metayer. 1998. Describing software architecture styles using graph grammars. IEEE Transactions on Software Engineering, 24, 7 (1998), 521–533. https://doi.org/10.1109/32.708567
[55]
Nancy Lynch and M.R. Tuttle. 1989. An introduction to input/output automata. CWI Quarterly, 2, 3 (1989), Sept., 219–246.
[56]
Jeff Magee and Jeff Kramer. 1996. Dynamic structure in software architectures. In ACM SIGSOFT Software Engineering Notes. 21(6), 3–14.
[57]
Anastasia Mavridou, Eduard Baranov, Simon Bliudze, and Joseph Sifakis. 2017. Configuration logics: Modeling architecture styles. J. Log. Algebr. Meth. Program., 86, 1 (2017), 2–29.
[58]
Othon Michail, George Skretas, and Paul G. Spirakis. 2020. Distributed Computation and Reconfiguration in Actively Dynamic Networks. In PODC ’20: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, August 3-7, 2020, Yuval Emek and Christian Cachin (Eds.). ACM, 448–457. https://doi.org/10.1145/3382734.3405744
[59]
Mohammad Noormohammadpour and Cauligi S. Raghavendra. 2018. Datacenter Traffic Control: Understanding Techniques and Tradeoffs. IEEE Commun. Surv. Tutorials, 20, 2 (2018), 1492–1525.
[60]
Peter W. O’Hearn. 2007. Resources, concurrency, and local reasoning. Theor. Comput. Sci., 375, 1-3 (2007), 271–307. https://doi.org/10.1016/j.tcs.2006.12.035
[61]
Peter W. O’Hearn, John C. Reynolds, and Hongseok Yang. 2001. Local Reasoning About Programs That Alter Data Structures. In Proceedings of the 15th International Workshop on Computer Science Logic (CSL ’01). 1–19.
[62]
Peter W. O’Hearn, Hongseok Yang, and John C. Reynolds. 2009. Separation and Information Hiding. ACM Trans. Program. Lang. Syst., 31, 3 (2009), Article 11, April, 50 pages. issn:0164-0925 https://doi.org/10.1145/1498926.1498929
[63]
Susan Owicki and David Gries. 1978. An Axiomatic Proof Technique for Parallel Programs. Springer New York, New York, NY. 130–152.
[64]
Bruna Soares Peres, Otavio Augusto de Oliveira Souza, Olga Goussevskaia, Chen Avin, and Stefan Schmid. 2019. Distributed Self-Adjusting Tree Networks. In 2019 IEEE Conference on Computer Communications, INFOCOM 2019, Paris, France, April 29 - May 2, 2019. IEEE, 145–153. https://doi.org/10.1109/INFOCOM.2019.8737417
[65]
R. C. Prim. 1957. Shortest connection networks and some generalizations. The Bell System Technical Journal, 36, 6 (1957), 1389–1401. https://doi.org/10.1002/j.1538-7305.1957.tb01515.x
[66]
John C. Reynolds. 2002. Separation Logic: A Logic for Shared Mutable Data Structures. In 17th IEEE Symposium on Logic in Computer Science (LICS 2002), 22-25 July 2002, Copenhagen, Denmark, Proceedings. IEEE Computer Society, 55–74. https://doi.org/10.1109/LICS.2002.1029817
[67]
Stefan Schmid, Chen Avin, Christian Scheideler, Michael Borokhovich, Bernhard Haeupler, and Zvi Lotker. 2016. SplayNet: Towards Locally Self-Adjusting Networks. IEEE/ACM Trans. Netw., 24, 3 (2016), June, 1421–1433. issn:1063-6692 https://doi.org/10.1109/TNET.2015.2410313
[68]
Ilya Sergey, Aleksandar Nanevski, Anindya Banerjee, and Germán Andrés Delbianco. 2016. Hoare-Style Specifications as Correctness Conditions for Non-Linearizable Concurrent Objects. SIGPLAN Not., 51, 10 (2016), Oct., 92–110.
[69]
Ze’ev Shtadler and Orna Grumberg. 1989. Network Grammars, Communication Behaviors and Automatic Verification. In Automatic Verification Methods for Finite State Systems, International Workshop, Joseph Sifakis (Ed.) (LNCS, Vol. 407). Springer, 151–165.
[70]
Daniel Dominic Sleator and Robert Endre Tarjan. 1985. Self-Adjusting Binary Search Trees. J. ACM, 32, 3 (1985), July, 652–686. issn:0004-5411 https://doi.org/10.1145/3828.3835
[71]
Gabriele Taentzer, Michael Goedicke, and Torsten Meyer. 1998. Dynamic change management by distributed graph transformation: Towards configurable distributed systems. In International Workshop on Theory and Application of Graph Transformations. 179–193.
[72]
Viktor Vafeiadis and Matthew Parkinson. 2007. A Marriage of Rely/Guarantee and Separation Logic. In CONCUR 2007 – Concurrency Theory. Springer Berlin Heidelberg, 256–271.
[73]
Michel Wermelinger. 1998. Towards a chemical model for software architecture reconfiguration. IEE Proceedings-Software, 145, 5 (1998), 130–136.
[74]
Michel Wermelinger and José Luiz Fiadeiro. 2002. A graph transformation approach to software architecture reconfiguration. Sci. Comput. Program., 44, 2 (2002), 133–155.
[75]
Michel Wermelinger, Antónia Lopes, and José Luiz Fiadeiro. 2001. A Graph Based Architectural (Re)Configuration Language. SIGSOFT Softw. Eng. Notes, 26, 5 (2001), Sept., 21–32. issn:0163-5948 https://doi.org/10.1145/503271.503213

Cited By

View all
  • (2024)Automated Infrastructure as Code Program TestingIEEE Transactions on Software Engineering10.1109/TSE.2024.339307050:6(1585-1599)Online publication date: 1-May-2024
  • (2023)Component-based Distributed Software Reconfiguration:A Verification-oriented SurveyACM Computing Surveys10.1145/359537656:1(1-37)Online publication date: 26-Aug-2023

Index Terms

  1. Reasoning about distributed reconfigurable systems

    Recommendations

    Comments

    Please enable JavaScript to view thecomments powered by Disqus.

    Information & Contributors

    Information

    Published In

    cover image Proceedings of the ACM on Programming Languages
    Proceedings of the ACM on Programming Languages  Volume 6, Issue OOPSLA2
    October 2022
    1932 pages
    EISSN:2475-1421
    DOI:10.1145/3554307
    Issue’s Table of Contents
    This work is licensed under a Creative Commons Attribution 4.0 International License.

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 31 October 2022
    Published in PACMPL Volume 6, Issue OOPSLA2

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. dynamic reconfiguration
    2. local reasoning
    3. parameterized systems

    Qualifiers

    • Research-article

    Funding Sources

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)208
    • Downloads (Last 6 weeks)46
    Reflects downloads up to 24 Nov 2024

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)Automated Infrastructure as Code Program TestingIEEE Transactions on Software Engineering10.1109/TSE.2024.339307050:6(1585-1599)Online publication date: 1-May-2024
    • (2023)Component-based Distributed Software Reconfiguration:A Verification-oriented SurveyACM Computing Surveys10.1145/359537656:1(1-37)Online publication date: 26-Aug-2023

    View Options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Login options

    Full Access

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media