Tight bounds for distributed selection
Tight bounds for distributed selection
复制标题
分布式选择的严格界限
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Roger Wattenhofer
中科院分区：
文献类型：
--
作者：
F. Kuhn;Thomas Locher;Roger Wattenhofer
我们重新审视分布式<i> k </i>选择的问题，在给定直径的一般连接图<i> d </i>的一般连接图中，由<i> n </i> nodes组成，每个节点都保留一个。数字元素，目标是确定<i> k <sup> th </sup> </i>在我们的模型中最小的</i>。图中的节点。我们提出了一种随机算法<i> o </i>（<i> d </i> log <sub> <i> d </i> </sub> <i> n </i>），另外的概率是确定性提出了哪个算法，具有最差的时间复杂性的<i> o </i>（<i> d </i> log2 <over> <i> d </i> <i> n </i>）大大改善了确定算法的最著名的界限。任何随机或确定性的sub> <i> i>）算法，这意味着随机算法在不对称上是最佳的。
We revisit the problem of distributed <i>k</i>-selection where, given a general connected graph of diameter <i>D</i> consisting of <i>n</i> nodes in which each node holds a numeric element, the goal is to determine the <i>k<sup>th</sup></i> smallest of these elements. In our model, there is no imposed relation between the magnitude of the stored elements and the number of nodes in the graph. We propose a randomized algorithm whose time complexity is <i>O</i>(<i>D</i>log<sub><i>D</i></sub> <i>n</i>) with high probability. Additionally, a deterministic algorithm with a worst-case time complexity of <i>O</i>(<i>D</i>log2<over><i>D</i> <i>n</i>) is presented which considerably improves the best known bound for deterministic algorithms. Moreover, we prove a lower bound of Ω(<i>D</i> log<sub><i>D</i></sub><i>n</i>) for any randomized or deterministic algorithm, implying that the randomized algorithm is asymptotically optimal.