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 120, 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 }
}

Tags:
    

Publication

Space-Time Universality of Field Calculus

— status

published  

— authors

Giorgio Audrito, Jacob Beal, Ferruccio Damiani, Mirko Viroli

— editors

Giovanna Di Marzo Serugendo, Michele Loreti

URLs & IDs

original page
original PDF

— DOI

10.1007/978-3-319-92408-3_1

BibTeX

— BibTeX ID
ABDV-COORDINATION2018
— BibTeX category
inproceedings

APICe

— event
ALP4IoT2017

Partita IVA: 01131710376 - Copyright © 2008-2021 APICe@DISI Research Group - PRIVACY