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.