Document Open Access Logo

Functional Programming for Distributed Systems with XC

Authors Giorgio Audrito , Roberto Casadei , Ferruccio Damiani , Guido Salvaneschi , Mirko Viroli

PDF
Thumbnail PDF

File

LIPIcs.ECOOP.2022.20.pdf
  • Filesize: 1.68 MB
  • 28 pages

Document Identifiers

Author Details

Giorgio Audrito
  • University of Turin, Italy
Roberto Casadei
  • University of Bologna, Cesena, Italy
Ferruccio Damiani
  • University of Turin, Italy
Guido Salvaneschi
  • Universität St. Gallen, Switzerland
Mirko Viroli
  • University of Bologna, Cesena, Italy

Funding

This work was supported by the EU/MUR FSE REACT-EU PON R&I 2014-2022 (CCI2014IT16M2OP005), the Swiss National Science Foundation (SNSF, No. 200429), the Hessian LOEWE initiative emergenCITY, and the Ateneo/CSP "Bando ex post 2020".

Cite AsGet BibTex

Giorgio Audrito, Roberto Casadei, Ferruccio Damiani, Guido Salvaneschi, and Mirko Viroli. Functional Programming for Distributed Systems with XC. In 36th European Conference on Object-Oriented Programming (ECOOP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 222, pp. 20:1-20:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ECOOP.2022.20

Abstract

Programming distributed systems is notoriously hard due to - among the others - concurrency, asynchronous execution, message loss, and device failures. Homogeneous distributed systems consist of similar devices that communicate to neighbours and execute the same program: they include wireless sensor networks, network hardware, and robot swarms. For the homogeneous case, we investigate an experimental language design that aims to push the abstraction boundaries farther, compared to existing approaches. In this paper, we introduce the design of XC, a programming language to develop homogeneous distributed systems. In XC, developers define the single program that every device executes and the overall behaviour is achieved collectively, in an emergent way. The programming framework abstracts over concurrency, asynchronous execution, message loss, and device failures. We propose a minimalistic design, which features a single declarative primitive for communication, state management, and connection management. A mechanism called alignment enables developers to abstract over asynchronous execution while still retaining composability. We define syntax and operational semantics of a core calculus, and briefly discuss its main properties. XC comes with two DSL implementations: a DSL in Scala and one in C++. An evaluation based on smart-city monitoring demonstrates XC in a realistic application.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed computing models
  • Theory of computation → Functional constructs
  • Theory of computation → Operational semantics
  • Theory of computation → Type structures
  • Computing methodologies → Distributed programming languages
Keywords
  • Core calculus
  • operational semantics
  • type soundness
  • Scala DSL

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Yehia Abd Alrahman, Rocco De Nicola, and Michele Loreti. Programming interactions in collective adaptive systems by relying on attribute-based communication. Science of Computer Programming, 192, 2020. URL: https://doi.org/10.1016/j.scico.2020.102428.
  2. Mustaque Ahamad, Gil Neiger, James E. Burns, Prince Kohli, and Phillip W. Hutto. Causal memory: Definitions, implementation, and programming. Distributed Comput., 9(1):37-49, 1995. URL: https://doi.org/10.1007/BF01784241.
  3. Joe Armstrong. Erlang. Commun. ACM, 53(9), September 2010. URL: https://doi.org/10.1145/1810891.1810910.
  4. Cyrille Artho, Klaus Havelund, Rahul Kumar, and Yoriyuki Yamagata. Domain-specific languages with Scala. In ICFEM, volume 9407 of Lecture Notes in Computer Science, pages 1-16. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-25423-4_1.
  5. Giorgio Audrito. FCPP: an efficient and extensible field calculus framework. In Proceedings of the 1st International Conference on Autonomic Computing and Self-Organizing Systems, ACSOS, pages 153-159. IEEE Computer Society, 2020. URL: https://doi.org/10.1109/ACSOS49614.2020.00037.
  6. Giorgio Audrito, Jacob Beal, Ferruccio Damiani, Danilo Pianini, and Mirko Viroli. Field-based coordination with the share operator. Logical Methods in Computer Science, 16(4), 2020. URL: https://doi.org/10.23638/LMCS-16(4:1)2020.
  7. Giorgio Audrito, Jacob Beal, Ferruccio Damiani, and Mirko Viroli. Space-time universality of field calculus. In Coordination Models and Languages, volume 10852 of Lecture Notes in Computer Science, pages 1-20. Springer, 2018. URL: https://doi.org/10.1007/978-3-319-92408-3_1.
  8. Giorgio Audrito, Roberto Casadei, Ferruccio Damiani, Danilo Pianini, and Mirko Viroli. Optimal resilient distributed data collection in mobile edge environments. Computers & Electrical Engineering, 2021. URL: https://doi.org/10.1016/j.compeleceng.2021.107580.
  9. Giorgio Audrito, Roberto Casadei, Ferruccio Damiani, Volker Stolz, and Mirko Viroli. Adaptive distributed monitors of spatial properties for cyber-physical systems. J. Syst. Softw., 175:110908, 2021. URL: https://doi.org/10.1016/j.jss.2021.110908.
  10. Giorgio Audrito, Roberto Casadei, Ferruccio Damiani, and Mirko Viroli. Compositional blocks for optimal self-healing gradients. In Self-Adaptive and Self-Organizing Systems (SASO), 2017, pages 91-100. IEEE, IEEE Computer Society, 2017. URL: https://doi.org/10.1109/SASO.2017.18.
  11. Giorgio Audrito, Ferruccio Damiani, Volker Stolz, Gianluca Torta, and Mirko Viroli. Distributed runtime verification by past-CTL and the field calculus. J. Syst. Softw., 187:111251, 2022. URL: https://doi.org/10.1016/j.jss.2022.111251.
  12. Giorgio Audrito, Ferruccio Damiani, Mirko Viroli, and Enrico Bini. Distributed real-time shortest-paths computations with the field calculus. In 2018 IEEE Real-Time Systems Symposium (RTSS), pages 23-34. IEEE Computer Society, 2018. URL: https://doi.org/10.1109/RTSS.2018.00013.
  13. Giorgio Audrito, Luigi Rapetta, and Gianluca Torta. Extensible 3D simulation of aggregated systems with FCPP. In 24th International Conference on Coordination Models and Languages, Proceedings, Lecture Notes in Computer Science. Springer, 2022. To appear. Google Scholar
  14. Jacob Beal. Trading accuracy for speed in approximate consensus. Knowledge Eng. Review, 31(4):325-342, 2016. URL: https://doi.org/10.1017/S0269888916000175.
  15. Jacob Beal, Stefan Dulman, Kyle Usbeck, Mirko Viroli, and Nikolaus Correll. Organizing the aggregate: Languages for spatial computing. In Formal and Practical Aspects of Domain-Specific Languages: Recent Developments, chapter 16, pages 436-501. IGI Global, 2013. URL: https://doi.org/10.4018/978-1-4666-2092-6.ch016.
  16. Jacob Beal, Danilo Pianini, and Mirko Viroli. Aggregate programming for the Internet of Things. IEEE Computer, 48(9), 2015. URL: https://doi.org/10.1109/MC.2015.261.
  17. Jacob Beal, Mirko Viroli, Danilo Pianini, and Ferruccio Damiani. Self-adaptation to device distribution in the Internet of Things. ACM Transactions on Autonomous and Adaptive Systems, 12(3):12:1-12:29, 2017. URL: https://doi.org/10.1145/3105758.
  18. Arne Brutschy, Giovanni Pini, Carlo Pinciroli, Mauro Birattari, and Marco Dorigo. Self-organized task allocation to sequentially interdependent tasks in swarm robotics. Auton. Agents Multi Agent Syst., 28(1):101-125, 2014. URL: https://doi.org/10.1007/s10458-012-9212-y.
  19. Tomás Bures, Ilias Gerostathopoulos, Petr Hnetynka, Jaroslav Keznikl, Michal Kit, and Frantisek Plasil. DEECO: an ensemble-based component system. In Symposium on Component Based Software Engineering (CBSE), pages 81-90. ACM, 2013. URL: https://doi.org/10.1145/2465449.2465462.
  20. Roberto Casadei. scafi/artifact-2021-ecoop-smartc: v1.2, 2022. URL: https://doi.org/10.5281/ZENODO.6538822.
  21. Roberto Casadei. scafi/artifact-2021-ecoop-xc: v1.2, 2022. URL: https://doi.org/10.5281/ZENODO.6538810.
  22. Roberto Casadei, Mirko Viroli, Giorgio Audrito, and Ferruccio Damiani. FScaFi : A core calculus for collective adaptive systems programming. In ISoLA (2), volume 12477 of Lecture Notes in Computer Science, pages 344-360. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-61470-6_21.
  23. Roberto Casadei, Mirko Viroli, Giorgio Audrito, Danilo Pianini, and Ferruccio Damiani. Engineering collective intelligence at the edge with aggregate processes. Eng. Appl. Artif. Intell., 97:104081, 2021. URL: https://doi.org/10.1016/j.engappai.2020.104081.
  24. Shane S. Clark, Jacob Beal, and Partha P. Pal. Distributed recovery for enterprise services. In 2015 IEEE 9th International Conference on Self-Adaptive and Self-Organizing Systems, Cambridge, MA, USA, September 21-25, 2015, pages 111-120. IEEE Computer Society, 2015. URL: https://doi.org/10.1109/SASO.2015.19.
  25. Bruno C. d. S. Oliveira, Adriaan Moors, and Martin Odersky. Type classes as objects and implicits. In SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA), pages 341-360. ACM, 2010. URL: https://doi.org/10.1145/1869459.1869489.
  26. Soura Dasgupta and Jacob Beal. A Lyapunov analysis for the robust stability of an adaptive Bellman-Ford algorithm. In Decision and Control (CDC), 2016 IEEE 55th Conference on, pages 7282-7287. IEEE, 2016. URL: https://doi.org/10.1109/CDC.2016.7799393.
  27. Rocco De Nicola, Michele Loreti, Rosario Pugliese, and Francesco Tiezzi. A formal approach to autonomic systems programming: The SCEL language. ACM Trans. Auton. Adapt. Syst., 9(2):7:1-7:29, 2014. URL: https://doi.org/10.1145/2619998.
  28. Mattias De Wael, Stefan Marr, Bruno De Fraine, Tom Van Cutsem, and Wolfgang De Meuter. Partitioned global address space languages. ACM Computing Surveys, 47(4), May 2015. URL: https://doi.org/10.1145/2716320.
  29. André DeHon, Jean-Louis Giavitto, and Frédéric Gruau, editors. Computing Media and Languages for Space-Oriented Computation, volume 06361 of Dagstuhl Seminar Proceedings, 2007. URL: http://drops.dagstuhl.de/portals/06361.
  30. Sébastien Doeraene. Cross-platform language design in Scala.js (keynote). In SCALA@ICFP, page 1. ACM, 2018. URL: https://doi.org/10.1145/3241653.3266230.
  31. Patrick Th. Eugster, Pascal A. Felber, Rachid Guerraoui, and Anne-Marie Kermarrec. The many faces of publish/subscribe. ACM Comput. Surv., 35(2), June 2003. URL: https://doi.org/10.1145/857076.857078.
  32. Alois Ferscha. Collective adaptive systems. In UbiComp/ISWC Adjunct, pages 893-895. ACM, 2015. URL: https://doi.org/10.1145/2800835.2809508.
  33. Debasish Ghosh, Justin Sheehy, Kresten Krab Thorup, and Steve Vinoski. Programming language impact on the development of distributed systems. J. Internet Serv. Appl., 3(1):23-30, 2012. URL: https://doi.org/10.1007/s13174-011-0042-y.
  34. Atsushi Igarashi, Benjamin C. Pierce, and Philip Wadler. Featherweight Java: A minimal core calculus for Java and GJ. ACM Transactions on Programming Languages and Systems, 23(3), 2001. URL: https://doi.org/10.1145/503502.503505.
  35. Márk Jelasity, Alberto Montresor, and Özalp Babaoglu. Gossip-based aggregation in large dynamic networks. ACM Trans. Comput. Syst., 23(3):219-252, 2005. URL: https://doi.org/10.1145/1082469.1082470.
  36. Pushpendu Kar, Arijit Roy, and Sudip Misra. Connectivity reestablishment in self-organizing sensor networks with dumb nodes. ACM Trans. Auton. Adapt. Syst., 10(4):28:1-28:30, 2016. URL: https://doi.org/10.1145/2816820.
  37. Naomi Kuze, Daichi Kominami, Kenji Kashima, Tomoaki Hashimoto, and Masayuki Murata. Hierarchical optimal control method for controlling large-scale self-organizing networks. ACM Trans. Auton. Adapt. Syst., 12(4):22:1-22:23, 2018. URL: https://doi.org/10.1145/3124644.
  38. Alberto Lluch-Lafuente, Michele Loreti, and Ugo Montanari. Asynchronous distributed execution of fixpoint-based computational fields. Log. Methods Comput. Sci., 13(1), 2017. URL: https://doi.org/10.23638/LMCS-13(1:13)2017.
  39. Thomas W. Malone and Kevin Crowston. The interdisciplinary study of coordination. ACM Comput. Surv., 26(1):87-119, 1994. URL: https://doi.org/10.1145/174666.174668.
  40. Marco Mamei and Franco Zambonelli. Programming pervasive and mobile computing applications with the TOTA middleware. In Pervasive Computing and Communications, 2004, pages 263-273. IEEE, 2004. URL: https://doi.org/10.1109/PERCOM.2004.1276864.
  41. Yuanqiu Mo, Jacob Beal, and Soura Dasgupta. An aggregate computing approach to self-stabilizing leader election. In International Workshops on Foundations and Applications of Self* Systems (FAS*W), pages 112-117. IEEE, 2018. URL: https://doi.org/10.1109/FAS-W.2018.00034.
  42. Christine Morin and Isabelle Puaut. A survey of recoverable distributed shared virtual memory systems. IEEE Trans. Parallel Distributed Syst., 8(9):959-969, 1997. URL: https://doi.org/10.1109/71.615441.
  43. Hamid Mushtaq, Zaid Al-Ars, and Koen Bertels. Survey of fault tolerance techniques for shared memory multicore/multiprocessor systems. In International Design and Test Workshop (IDT), pages 12-17. IEEE, 2011. URL: https://doi.org/10.1109/IDT.2011.6123094.
  44. Ryan Newton and Matt Welsh. Region streams: Functional macroprogramming for sensor networks. In Workshop on Data Management for Sensor Networks, pages 78-87, 2004. URL: https://doi.org/10.1145/1052199.1052213.
  45. Torsten Hoefler on behalf of the MPI Forum. MPI: A message-passing interface standard, version 2.2. Specification, Message Passing Interface Forum, September 2009. URL: http://www.mpi-forum.org/docs/mpi-2.2/mpi22-report.pdf.
  46. H. Van Dyke Parunak, Sven Brueckner, Robert S. Matthews, and John A. Sauter. Pheromone learning for self-organizing agents. IEEE Trans. Syst. Man Cybern. Part A, 35(3):316-326, 2005. URL: https://doi.org/10.1109/TSMCA.2005.846408.
  47. Rajiv Ranjan, Omer F. Rana, Surya Nepal, Mazin Yousif, Philip James, Zhenya Wen, Stuart L. Barr, Paul Watson, Prem Prakash Jayaraman, Dimitrios Georgakopoulos, Massimo Villari, Maria Fazio, Saurabh Kumar Garg, Rajkumar Buyya, Lizhe Wang, Albert Y. Zomaya, and Schahram Dustdar. The next grand challenges: Integrating the internet of things and data science. IEEE Cloud Comput., 5(3):12-26, 2018. URL: https://doi.org/10.1109/MCC.2018.032591612.
  48. Mirko Viroli, Giorgio Audrito, Jacob Beal, Ferruccio Damiani, and Danilo Pianini. Engineering resilient collective adaptive systems by self-stabilisation. ACM Trans. Model. Comput. Simul., 28(2):16:1-16:28, 2018. URL: https://doi.org/10.1145/3177774.
  49. Mirko Viroli, Jacob Beal, Ferruccio Damiani, Giorgio Audrito, Roberto Casadei, and Danilo Pianini. From distributed coordination to field calculus and aggregate computing. J. Log. Algebraic Methods Program., 109, 2019. URL: https://doi.org/10.1016/j.jlamp.2019.100486.
  50. Pascal Weisenburger, Mirko Köhler, and Guido Salvaneschi. Distributed system development with ScalaLoci. Proc. ACM Program. Lang., 2(OOPSLA):129:1-129:30, 2018. URL: https://doi.org/10.1145/3276499.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact