Giorgio Audrito, Jacob Beal, Ferruccio Damiani, Mirko Viroli

Coordination Models and Languages, Ch. 1, pages 1–20
Lecture Notes in Computer Science 10852,  2018
Springer
Giovanna Di Marzo Serugendo, Michele Loreti (eds.)

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.

 @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 }

Events

  • Architectures, Languages and Paradigms for IoT (ALP4IoT2017) — 18/09/2017

Tags:

Publication

— authors

Giorgio Audrito, Jacob Beal, Ferruccio Damiani, Mirko Viroli

— editors

Giovanna Di Marzo Serugendo, Michele Loreti

— status

published

— sort

paper in proceedings

Venue

— volume

Coordination Models and Languages

— series

Lecture Notes in Computer Science

— volume

10852

— chapter

1

— pages

1–20

— article no.

1

— publication date

2018

URLs

original page  |  original PDF

Identifiers

— DOI

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

BibTeX

— BibTeX ID
ABDV-COORDINATION2018
— BibTeX category
inproceedings

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