Compositional Blocks for Optimal Self-Healing Gradients

With the constant increase in the number of interconnected devices in today networks, and the high demand of adaptiveness, more and more computations can be designed according to self-organisation principles. In this context, a key building block for large-scale system coordination, called gradient, is used to estimate distances in a fully-distributed way: it is the basis for a vast variety of higher level patterns including information broadcast, events forecasting, distributed sensing, and so on. However, computing gradients is very problematic in mobile environments: the fastest self-healing gradient conceived so far (called BIS) achieves a reaction speed proportional to the single-path speed of information in the network. In this paper we introduce a new gradient algorithm, SVD (Stale Values Detection) gradient, which uses broadcasts to reach a reaction speed that is equal to the multi-path speed of information, namely, the fastest speed possibly achievable by network algorithms. We then combine SVD with other blocks (metric correction, smooth filtering, BIS gradient, information damping) proposing a composed block called ULT(imate) gradient. We evaluate the resulting algorithm and compare it with other approaches, showing it scores best both on accuracy and smoothness while keeping communication cost under control.