EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Self-Regulating Random Walks for Resilient Decentralized Learning on Graphs

Maximilian Egger, Rawad Bitar, Ghadir Ayache, Antonia Wachter-Zeh, Salim El Rouayheb

IEEE Transactions on Information Theory · 2026-09 · 72 (9) · 6864-6878

DOI: 10.1109/tit.2026.3706658 ↗

Kurz gefasst

Fachartikel in der Zeitschrift IEEE Transactions on Information Theory, 2026-09. Verfasst von Maximilian Egger und 4 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 31 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: German Research Foundation, Army Research Laboratory, National Science Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Consider the setting of multiple random walks (RWs) on a graph executing a certain computational task. For instance, in decentralized learning via RWs, a model is updated at each iteration based on the local data of the visited node and then passed to a randomly chosen neighbor. RWs can fail due to node or link failures. The goal is to maintain a desired number of RWs to ensure failure resilience. Achieving this is challenging due to the lack of a central entity to track which RWs have failed to replace them with new ones by forking (duplicating) surviving ones. Without duplications, the number of RWs will eventually go to zero, causing a catastrophic failure of the system. We propose two decentralized algorithms called DecAFork and DecAFork+ that can maintain the number of RWs in the graph around a desired value even in the presence of arbitrary RW failures. Nodes continuously estimate the number of surviving RWs by estimating their return time distribution and fork the RWs when failures are likely to happen. DecAFork+ additionally allows terminations to avoid overloading the network by forking too many RWs. We present extensive numerical simulations that show the performance of DecAFork and DecAFork+ regarding fast detection and reaction to failures compared to a baseline, and establish theoretical guarantees on the performance of both algorithms.

Förderung

  • German Research Foundation
  • Army Research Laboratory
  • National Science Foundation

Zitieren

APA

Egger, M., Bitar, R., Ayache, G., Wachter-Zeh, A., & Rouayheb, S. E. (2026). Self-Regulating Random Walks for Resilient Decentralized Learning on Graphs. IEEE Transactions on Information Theory, 72(9), 6864-6878. https://doi.org/10.1109/tit.2026.3706658

Vancouver

Egger M, Bitar R, Ayache G, Wachter-Zeh A, Rouayheb SE. Self-Regulating Random Walks for Resilient Decentralized Learning on Graphs. IEEE Transactions on Information Theory. 2026;72(9):6864-6878. doi:10.1109/tit.2026.3706658

BibTeX
@article{Egger2026,
  author = {Egger, Maximilian and Bitar, Rawad and Ayache, Ghadir and Wachter-Zeh, Antonia and Rouayheb, Salim El},
  title = {Self-Regulating Random Walks for Resilient Decentralized Learning on Graphs},
  journal = {IEEE Transactions on Information Theory},
  year = {2026},
  volume = {72},
  number = {9},
  pages = {6864--6878},
  doi = {10.1109/tit.2026.3706658}
}
Kostenlos starten →