Publications » Space-Time Universality of Field Calculus

Space-Time Universality of Field Calculus

Giorgio Audrito, Jacob Beal, Ferruccio Damiani, Mirko Viroli
Recent work in the area of coordination models and collective adaptive systems promotes a view of distributed computations as functional blocks manipulating data structures spread over space and evolving over time. In this paper, we address expressiveness issues of such computations, and specifically focus on the field calculus, a prominent emerging language in this context. Based on the classical notion of event structure, we introduce the cone Turing machine as a ground for studying computability issues, and first use it to prove that field calculus is space-time universal. We then observe that, in the most general case, field calculus computations can be rather inefficient in the size of messages exchanged, but this can be remedied by an encoding to nearly similar computations with slower information speed. We capture this concept by a notion of delayed space-time universality, which we prove to hold for the set of message-efficient algorithms expressible by field calculus. As a corollary, it is derived that field calculus can implement with message-size efficiency all self-stabilising distributed algorithms.
Coordination Models and Languages, Ch. 1, Lecture Notes in Computer Science 10852, pages 1--20, 2018.
Giovanna Di Marzo Serugendo, Michele Loreti (eds.), Springer
@inproceedings{ABDV-COORDINATION2018,
  author    = {Audrito, Giorgio  and
               Beal, Jacob  and
                Damiani, Ferruccio and
               Viroli, Mirko },
  title     = {Space-Time Universality of Field Calculus},
  booktitle = {Coordination Models and Languages - 20th {IFIP} {WG} 6.1 International
               Conference, {COORDINATION} 2018, Held as Part of the 13th International
               Federated Conference on Distributed Computing Techniques, DisCoTec
               2018, Madrid, Spain, June 18-21, 2018. Proceedings},
  pages     = {1--20},
  year      = {2018},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {10852},
  url       = {https://doi.org/10.1007/978-3-319-92408-3_1},
  doi       = {10.1007/978-3-319-92408-3_1},
  editor    = {Di Marzo Serugendo, Giovanna  and
               Loreti, Michele }
}