Space-Time Universality of Field Calculus - Coordination Models and Languages (COORDINATION 2018)
Conference Papers Year : 2018

Space-Time Universality of Field Calculus

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.
Fichier principal
Vignette du fichier
468924_1_En_1_Chapter.pdf (456.58 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

hal-01821491 , version 1 (22-06-2018)

Licence

Identifiers

Cite

Giorgio Audrito, Jacob Beal, Ferruccio Damiani, Mirko Viroli. Space-Time Universality of Field Calculus. 20th International Conference on Coordination Languages and Models (COORDINATION), Jun 2018, Madrid, Spain. pp.1-20, ⟨10.1007/978-3-319-92408-3_1⟩. ⟨hal-01821491⟩
258 View
95 Download

Altmetric

Share

More