Relations Linking Failure Detectors Associated with k-Set Agreement in Message-Passing Systems

The k-set agreement problem is a coordination problem where each process is assumed to propose a value and each process that does not crash has to decide a value such that each decided value is a proposed value and at most k different values are decided. While it can always be solved in synchronous systems, k-set agreement has no solution in asynchronous send/receive message-passing systems where up to t ≥ k processes may crash. A failure detector is a distributed oracle that provides processes with additional information related to failed processes and can consequently be used to enrich the computability power of asynchronous send/receive message-passing systems. Several failure detectors have been proposed to circumvent the impossibility of k-set agreement in pure asynchronous send/receive message-passing systems. Considering three of them (namely, the generalized quorum failure detector ∑k, the generalized loneliness failure detector Lk and the generalized eventual leader failure detector k) the paper investigates their computability power and the relations that link them. It has three mains contributions: (a) it shows that the failure detector k and the eventual version of Lk have the same computational power; (b) it shows that Lk is realistic if and only if k ≽ n=2; and (c) it gives an exact characterization of the difference between Lk (that is too strong for k-set agreement) and Lk (that is too weak for k-set agreement).Ce rapport reprend les différents détecteurs de fautes introduits pour renforcer les systèmes asynchrones et rendre le problème de k-accord décidable. En effet, plusieurs détecteurs de fautes ont été introduits mais certains sont trop forts et d'autres trop faibles. Ce rapport a pour but de déterminer l'espace qui sépare les premiers des seconds afin d'essayer de se rapprocher du détecteur minimal