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
December 2018
IEEE Computer Society

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
 @INPROCEEDINGS{ADVB-RTSS2018,
author={Audrito, Giorgio and Damiani, Ferruccio and Viroli, Mirko and Bini, Enrico},
booktitle={2018 IEEE Real-Time Systems Symposium (RTSS)},
title={Distributed Real-Time Shortest-Paths Computations with the Field Calculus},
year={2018},
volume={},
number={},
pages={23-34},
keywords={Calculus;Aggregates;Programming;Computational modeling;Real-time systems;Sensors;Wireless sensor networks;aggregate computing;field calculus;shortest path;IoT;distributed systems},
doi={10.1109/RTSS.2018.00013},
ISSN={2576-3172},
month={Dec}
Tags:

Publication

— authors

Giorgio Audrito, Ferruccio Damiani, Mirko Viroli, Enrico Bini

— status

published

— sort

paper in proceedings

Venue

— volume

2018 IEEE Real-Time Systems Symposium (RTSS)

— pages

23-34

— publication date

December 2018

URLs

original page  |  original PDF

Identifiers

— DOI

10.1109/RTSS.2018.00013

— print ISSN

2576-3172

BibTeX

— BibTeX ID
ADVB-RTSS2018
— BibTeX category
inproceedings

Partita IVA: 01131710376 - Copyright © 2008-2022 APICe@DISI Research Group - PRIVACY