Skip to Main Content (Press Enter)

Logo UNITO
  • ×
  • Home
  • Pubblicazioni
  • Progetti
  • Persone
  • Competenze
  • Settori
  • Strutture
  • Terza Missione

UNI-FIND
Logo UNITO

|

UNI-FIND

unito.it
  • ×
  • Home
  • Pubblicazioni
  • Progetti
  • Persone
  • Competenze
  • Settori
  • Strutture
  • Terza Missione
  1. Pubblicazioni

Space-time universality of field calculus

Contributo in Atti di convegno
Data di Pubblicazione:
2018
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.
Tipologia CRIS:
04A-Conference paper in volume
Keywords:
Computability; Distributed computing; Field calculus; Theoretical Computer Science; Computer Science (all)
Elenco autori:
Audrito, Giorgio; Beal, Jacob; Damiani, Ferruccio; Viroli, Mirko
Autori di Ateneo:
AUDRITO Giorgio
DAMIANI Ferruccio
Link alla scheda completa:
https://iris.unito.it/handle/2318/1671337
Link al Full Text:
https://iris.unito.it/retrieve/handle/2318/1671337/422147/main.pdf
Titolo del libro:
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Pubblicato in:
LECTURE NOTES IN COMPUTER SCIENCE
Journal
LECTURE NOTES IN COMPUTER SCIENCE
Series
  • Dati Generali

Dati Generali

URL

http://springerlink.com/content/0302-9743/copyright/2005/
  • Utilizzo dei cookie

Realizzato con VIVO | Designed by Cineca | 25.6.1.0