Journal
IEEE TRANSACTIONS ON AUTOMATIC CONTROL
Volume 64, Issue 10, Pages 4121-4136Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TAC.2019.2904239
Keywords
Aggregating computing; Internet of things; Lyapunov function; stability; robustness; ultimate boundedness
Funding
- Defense Advanced Research Projects Agency (DARPA) [HR001117C0049]
Ask authors/readers for more resources
Self-stabilizing distance estimation algorithms are an important building block of many distributed systems, such as seen in the emerging field of aggregate computing. Their safe use in feedback systems or under persistent perturbations has not previously been formally analyzed. Self-stabilization only involves eventual convergence, and is not endowed with robustness properties associated with global uniform asymptotic stability and thus does not guarantee stability under perturbations or feedback. We formulate a Lyapunov function to analyze the Adaptive Bellman-Ford distance estimation algorithm and use it to prove global uniform asymptotic stability, a property which the classical Bellman-Ford algorithm lacks. Global uniform asymptotic stability assures a measure of robustness to structural perturbations, empirically observed by us in a previous work. We also show that the algorithm is ultimately bounded under bounded measurement error and device mobility and provide a tight bound on the ultimate bound and the time to attain it.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available