HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [39 references]  Display  Hide  Download

Contributor : Hal Ifip Connect in order to contact the contributor
Submitted on : Friday, June 22, 2018 - 2:55:44 PM
Last modification on : Monday, February 7, 2022 - 4:06:04 PM
Long-term archiving on: : Tuesday, September 25, 2018 - 7:54:31 AM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License



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⟩



Record views


Files downloads