کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6875517 1441963 2018 37 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Gracefully degrading consensus and k-set agreement in directed dynamic networks
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Gracefully degrading consensus and k-set agreement in directed dynamic networks
چکیده انگلیسی
Finally, we relate (the eventually-forever-variants of) our message adversaries to failure detectors. It turns out that even though VSSC(1,∞) allows to solve consensus and to implement the Ω failure detector, it does not allow to implement Σ. This contrasts the fact that, in asynchronous message-passing systems with a majority of process crashes, (Σ,Ω) is a weakest failure detector for solving consensus. Similarly, although the message adversary VSSC(n,d)+MAJINF(k) allows to solve k-set agreement, it does not allow to implement the failure detector Σk, which is known to be necessary for k-set agreement in asynchronous message-passing systems with a majority of process crashes. Consequently, it is not possible to adapt failure-detector-based algorithms to work in conjunction with our message adversaries.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 726, 23 May 2018, Pages 41-77
نویسندگان
, , , , ,