Brief Announcement: Message Reduction in the LOCAL Model is a Free Lunch.
Brief Announcement: Message Reduction in the LOCAL Model is a Free Lunch.
复制标题
简短声明：LOCAL 模型中的消息缩减是免费午餐。
DOI：
10.1145/3293611.3331582
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Shimon Bitton,Yuval Emek,Taisuke Izumi,Shay Kutten
中科院分区：
文献类型：
--
作者：
Ryota Eguchi;Naoki Kitamura;Taisuke Izumi;Taisuke Izumi,Francois Le Gall,Frederic Magniez;Yuval Emek,Noga Harlev,Taisuke Izumi;Yuichi Sudo,Fukuhito Ooshita,Taisuke Izumi,Hirotsugu Kakugawa,Toshimitsu Masuzawa;Taisuke Izumi,Francois Le Gall;Shimon Bitton,Yuval Emek,Taisuke Izumi,Shay Kutten
提出了一种新的扳手构造算法，该算法在LOCAL模型下工作，假设边缘id唯一。给定一个n节点的通信图，一个具有恒定伸展和Õ（n1 + c）边（对于任何小常数c > 0）的扳手被有效地构造——即，在恒定的轮数和Õ（n1 + 2c） whp的消息复杂度中。扳手的许多已知应用之一是用于减少各种算法的消息数量。然而，通常，人们仍然需要支付制造扳手的成本。由于此处扳手构造的效率，我们证明每个t轮LOCAL算法都可以转换为具有相同渐近时间复杂度和Õ（tn1 + O(1/log t)）消息复杂度的随机化算法。所有以前的LOCAL算法的消息缩减方案都会导致O(log n)-乘法或O(polylog (n))-加性的轮复杂度爆炸。
A new spanner construction algorithm is presented, working under the LOCAL model assuming unique edge IDs. Given an n-node communication graph, a spanner with a constant stretch and Õ(n1 + c) edges (for any small constant c > 0) is constructed efficiently --- i.e., in a constant number of rounds and a message complexity of Õ (n1 + 2c) whp.One of the many known applications of spanners is for reducing the number of messages of various algorithms. However, usually, one still needs to pay the cost of constructing the spanner. Due to the efficiency of the spanner construction here, we show that every t-round LOCAL algorithm can be transformed into a randomized one with the same asymptotic time complexity and Õ(t2n1 + O(1/log t)) message complexity. All previous message-reduction schemes for LOCAL algorithms incur either an O(log n)-multiplicative or an O(polylog (n))-additive blow-up of the round complexity.