Derandomizing local distributed algorithms under bandwidth restrictions
Derandomizing local distributed algorithms under bandwidth restrictions
复制标题
DOI：
10.1007/s00446-020-00376-1
复制
发表时间：
2016-08
影响因子：
1.3
通讯作者：
K. Censor-Hillel;M. Parter;Gregory Schwartzman
中科院分区：
文献类型：
--
作者：
K. Censor-Hillel;M. Parter;Gregory Schwartzman
本文讨论了分布式计算中的局部问题的基石家族，并研究了带宽限制下随机解和确定解之间的奇怪差距。我们的主要贡献是在提供工具去随机化的解决方案，当地的问题，当thennodes只能发送位的消息，在每一轮的通信。我们的框架主要遵循吕比的去随机化方法（J Comput Syst Sci 47（2）：250-286，1993），并结合了所有人对所有人通信的力量。我们的主要结果如下：首先，我们表明，在拥挤的集团模型，它允许所有到所有的通信，有一个确定性的最大独立集算法，运行轮，其中是最大程度。当，边界改进为。此外，我们还确定性地构造了拥挤团模型中的轮内a-带边。
This paper addresses the cornerstone family oflocal problemsin distributed computing, and investigates the curious gap between randomized and deterministic solutions under bandwidth restrictions. Our main contribution is in providing tools for derandomizing solutions to local problems, when thennodes can only send-bit messages in each round of communication. Our framework mostly follows by the derandomization approach of Luby (J Comput Syst Sci 47(2):250–286, 1993) combined with the power of all to all communication. Our key results are as follows: first, we show that in thecongested cliquemodel, which allows all-to-all communication, there is a deterministic maximal independent set algorithm that runs inrounds, whereis the maximum degree. When, the bound improves to. In addition, we deterministically construct a-spanner withedges inrounds in the congested clique model.