A Tale of Two Learning Algorithms: Multiple Stream Random Walk and Asynchronous Gossip

We investigate the relative performance of gossip and random walk-based decentralized learning algorithms across varying network topologies and data heterogeneities. To this end, we introduce “Multi-Walk,” an asynchronous multi-stream random walk algorithm, and comprehensively compare its convergence against “Asynchronous Gossip” in terms of computational iterations, wall-clock time, and communication overhead. Our analysis demonstrates that Multi-Walk achieves superior iteration convergence in large diameter graphs and consistently lower communication costs, except within small-diameter networks experiencing extreme data heterogeneity. Furthermore, both methods exhibit linear wall-clock speedups relative to the number of concurrent computations. These findings elucidate the inherent performance trade-offs between the two approaches, offering guidance on algorithm selection based on structural and distributional network conditions. Our codes are available for reproducibility.