Distributed Real-Time Shortest-Paths Computations with the Field Calculus

Giorgio Audrito, Ferruccio Damiani, Mirko Viroli, Enrico Bini

2018 IEEE Real-Time Systems Symposium (RTSS), pages 23-34
IEEE Computer Society
December 2018

As the density of sensing/computation/actuation nodes is increasing, it becomes more and more feasible and useful to think at an entire network of physical devices as a single, continuous space-time computing machine. The emergent behaviour of the whole software system is then induced by local computations deployed within each node and by the dynamics of the information diffusion. A relevant example of this distribution model is given by aggregate computing and its companion language field calculus, a minimal set of purely functional constructs used to manipulate distributed data structures evolving over space and time, and resulting in robustness to changes. In this paper, we study the convergence time of an archetypal and widely used component of distributed computations expressed in field calculus, called gradient: a fully-distributed estimation of distances over a metric space by a spanning tree. We provide an analytic result linking the quality of the output of a gradient to the amount of computing resources dedicated. The resulting error bounds are then exploited for network design, suggesting an optimal density value taking broadcast interferences into account. Finally, an empirical evaluation is performed validating the theoretical results.

(keywords) Calculus;Aggregates;Programming;Computational modeling;Real-time systems;Sensors;Wireless sensor networks;aggregate computing;field calculus;shortest path;IoT;distributed systems



— authors

Giorgio Audrito, Ferruccio Damiani, Mirko Viroli, Enrico Bini

— status


— sort

paper in proceedings

— publication date

December 2018

— volume

2018 IEEE Real-Time Systems Symposium (RTSS)

— pages


— number of pages


— location

Nashville, TN, USA


original page  |  original PDF




— print ISSN


Partita IVA: 01131710376 — Copyright © 2008–2023 APICe@DISI – PRIVACY