Logo image
Back
Space-Time Universality of Field Calculus
Conference proceeding   Peer reviewed

Space-Time Universality of Field Calculus

Giorgio Audrito, Jacob Beal, Ferruccio Damiani and Mirko Viroli
Lecture Notes in Computer Science, Vol.LNCS-10852, pp.1-20
Coordination Models and Languages
20th International Conference on Coordination Languages and Models (COORDINATION)
2018
DOI: 10.1007/978-3-319-92408-3_1
url
https://inria.hal.science/hal-01821491View
Open Access

Abstract

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.
 Computer Science Networking and Internet Architecture

Details

Metrics

5 Record Views
Logo image