کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
433980 689665 2015 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Sublinear bounds for randomized leader election
ترجمه فارسی عنوان
محدوده های زیر خطی برای انتخاب رهبر تصادفی
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

This paper concerns randomized leader election in synchronous distributed networks. A distributed leader election algorithm is presented for complete n  -node networks that runs in O(1)O(1) rounds and (with high probability) uses only O(nlog3/2⁡n) messages to elect a unique leader (with high probability). When considering the “explicit” variant of leader election where eventually every node knows the identity of the leader, our algorithm yields the asymptotically optimal bounds of O(1)O(1) rounds and O(n)O(n) messages. This algorithm is then extended to one solving leader election on any connected non-bipartite n-node graph G   in O(τ(G))O(τ(G)) time and O(τ(G)nlog3/2⁡n) messages, where τ(G)τ(G) is the mixing time of a random walk on G. The above result implies highly efficient (sublinear running time and messages) leader election algorithms for networks with small mixing times, such as expanders and hypercubes. In contrast, previous leader election algorithms had at least linear message complexity even in complete graphs. Moreover, super-linear message lower bounds are known for time-efficient deterministic   leader election algorithms. Finally, we present an almost matching lower bound for randomized leader election, showing that Ω(n) messages are needed for any leader election algorithm that succeeds with probability at least 1/e+ε1/e+ε, for any small constant ε>0ε>0. We view our results as a step towards understanding the randomized complexity of leader election in distributed networks.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 561, Part B, 4 January 2015, Pages 134–143
نویسندگان
, , , , ,