论文标题
动态算法的几乎最佳分布式实现对称性问题
Near-Optimal Distributed Implementations of Dynamic Algorithms for Symmetry-Breaking Problems
论文作者
论文摘要
动态图算法的领域旨在实现对拓扑随时间发展的现实网络的透彻理解。传统上，重点一直放在经典的顺序，集中设置上，其中算法的主要质量度量是其更新时间，即每次更新后恢复解决方案所需的时间。尽管现实生活中的网络经常分布在多台机器上，但发现有效的动态，分布式图算法的基本问题很少受到关注。在此设置中的目标是优化每个更新步骤产生的回合和消息复杂性，理想情况下实现了与$ O（1）$（也许是摊销）回合中集中式更新时间相匹配的消息复杂性。 为了启动对动态，分布式算法的系统研究，我们研究了一些最中心的对称性问题：最大独立集（MIS），最大匹配/（左右）最大（左右）最大基数匹配（mm/mcm）和$（δ+ 1）$ - $ dertex $ - pertex cornetex cornecortex cornerty。本文着重于确定性的动态，分布式算法，尤其是对自适应对手的鲁棒性。我们的大部分重点是我们的MIS算法，该算法实现了$ o \ left（m^{2/3} \ log^2 n \ right）$在$ o \ left中摊销的消息（\ log^2 n \ right）$在consest模型中amortized rounds。值得注意的是，我们算法的摊销消息复杂性与Gupta和Khan [Sosa'21]最著名的确定性集中式MIS算法的摊销更新时间与Polylog $ n $ ractor相匹配。 Assadi等人的先前最佳确定性分布式MIS算法。 [stoc'18]，使用$ o（m^{3/4}）$ o（1）$ o（1）$（1）$ a摊销的回合，即，我们通过对圆形复杂性增加的多项式提高了消息复杂性的多项式提高；此外，Assadi等人的算法。有一个隐含的假设，即[...]
The field of dynamic graph algorithms aims at achieving a thorough understanding of real-world networks whose topology evolves with time. Traditionally, the focus has been on the classic sequential, centralized setting where the main quality measure of an algorithm is its update time, i.e. the time needed to restore the solution after each update. While real-life networks are very often distributed across multiple machines, the fundamental question of finding efficient dynamic, distributed graph algorithms received little attention to date. The goal in this setting is to optimize both the round and message complexities incurred per update step, ideally achieving a message complexity that matches the centralized update time in $O(1)$ (perhaps amortized) rounds. Toward initiating a systematic study of dynamic, distributed algorithms, we study some of the most central symmetry-breaking problems: maximal independent set (MIS), maximal matching/(approx-) maximum cardinality matching (MM/MCM), and $(Δ+ 1)$-vertex coloring. This paper focuses on dynamic, distributed algorithms that are deterministic, and in particular -- robust against an adaptive adversary. Most of our focus is on our MIS algorithm, which achieves $O\left(m^{2/3}\log^2 n\right)$ amortized messages in $O\left(\log^2 n\right)$ amortized rounds in the Congest model. Notably, the amortized message complexity of our algorithm matches the amortized update time of the best-known deterministic centralized MIS algorithm by Gupta and Khan [SOSA'21] up to a polylog $n$ factor. The previous best deterministic distributed MIS algorithm, by Assadi et al. [STOC'18], uses $O(m^{3/4})$ amortized messages in $O(1)$ amortized rounds, i.e., we achieve a polynomial improvement in the message complexity by a polylog $n$ increase to the round complexity; moreover, the algorithm of Assadi et al. makes an implicit assumption that the [...]
