Notes

• Proposes and analyzes the Multi-Walk (MW) algorithm, addressing the lack of comprehensive convergence analysis for Asynchronous Gossip.
• MW shows better convergence in terms of iterations compared to Asynchronous Gossip in graphs with large diameters (e.g., cycles).
• In small-diameter graphs (e.g., complete graphs), relative performance depends on the number of walks and data heterogeneity.
• Wall-clock time analysis shows linear speed-up with the number of walks for MW and with nodes for Asynchronous Gossip.
• MW generally outperforms Asynchronous Gossip in communication overhead, except in small-diameter topologies with extreme data heterogeneity.
• Highlights the effectiveness of each algorithm under different conditions; code is available for reproducibility.

• 提出并分析了多流随机行走算法MW，填补了异步Gossip算法缺乏全面收敛分析的空白。
• 在直径较大的图（如环）中，MW在迭代次数上的收敛性优于异步Gossip。
• 在直径较小的图（如完全图）中，MW与异步Gossip的相对性能取决于行走数量和数据的异质性。
• 在挂钟时间分析中，MW的性能随行走数量线性提升，异步Gossip则随节点数量线性提升。
• 在通信开销方面，除了数据异质性极高的小直径拓扑外，MW通常优于异步Gossip。
• 研究结果强调了不同算法在不同图拓扑和数据异质性场景下的有效性，代码已开源。

• マルチウォーク（MW）アルゴリズムを提案・分析し、非同期Gossipの包括的な収束分析の不足を補った。
• 直径の大きいグラフ（例：サイクル）では、MWは反復回数において非同期Gossipより優れた収束性を示す。
• 直径の小さいグラフ（例：完全グラフ）では、相対的性能はウォーク数とデータ不均一性に依存する。
• 実時間分析では、MWはウォーク数に、非同期Gossipはノード数に比例した線形高速化を示す。
• 通信オーバーヘッドでは、極端なデータ不均一性を持つ小直径トポロジーを除き、MWが非同期Gossipを上回る。
• 異なる条件下での各アルゴリズムの有効性を強調し、再現性のためにコードを公開している。