کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950687 | 1364299 | 2017 | 37 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Self-stabilizing leader election in polynomial steps
ترجمه فارسی عنوان
انتخاب رهبر خود تثبیت کننده در مراحل چندجملهای
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
الگوریتم های توزیع شده، تحمل خطا، خود تثبیت، انتخاب رهبر دائم ناعادلانه،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We propose a silent self-stabilizing leader election algorithm for bidirectional arbitrary connected identified networks. This algorithm is written in the locally shared memory model under the distributed unfair daemon. It requires no global knowledge on the network. Its stabilization time is in Î(n3) steps in the worst case, where n is the number of processes. Its memory requirement is asymptotically optimal, i.e., Î(logâ¡n) bits per processes. Its round complexity is of the same order of magnitude - i.e., Î(n) rounds - as the best existing algorithms designed with similar settings. To the best of our knowledge, this is the first self-stabilizing leader election algorithm for arbitrary identified networks that is proven to achieve a stabilization time polynomial in steps. By contrast, we show that the previous best existing algorithms designed with similar settings stabilize in a non-polynomial number of steps in the worst case.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 254, Part 3, June 2017, Pages 330-366
Journal: Information and Computation - Volume 254, Part 3, June 2017, Pages 330-366
نویسندگان
Karine Altisen, Alain Cournier, Stéphane Devismes, Anaïs Durand, Franck Petit,