10:00 - 12:00 | Mon 17 Dec | Splash 9 | MoA17
Self-stabilizing information spreading algorithms are an important building block of many distributed systems featuring in aggregate computing. The convergence dynamics of self-stabilizing information spreading, however, have not previously been characterized, except in the special case of a distance finding variant known as the Adaptive Bellman-Ford (ABF) Algorithm. As a step towards understanding the behavior of these algorithms, particularly when interconnected with other building blocks, it is important to develop a framework to demonstrate their robust stability. Accordingly, this paper analyzes an extremely general information spreading algorithm of which ABF is a special case. We provide a proof of global uniform asymptotic stability, upper bound on the time to converge, and ultimate bounds on state error in face of persistent perturbations.
No information added