Convergence and Robustness Bounds for Distributed Asynchronous Shortest-Path
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912473600229376 |
|---|---|
| author | Miller, Jared Bianchi, Mattia Dörfler, Florian |
| author_facet | Miller, Jared Bianchi, Mattia Dörfler, Florian |
| contents | This work analyzes convergence times and robustness bounds for asynchronous distributed shortest-path computation. We focus on the Adaptive Bellman--Ford algorithm, a self-stabilizing method in which each agent updates its shortest-path estimate based only on the estimates of its neighbors and forgetting its previous estimate. In the asynchronous framework considered in this paper, agents are allowed to idle or encounter race conditions during their execution of the Adaptive Bellman--Ford algorithm. We build on Lyapunov-based results that develop finite-time convergence and robustness bounds for the synchronous shortest-path setting, in order to produce finite-time convergence and robustness bounds for the asynchronous setting. We also explore robustness against interval-bounded noise processes and establish convergence and robustness guarantees for asynchronous most-probable-path algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_07263 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Convergence and Robustness Bounds for Distributed Asynchronous Shortest-Path Miller, Jared Bianchi, Mattia Dörfler, Florian Optimization and Control Systems and Control This work analyzes convergence times and robustness bounds for asynchronous distributed shortest-path computation. We focus on the Adaptive Bellman--Ford algorithm, a self-stabilizing method in which each agent updates its shortest-path estimate based only on the estimates of its neighbors and forgetting its previous estimate. In the asynchronous framework considered in this paper, agents are allowed to idle or encounter race conditions during their execution of the Adaptive Bellman--Ford algorithm. We build on Lyapunov-based results that develop finite-time convergence and robustness bounds for the synchronous shortest-path setting, in order to produce finite-time convergence and robustness bounds for the asynchronous setting. We also explore robustness against interval-bounded noise processes and establish convergence and robustness guarantees for asynchronous most-probable-path algorithms. |
| title | Convergence and Robustness Bounds for Distributed Asynchronous Shortest-Path |
| topic | Optimization and Control Systems and Control |
| url | https://arxiv.org/abs/2507.07263 |