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 metadatas

Cited literature [39 references]  Display  Hide  Download

https://hal.inria.fr/hal-01821491
Contributor : Hal Ifip <>
Submitted on : Friday, June 22, 2018 - 2:55:44 PM
Last modification on : Friday, June 22, 2018 - 3:09:24 PM
Long-term archiving on: : Tuesday, September 25, 2018 - 7:54:31 AM

File

 Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2021-01-01

Please log in to resquest access to the document

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

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⟩

Share

Metrics

Record views

388