论文标题
回合与最大独立集的交流权衡
Rounds vs Communication Tradeoffs for Maximal Independent Sets
论文作者
论文摘要
我们考虑使用顶点分区输入的共享黑板通信模型中找到最大独立集（MIS）的问题。有$ n $播放器对应于一个无向图的顶点，每个玩家都在其顶点上看到事件的边缘 - 这样，每个边缘都以其端点都知道，因此由两个播放器共享。玩家通过在所有玩家可见的共享黑板上发布消息来同时进行交流，目的是计算图形的错误。尽管MIS问题在其他分布式模型中进行了充分的研究，而共享的黑板也许是最简单的广播模型，但我们问题的下限仅是针对一轮协议而知的。 我们在圆形通信权衡方面提出了一个计算此模型中错误的折衷方案。具体来说，我们表明，当允许$ r $ $ $ round的交互作用时，至少一个玩家需要传达$ω（n^{1/20^{r+1}}）$ bits。特别是，使用对数带宽，找到MIS需要$ω（\ log \ log {n}）$ rounds。可以将这种下限与Ghaffari，Gouleakis，Konrad，Mitrović和Rubinfeld [PODC 2018]的算法进行比较，该算法在$ O（\ log \ log {n}）$ rounds中求解了MIS，但对于普通玩家来说是对数的带宽。此外，我们的下限进一步扩展到了最大二分匹配的紧密相关的问题。 为了证明我们的结果，我们设计了一个新的消除框架，我们将其称为部分输入嵌入，这在未来的工作中也可能对在玩家之间的边缘共享的情况下证明圆形敏感的下限。 最后，我们讨论了结果对多轮（自适应）分布式草图算法，广播拥堵集团以及在双面匹配市场中的福利最大化问题的几种含义。
We consider the problem of finding a maximal independent set (MIS) in the shared blackboard communication model with vertex-partitioned inputs. There are $n$ players corresponding to vertices of an undirected graph, and each player sees the edges incident on its vertex -- this way, each edge is known by both its endpoints and is thus shared by two players. The players communicate in simultaneous rounds by posting their messages on a shared blackboard visible to all players, with the goal of computing an MIS of the graph. While the MIS problem is well studied in other distributed models, and while shared blackboard is, perhaps, the simplest broadcast model, lower bounds for our problem were only known against one-round protocols. We present a lower bound on the round-communication tradeoff for computing an MIS in this model. Specifically, we show that when $r$ rounds of interaction are allowed, at least one player needs to communicate $Ω(n^{1/20^{r+1}})$ bits. In particular, with logarithmic bandwidth, finding an MIS requires $Ω(\log\log{n})$ rounds. This lower bound can be compared with the algorithm of Ghaffari, Gouleakis, Konrad, Mitrović, and Rubinfeld [PODC 2018] that solves MIS in $O(\log\log{n})$ rounds but with a logarithmic bandwidth for an average player. Additionally, our lower bound further extends to the closely related problem of maximal bipartite matching. To prove our results, we devise a new round elimination framework, which we call partial-input embedding, that may also be useful in future work for proving round-sensitive lower bounds in the presence of edge-sharing between players. Finally, we discuss several implications of our results to multi-round (adaptive) distributed sketching algorithms, broadcast congested clique, and to the welfare maximization problem in two-sided matching markets.
