Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6875517 | Theoretical Computer Science | 2018 | 37 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Martin Biely, Peter Robinson, Ulrich Schmid, Manfred Schwarz, Kyrill Winkler,