Self-Regulating Random Walks for Resilient Decentralized Learning on Graphs
This addresses failure resilience in decentralized learning systems, which is crucial for applications like distributed AI, but the approach is incremental as it builds on existing RW-based methods.
The paper tackles the problem of maintaining a desired number of random walks (RWs) on graphs to ensure resilience against node or link failures in decentralized learning, proposing two algorithms (DecAFork and DecAFork+) that maintain RW counts around a target value with fast detection and reaction to failures compared to a baseline, supported by theoretical guarantees and extensive simulations.
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.