A Lyapunov analysis for the robust stability of an adaptive Bellman-Ford algorithm
Soura Dasgupta, Jacob Beal · 2016
Self-stabilizing (asymptotically stable) distance estimation algorithms are an important building block of many distributed systems featuring in Spatial or Aggregate computing, but the dynamics of their convergence to correct distance estimates has not previously been formally analyzed. As a first step to understanding, how they behave in interconnections involving other building blocks, it is important to develop a Lyapunov framework to demonstrate their robust stability. This paper addresses this shortcoming by providing the first Lyapunov-based analysis of an adaptive Bellman-Ford algorithm, by formulating a simple Lyapunov function. This analysis proves global uniform asymptotic stability of such algorithms, a property which the classical Bellman-Ford algorithm lacks, thus demonstrating a measure of robustness to structural perturbations, empirically observed by us in a previous work.