Journal article
Robustness of the Adaptive Bellman -Ford Algorithm: Global Stability and Ultimate Bounds
IEEE transactions on automatic control, Vol.64(10), pp.4121-4136
10/2019
DOI: 10.1109/TAC.2019.2904239
Abstract
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.
Details
- Title: Subtitle
- Robustness of the Adaptive Bellman -Ford Algorithm: Global Stability and Ultimate Bounds
- Creators
- Yuanqiu Mo - University of IowaSoura Dasgupta - University of IowaJacob Beal - Raytheon Technologies
- Resource Type
- Journal article
- Publication Details
- IEEE transactions on automatic control, Vol.64(10), pp.4121-4136
- Publisher
- IEEE
- DOI
- 10.1109/TAC.2019.2904239
- ISSN
- 0018-9286
- eISSN
- 1558-2523
- Grant note
- HR001117C0049 / Defense Advanced Research Projects Agency (10.13039/100000185)
- Language
- English
- Date published
- 10/2019
- Academic Unit
- Electrical and Computer Engineering
- Record Identifier
- 9984197201702771
Metrics
3 Record Views