Chasing the Weakest Failure Detector for k-Set Agreement in Message-Passing Systems

International audienceThis paper continues our quest for the weakest failure detector which allows the k-set agreement problem to be solved in asynchronous message-passing systems prone to process failures. It has two main contributions which will be instrumental to complete this quest. The first contribution is a new failure detector (denoted ΠΣx,y) that has several noteworthy properties. (a) It is stronger than Σx which has been shown to be necessary. (b) It is equivalent to the pair Σ, Ω when x = y = 1 (optimal to solve consensus). (c) It is equivalent to the pair Σn−1, Ωn−1 when x = y = n−1 (optimal for (n − 1)-set agreement). (d) It is strictly weaker than the pair Σx, Ωy (which has been investigated in previous works). (e) It is operational: the paper presents a ΠΣx,y-based algorithm that solves k-set agreement for k ≥ xy (intuitively, x refers to the maximum number of isolated groups of processes and y to the number of leaders in each of these groups). The second contribution of the paper is a proof that, for 1 < k < n − 1, the eventual leaders failure detector Ω k (which eventually provides each process with the same set of k process identities, this set including at least one correct process) is not necessary to solve k-set agreement problem