Optimal single-path information propagation in gradient-based algorithms

Last modified by Mirko Viroli on 2020/10/12 17:21

Giorgio Audrito, Ferruccio Damiani, Mirko Viroli

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
Science of Computer Programming 166, pages 146166, 2018, Elsevier Science B.V.
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}



2011 © aliCE Research Group @ DEIS, Alma Mater Studiorum-Università di Bologna