Distributed Detection of Cycles
Distributed Detection of Cycles
复制标题
分布式循环检测
DOI：
10.1145/3087556.3087571
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Dennis Olivetti
中科院分区：
文献类型：
--
作者：
P. Fraigniaud;Dennis Olivetti
Brakerski和Patt-Shamir（2011）引入了网络中的分布式属性测试，其目的是以分布式方式检测大型密集子网络的存在。最近，Censor-Hillel等人（2016）已经展示了如何通过分布式算法在恒定数量的轮次中检测3-循环。在后续工作中，Fraigniaud等人（2016）也展示了如何在恒定数量的轮中检测4个周期。然而，这些后面的工作中的技术被证明不能推广到k ≥ 5的更大的循环Ck。在本文中，我们完全解决了循环检测的问题，通过建立以下结果。对于每一个k ≥ 3，存在一个Ck-自由度的分布式属性测试算法，在常数轮数中执行。所有这些结果都适用于分布式网络计算的经典拥塞模型。我们的算法是单侧误差。其轮复杂度为O（1/ε），其中ε ∈（0，1）是衡量法律的实例与非法实例之间的差距的性能测试参数。
Distributed property testing in networks has been introduced by Brakerski and Patt-Shamir (2011), with the objective of detecting the presence of large dense sub-networks in a distributed manner. Recently, Censor-Hillel et al. (2016) have shown how to detect 3-cycles in a constant number of rounds by a distributed algorithm. In a follow up work, Fraigniaud et al. (2016) have shown how to detect 4-cycles in a constant number of rounds as well. However, the techniques in these latter works were shown not to generalize to larger cycles Ck with k ≥ 5. In this paper, we completely settle the problem of cycle detection, by establishing the following result. For every k ≥ 3, there exists a distributed property testing algorithm for Ck-freeness, performing in a constant number of rounds. All these results hold in the classical congest/ model for distributed network computing. Our algorithm is 1-sided error. Its round-complexity is O(1/ε) where ε ∈(0,1) is the property testing parameter measuring the gap between legal and illegal instances.