Optimal single-path information propagation in gradient-based algorithms


Giorgio Audrito, Ferruccio Damiani, Mirko Viroli

Science of Computer Programming 166, pages 146166,  2018
Elsevier Science B.V.

Scenarios like wireless network networks, Internet of Things, and pervasive computing, promote full distribution of computation as well as opportunistic, peer-to-peer interactions between devices spread in the environment. In this context, computing estimated distances between devices in the network is a key component, commonly referred to as the gradient self-organisation pattern: it is frequently used to broadcast information, forecast pointwise events, as carrier for distributed sensing, and as combinator for higher-level spatial structures. However, computing gradients is very problematic in an environment affected by mutability in the position and working frequency of devices: existing algorithms fail in reaching adequate trade-offs between accuracy and reaction speed to environment changes.

We propose BIS (Bounded Information Speed) gradient, a fully-distributed algorithm that uses time information to achieve a smooth and predictable reaction speed, and prove it is optimal across algorithms following a single-path-communication strategy to spread information. We empirically evaluate BIS gradient and compare it with other approaches, showing that BIS achieves the best accuracy while keeping smoothness under control, and accordingly provides improved performance when used as building block in more complex algorithms for creating spatial structures and performing distributed collection of data.

(keywords) Aggregate programming, Gradient, Information speed, Reliability, Spatial computing
 @article{gradients-scp166,
Author = {Audrito, Giorgio and Damiani, Ferruccio and Viroli, Mirko},
Doi = {10.1016/j.scico.2018.06.002},
Issn = {0167-6423},
Journal = {Science of Computer Programming},
Keywords = {Aggregate programming, Gradient, Information speed, Reliability, Spatial computing},
Pages = {146--166},
Title = {Optimal single-path information propagation in gradient-based algorithms},
Url = {http://www.sciencedirect.com/science/article/pii/S0167642318302387},
Volume = 166,
Year = 2018

Journals & Series

Tags:

Publication

— authors

Giorgio Audrito, Ferruccio Damiani, Mirko Viroli

— status

published

— sort

article in journal

Venue

— journal

Science of Computer Programming

— volume

166

— pages

146166

— publication date

2018

URLs

original page

Identifiers

— DOI

10.1016/j.scico.2018.06.002

— print ISSN

0167-6423

BibTeX

— BibTeX ID
gradients-scp166
— BibTeX category
article

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