Space-Time Universality of Field Calculus


Giorgio Audrito, Jacob Beal, Ferruccio Damiani, Mirko Viroli

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

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.

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

— publication date

2018

— volume

Coordination Models and Languages

— series

Lecture Notes in Computer Science

— volume

10852

— chapter

1

— pages

1–20

— article no.

1

— number of pages

20

URLs

original page  |  original PDF

identifiers

— DOI

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

Partita IVA: 01131710376 — Copyright © 2008–2023 APICe@DISI – PRIVACY