Achour Mostéfaoui

Michel Raynal

Julien Stainer

A Mostefaoui

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

Keywords: Asynchronous system, Distributed computing, Eventual leader, Failure detector, Fault-tolerance, Message-passing system, Quorum, Reduction, k-Set agreement, Wait-freedom

This 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 any number of process failures. It has two main contributions which (we hope) will be instrumental to complete this quest.

The first contribution is a new failure detector (denoted ΠΣ x,y ). This failure detector 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 (from which it follows that ΠΣ 1,1 is optimal to solve consensus). (c) It is equivalent to the pair Σ n-1 , Ω n-1 when x = y = n -1 (from which it follows that ΠΣ n-1,n-1 is optimal for (n -1)-set agreement). (d) It is strictly weaker than the pair Σ x , Ω y (which has been investigated in previous works) for the pairs (x, y) such that 1 < y < x < n. (e) It is operational: the paper presents a ΠΣ x,y -based algorithm that solves k-set agreement for k ≥ xy.

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. More precisely, the paper shows that the weakest failure detector for k-set agreement and Ω k cannot be compared.

En quête du détecteur de fautes minimal pour le problème d'accord ensembliste

Résumé : Ce rapport est une avancée dans la recherche du détecteur de fautes minimal permettant de résoudre le problème d'accord ensembliste dans un système asynchrone à communication par messages.

Mots clés : Calcul distribué, détecteur de fautes, k-accord, leader inéluctable, réduction, système asynchrone, tolérance aux fautes, wait-free.

Introduction

The k-set agreement problem This problem is a natural generalization of the consensus problem. It is a coordination problem (also called decision problem) introduced by S. Chaudhuri [START_REF] Chaudhuri | More Choices Allow More Faults: Set Consensus Problems in Totally Asynchronous Systems[END_REF] to explore the relation linking the number of process failures and the minimal number of values that processes are allowed to decide. This problem can be defined as follows [START_REF] Chaudhuri | More Choices Allow More Faults: Set Consensus Problems in Totally Asynchronous Systems[END_REF][START_REF] Raynal | Set agreement. Encyclopedia of Algorithms[END_REF]. Each process proposes a value and every non-faulty process has to decide a value (termination), in such a way that a decided value is a proposed value (validity) and no more than k different values are decided (agreement). The problem parameter k defines the coordination degree: k = 1 corresponds to its most constrained instance (consensus) while k = n -1 corresponds to its weakest non-trivial instance (called set agreement).

Let t be the model parameter that defines the upper bound on the number of processes that may crash in a run, 0 ≤ t < n. If t < k, k-set agreement can be trivially solved in both synchronous and asynchronous systems: k predetermined processes broadcast (write in the shared memory) the values they propose and a process decides the first proposed value it receives (reads from the shared memory). Hence, the interesting setting is when t ≥ k, i.e., when the number of values that can be decided is smaller or equal to the maximal number of processes that may crash in a run.

Round-based algorithms that solve the k-set agreement problem for k ≤ t < n in crash-prone synchronous message-passing systems are presented in [START_REF] Attiya | Distributed Computing: Fundamentals, Simulations and Advanced Topics[END_REF][START_REF] Lynch | Distributed Algorithms[END_REF][START_REF] Raynal | Fault-Tolerant Agreement in Synchronous Message-Passing Systems[END_REF]. These algorithms are optimal in the sense that the processes decide in at most ⌊ t k ⌋ + 1 rounds which has been shown to be a lower bound on the number of rounds for a process to decide 1 . For asynchronous systems where the processes communicate by reading/writing a shared memory or sending/receiving messages, the situation is different, namely, when t ≥ k, the k-set agreement problem has no solution [START_REF] Borowsky | Generalized FLP Impossibility Results for t-Resilient Asynchronous Computations[END_REF][START_REF] Herlihy | The Topological Structure of Asynchronous Computability[END_REF][START_REF] Saks | Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge[END_REF].

Failure detectors Let us observe that in an asynchronous system where the only means for processes to communicate is a read/write shared memory or send/receive message-passing network, no process is able to know if another process has crashed or is only very slow. The concept of a failure detector originates from this simple observation. A failure detector is a device (distributed oracle) that enriches a distributed system by providing alive processes with information on failed processes [START_REF] Chandra | Unreliable Failure Detectors for Reliable Distributed Systems[END_REF]. Several classes of failure detectors can be defined according to the type of information on failures they provide to processes (see [START_REF] Raynal | Failure Detectors for Asynchronous Distributed Systems: an Introduction[END_REF] for an introduction to failure detectors).

Given a system model M (e.g., asynchronous read/write shared memory system model or asynchronous send/receive messagepassing system model) a failure detector A is stronger than a failure detector B with respect to M (denoted A M B or B M A) if there is an algorithm (called reduction) that builds B in M enriched with A (we then also say that B is weaker than A). If A is stronger than B and B is stronger than A, then A and B are equivalent with respect to M (denoted A ≃ M B). If A M B and B M A then A is strictly stronger than B -equivalently B is strictly weaker than A-(denoted A ≻ M B or B ≺ M A). If A M B and B M A (denoted A ≃ M B), A and B cannot be compared in M.

Failure detectors have been investigated since 2000 [START_REF] Mostéfaoui | k-Set Agreement with Limited Accuracy Failure Detectors[END_REF] to circumvent the "t ≥ k" impossibility result associated with the k-set agreement problem in asynchronous systems. (Random oracles to solve the k-set agreement problem have also been investigated [START_REF] Mostéfaoui | Randomized Set Agreement[END_REF].) The question of the weakest failure detector to solve the k-set agreement problem (k > 1) has been stated first in [START_REF] Raynal | In Search of the Holy Grail: Looking for the Weakest Failure Detector for Wait-free Set Agreement[END_REF]. A failure detector A is the weakest failure detector that allows a problem P to be solved in a model M if any failure detector B that allows P to be solved in M is such that B M A.

The weakest failure detector for k-set agreement in shared memory systems where t = n -1 The eventual leader failure detector Ω introduced in [START_REF] Chandra | The Weakest Failure Detector for Solving Consensus[END_REF] is the weakest failure detector that allows consensus (i.e., 1-set agreement) to be solved in shared memory systems where any number of processes may crash [START_REF] Lo | Using Failure Detectors to Solve Consensus in Asynchronous Shared-memory Systems[END_REF]. Ω ensures that there is an unknown but finite time after which all the processes have the same non-faulty leader (before that time, there is an anarchy period during which each process can have an arbitrarily changing faulty or non-faulty leader). At the other end of the spectrum (k = n -1), the failure detector Ω n-1 (anti-omega) has been introduced in [START_REF] Zielinski | Anti-Omega: the Weakest Failure Detector for Set Agreement[END_REF] where it is shown to be the weakest failure detector that allows (n -1)-set agreement to be solved in these systems.

A simple generalization of Ω and [START_REF] Raynal | Rump Session at 26th ACM Symposium on Principles of Distributed Computing (PODC'07)[END_REF] where it is conjectured to be the weakest failure detector class for solving k-set agreement in asynchronous read/write shared memory systems. This conjecture has been proved in [START_REF] Gafni | The Weakest Failure Detector for Solving k-Set Agreement[END_REF]. A failure detector of the class Ω k provides each process with a (possibly always changing) set of k processes such that, after some unknown but finite time, all the sets that are output have in common the same non-faulty process. The optimality of Ω k to solve k-set agreement in shared memory systems seems to be related to the fact that this problem is equivalent to the k-simultaneous consensus problem [START_REF] Afek | The k-Simultaneous Consensus Problem[END_REF] in which each process executes k independent consensus instances (to which it proposes the same input value) and is required to terminate in one of them. As indicated in [START_REF] Zielinski | Anti-Omega: the Weakest Failure Detector for Set Agreement[END_REF], this problem has been instrumental in determining the weakest failure detector for wait-free solving the (n -1)-set agreement problem in asynchronous shared memory systems.

Ω n-1 denoted Ω k , 1 ≤ k ≤ n -1, (Ω 1 is Ω) has been introduced in
The cases k = 1 and k = n-1 in message-passing systems where t = n-1 When k = 1, as already indicated k-set agreement boils down to consensus, and it is know that the failure detector denoted Ω is the weakest to solve consensus in asynchronous message-passing systems where t < n/2 [START_REF] Chandra | The Weakest Failure Detector for Solving Consensus[END_REF]. This lower bound result is extended to any value of t in [START_REF] Delporte-Gallet | Tight Failure Detection Bounds on Atomic Object Implementations[END_REF] where the failure detector Σ is introduced and is shown that Σ × Ω is the weakest failure detector to solve consensus in message-passing systems when t < n. This means that Σ is the minimal additional power (as far as information on failures is concerned) required to overcome the barrier t < n/2 and attain t ≤ n -1. Actually the power provided by Σ is the minimal one required to implement a shared register in a message-passing system [START_REF] Bonnet | A Simple Proof of the Necessity of the Failure Detector Σ to Implement an Atomic Register in Asynchronous Messagepassing Systems[END_REF][START_REF] Delporte-Gallet | Tight Failure Detection Bounds on Atomic Object Implementations[END_REF]. Σ provides each process with a quorum (set of process identities) such that the values of any two quorums (each taken at any time) intersect, and there is a finite time after which any quorum includes only correct processes. Fundamentally, Σ prevents partitioning. A failure detector Σ × Ω outputs a pair of values, one for Σ and one for Ω.

The Loneliness failure detector (denoted L) has been proposed in [START_REF] Delporte-Gallet | The Weakest Failure Detector for Message Passing Set-Agreement[END_REF] where it is proved that it is the weakest failure detector for solving (n -1)-set agreement in the asynchronous message-passing model with t = n -1. Such a failure detector provides each process p with a boolean (that p can only read) such that the boolean of at least one process remains always false and, if all but one process crash, the boolean of the remaining process becomes and remains true forever. Let us notice that the weakest failure detector for (n -1)-set agreement is not the same in the read/write shared memory model (where it is Ω n-1 ) and the send/receive message-passing model (where it is L).

The quest for the weakest failure detector for k-set agreement in message-passing systems This quest seems to be one of the most difficult research topics in the theory of fault-tolerant distributed computing. Since a few years, several new failure detectors have been proposed for solving k-set agreement in asynchronous message passing systems prone to any number of crashes, but so far finding the weakest still remains a challenge.

A recent survey on failure detectors proposed so far to solve k-set agreement has appeared in [START_REF] Raynal | Failure Detectors to solve Asynchronous k-set Agreement: a Glimpse of Recent Results[END_REF]. The interested reader will also find in [START_REF] Mostéfaoui | Relations Linking Failure Detectors Associated with k-Set Agreement in Message-passing Systems[END_REF] a study on relations linking some of these failure detectors. Here we only present the failure detector Σ x introduced in [START_REF] Bonnet | On the Road to the Weakest Failure Detector for k-Set Agreement in Message-passing Systems[END_REF] because it is central to the paper. Σ x generalizes the quorum failure detector class Σ introduced in [START_REF] Delporte-Gallet | Tight Failure Detection Bounds on Atomic Object Implementations[END_REF] (Σ 1 is Σ). This failure detector provides each process with a set (quorum) such that at least two quorums do intersect in any set of x + 1 quorums (whose values are taken at any times). Moreover, there is a finite (but unknown) time after which the quorum of any process includes only non-faulty processes. Two main results are proved in [START_REF] Bonnet | On the Road to the Weakest Failure Detector for k-Set Agreement in Message-passing Systems[END_REF]: (a) as far as information on failures is concerned, Σ k is a necessary requirement to solve k-set agreement; (b) Σ n-1 is sufficient to solve (n -1)-set agreement. Interestingly, a Σ x -based algorithm is presented in [START_REF] Bouzid | Anti-Ω k × Σ k )-Based k-Set Agreement Algorithms[END_REF]

that solves k-set agreement for k ≥ n -⌊ n x+1 ⌋.
Contributions of the paper This paper is a new step in the quest for the weakest failure detector for k-set agreement in messagepassing systems. It has two main contributions.

• The first contribution is the definition and the investigation of a new failure detector class denoted ΠΣ x,y .

-Intuitively ΠΣ x,1 (1) prevents the system from partitioning into more than k independent subsets and (2) guarantees that the processes of at least one of these subsets agree on a common leader. ΠΣ x,y can be seen as y independent instances of ΠΣ x,1 in which item (2) is has to be guaranteed in only one of these instances. -Let AMP denote the asynchronous message-passing system model where up to n -1 process may crash. The properties of ΠΣ x,y are the following: (a

) ΠΣ 1,y ≃ AMP Σ 1 , Ω y ; (b) ΠΣ x,n-1 ≃ AMP Σ x ; (c) ΠΣ x,y AMP Σ x , Ω y for 1 ≤ x, y ≤ n and ΠΣ x,y ≺ AMP Σ x , Ω y for 1 < y < x < n.
It follows from (a) and (b) that ΠΣ 1,1 and ΠΣ n-1,n-1 are the weakest failure detectors to solve k-set agreement for k = 1 and k = n -1, respectively. For 1 ≤ k ≤ n -1, we have the following. An algorithm based on the pair of failure detectors Σ x , Ω y is presented in [START_REF] Bouzid | Anti-Ω k × Σ k )-Based k-Set Agreement Algorithms[END_REF] that solves k-set agreement for k ≥ xy (let BT-2010 denote this algorithm). Moreover, it is shown in that paper that there is no Σ x , Ω y -based k-set agreement algorithm when (k < xy) ∧ (n ≥ 2xy).

Actually, an appropriate modification of BT-2010 provides us with a ΠΣ x,y -based k-set algorithm that has the same properties (listed above) as BT-2010. The important point is here the following one: while BT-2010 and the proposed algorithm work for the same pairs (x, y), it follows from item (c) that the proposed algorithm is based on weaker information on failures than BT-2010.

• The second contribution of the paper (which has been obtained thanks to the previous failure detector ΠΣ x,y ) is the following: Ω k is not necessary to solve k-set agreement when 1 < k < n -1. Combined with the fact that Σ k is necessary [START_REF] Bonnet | On the Road to the Weakest Failure Detector for k-Set Agreement in Message-passing Systems[END_REF], this result restricts the area we have to look for in order to discover the weakest failure detector for k-set agreement in message-passing systems for 1 < k < n -1.

Roadmap

The paper is made up of 7 sections. Section 2 presents the base computation model and the k-set agreement problem. Section 3 presents the eventual leaders and generalized quorums failure detectors. Section 4 defines the new failure detector ΠΣ x,y and shows that it is strictly weaker than Σ x , Ω y for 1 < y < x < n. Assuming k ≥ xy, Section 5 presents an algorithm that solves the k-set agreement problem in the asynchronous message-passing model enriched with ΠΣ x,y . Section 6 shows that Ω k is not necessary for solving k-set agreement (when 1 < k < n -1). Finally, Section 7 concludes the paper.

2 Base computation model and k-set agreement

Computation model Process model

The system consists of a set of n sequential processes denoted p 1 , ..., p n . P = {1, . . . , n} is the set of process identities. Each process executes a sequence of (internal or communication) atomic steps. A process executes its code until it possibly crashes (if it ever crashes). After it has crashed, a process executes no more steps. A process that crashes in a run is said faulty in that run, otherwise it is correct. Given a run, C and F denote the set processes that are correct and the set of processes that are faulty in that run, respectively. Up to t = n -1 processes may crash in a run, hence, 1 ≤ |C| ≤ n.

Communication model

The processes communicate by executing atomic communication steps which are the sending or the reception of a message. Every pair of processes is connected by a bidirectional channel. The channels are failure-free (no creation, alteration, duplication or loss of messages) and asynchronous (albeit the time taken by a message to travel from its sender to its receiver is finite, there is no bound on transfer delays). The notation "broadcast MSG_TYPE(m)" is used as a (non-atomic) shortcut for "for each j ∈ P do send MSG_TYPE(m) to p j end for" (let us observe that p i sends then the message also to itself).

Underlying time model

The underlying time model is the set N of natural integers. As we are in an asynchronous system, this time notion is not accessible to the processes (hence, the model is sometimes called time-free model). It can only be used from an external observer point of view to state or prove properties. Time instants are denoted τ , τ ′ , etc.

Notation The previous asynchronous crash-prone message-passing system model is denoted AMP[∅]. AMP stands for "Asynchronous Message-Passing"; ∅ means this is the "base" system (not enriched with a failure detector).

The k-Set agreement problem

As already indicated in the Introduction, the k-set agreement problem has been introduced by Soma Chaudhuri [START_REF] Chaudhuri | More Choices Allow More Faults: Set Consensus Problems in Totally Asynchronous Systems[END_REF]. It generalizes the consensus problem (that corresponds to k = 1). It is defined as follows. Each process proposes a value and has to decide a value in such a way that the following properties are satisfied:

• Termination. Every correct process decides a value.

• Validity. A decided value is a proposed value.

• Agreement. At most k different values are decided.

Existing families of failure detectors

This section presents failure detectors that have been proposed in the quest of the weakest failure detector for k-set agreement. The system model AMP[∅] enriched with a failure detector A is denoted AMP[A].

A failure detector provides each alive process with a read-only local variable. Let xxx i be such a variable of process p i . Let xxx τ i denotes the value of xxx i at time τ .

The Ω k and Ω k families

The eventual leaders failure detectors of the families Ω k and Ω k provide each process p i with a local variable denoted leaders i . They originates from

Ω [9] (Ω 1 ≡ Ω 1 ≡ Ω). Ω k is a straightforward generalization of Ω n-1 (introduced in [30]
). Ω k has been shown to be the weakest failure detector to solve k-set agreement in asynchronous shared memory systems with any number of process crashes in [START_REF] Gafni | The Weakest Failure Detector for Solving k-Set Agreement[END_REF].

Base properties Let us consider the following properties on the sets leaders i .

• Validity. ∀i, ∀τ :

leaders τ i is a set of k process identities. • Strong eventual leadership. ∃ LD, τ : (LD ∩ C = ∅) ∧ (∀τ ′ ≥ τ, ∀i ∈ C : leaders τ ′ i = LD). • Weak eventual leadership. ∃ ℓ ∈ C, τ : (∀τ ′ ≥ τ, ∀i ∈ C : ℓ ∈ leaders τ ′ i ).
Validity combined with strong eventual leadership states that, after some unknown but finite time, all correct processes have the same set of k leaders and at least one of them is a correct process. Validity combined with weak eventual leadership requires only that the correct processes eventually share a common correct leader.

The Ω k family This family (introduced in [START_REF] Neiger | Failure Detectors and the Wait-free Hierarchy[END_REF]) includes the failure detectors that satisfy the validity and strong eventual leadership properties.

The Ω k family This family (introduced in [START_REF] Raynal | Rump Session at 26th ACM Symposium on Principles of Distributed Computing (PODC'07)[END_REF]) includes the failure detectors that satisfy the validity and weak eventual leadership properties.

The Σ k and Π k families

The Σ k family As noticed in the Introduction, the generalized quorum failure detector Σ k (introduced in [START_REF] Bonnet | On the Road to the Weakest Failure Detector for k-Set Agreement in Message-passing Systems[END_REF]) is a generalization of the quorum failure detector Σ introduced in [START_REF] Delporte-Gallet | Tight Failure Detection Bounds on Atomic Object Implementations[END_REF] where it is shown to be the weakest failure detector to implement a register in AMP [∅].

Σ k provides each process p i with a set qr i (called quorum) that satisfies the following properties (after a process p i has crashed, we have qr i = P by definition). The self-inclusion property (which does not appear in [START_REF] Bonnet | On the Road to the Weakest Failure Detector for k-Set Agreement in Message-passing Systems[END_REF]) is considered here because it allows for a simpler formulation of algorithms.

• Self-inclusion. ∀ i ∈ P, ∀ τ : i ∈ qr τ i . • Quorum liveness. ∃ τ : ∀ i ∈ C, ∀ τ ′ ≥ τ : qr τ ′ i ⊆ C. • Quorum intersection. ∀ id 1 , . . . , id x+1 ∈ P, ∀ τ 1 , . . . , τ x+1 : ∃ i, j : (i = j) ∧ (qr τi idi ∩ qr τj idj = ∅).
It is shown in [START_REF] Bonnet | On the Road to the Weakest Failure Detector for k-Set Agreement in Message-passing Systems[END_REF] that Σ k is necessary when one wants to solve k-set agreement in AMP[∅].

The Π k family The failure detector Π k (introduced in [START_REF] Bonnet | On the Road to the Weakest Failure Detector for k-Set Agreement in Message-passing Systems[END_REF]) is an extension of Σ k to which it adds the following property.

• Eventual leadership. ∃ LD, τ : (|LD| = k) ∧ (∀τ ′ ≥ τ, ∀i ∈ C : qr τ ′ i ∩ LD = ∅).
It is shown in [START_REF] Bonnet | On the Road to the Weakest Failure Detector for k-Set Agreement in Message-passing Systems[END_REF] that Π k and the pair

Σ k , Ω k are equivalent, i.e., Π k can be built in AMP[Σ k , Ω k ] and Σ k , Ω k can be built in AMP[Π k ].
It is also shown in [START_REF] Bonnet | On the Road to the Weakest Failure Detector for k-Set Agreement in Message-passing Systems[END_REF] that Π n-1 and L are equivalent. If follows from these observations that Π 1 and Π n-1 are the weakest failure detectors for k = 1 and k = n -1. Unfortunately, as shown in [START_REF] Biely | Easy Impossibility Proofs for k-Set Agreement in Message-passing Systems[END_REF][START_REF] Bouzid | Anti-Ω k × Σ k )-Based k-Set Agreement Algorithms[END_REF], Π k does not allow to solve k-set agreement for

1 < k < n -1.
4 The family of failure detectors ΠΣ x,y

Definition

The definition of ΠΣ x,y is incremental, first is defined ΠΣ x and then ΠΣ x,y .

The failure detector ΠΣ x A failure detector ΠΣ x provides each process p i with a set qr i and a variable leader i which define the current quorum and the current leader of p i . It is defined by the following properties.

• Self-inclusion. ∀ i ∈ P, ∀ τ : i ∈ qr τ i . • Quorum liveness. ∃ τ : ∀ i ∈ C, ∀ τ ′ ≥ τ : qr τ ′ i ⊆ C. • Quorum intersection. ∀ id 1 , . . . , id x+1 ∈ P, ∀ τ 1 , . . . , τ x+1 : ∃ i, j : (i = j) ∧ (qr τi idi ∩ qr τj idj = ∅). • Eventual partial leadership. ∃ℓ ∈ C : ∀i ∈ C: ∀τ : ∃τ i , τ ℓ ≥ τ : qr τi i ∩ qr τ ℓ ℓ = ∅ ⇒ ∃τ : ∀τ ′ ≥ τ : leader τ ′ i = ℓ .
The self-inclusion, liveness and intersection properties are the properties that define Σ x : after some time the quorum of any correct process contains only correct processes (liveness) and any set of x + 1 quorums contains two intersecting quorums (intersection). Hence, ΠΣ x Σ x . Eventual partial leadership states that there is a correct process p ℓ such that, for any correct process p i whose quorum qr i intersects infinitely often its quorum qr ℓ (left part of the implication), then eventually p ℓ is forever the leader of p i (right part of the implication).

The failure detector ΠΣ x,y ΠΣ x is ΠΣ x,1 . More generally, ΠΣ x,y provides each process p i with an array FD i [1..y] such that for each each j, 1 ≤ j ≤ y, FD i [j] is a pair containing a quorum FD i 4.2 ΠΣ x,y vs Σ x , Ω y A failure detector Σ x , Ω y provides each process p i with two independent read-only local variables: qr i that satisfies the properties defined by Σ x , and leaders i that satisfies the properties defined by Ω y .

Lemma 1. Let 1 ≤ x, y ≤ n -1. ΠΣ x,y AMP Σ x , Ω y .
Proof Let qr i be the output of Σ x at process p i . For any j ∈ [1..y], let FD i [j].qr = qr i . Hence, each quorum FD i [j].qr inherits from the liveness and intersection properties of Σ x and consequently the vector safety property of ΠΣ x,y is satisfied. The proof of the vector liveness property of ΠΣ x,y is similar to the proof showing that vector-Ω can be built from Ω n-1 [START_REF] Zielinski | Anti-Omega: the Weakest Failure Detector for Set Agreement[END_REF]. Each process p i executes Algorithm 1 in which susp_nb i [1..n] is a local variable of p i initialized to [0, . . . , 0]. Moreover, the processes are provided with a reliable broadcast operation denoted rel_broadcast. Such an operation ensures that, if a message is delivered by a process (which can be correct or not), then it is delivered by all correct processes. This operation can be implemented in AMP[∅] (e.g., [START_REF] Chandra | Unreliable Failure Detectors for Reliable Distributed Systems[END_REF][START_REF] Raynal | Communication and Agreement Abstractions for Fault-Tolerant Asynchronous Distributed Systems[END_REF]). Each process p i repeatedly broadcasts (with rel_broadcast) its current value of leaders i (line 01). When, it is delivered LEADER(ld ) (01) repeat forever rel_broadcast LEADER(leaders i ) end repeat.

(02) when LEADER(ld ) is delivered: (03) for each j / ∈ ld do susp_nb i [j] ← susp_nb i [j] + 1 end for; (04) let j 1 , j 2 , . . . , jn be a permutation of {1, . . . , n} such that

(susp_nb i [j 1 ], j 1 ) < (susp_nb i [j 2 ], j 2 ) < • • • < (susp_nb i [jn], jn); (05) for each x ∈ {1, . . . , y} do FD i [x].leader ← jx end for.
Algorithm 1: From Σ x , Ω y to ΠΣ x,y (code for p i ) a process p i first increases the suspicion number susp_nb i [j] of all j / ∈ ld (line 03). It then sorts process identities according to the lexicographical order on the pairs {(susp_nb i [j], j)} 1≤j≤n (line 04). Finally, for each x ∈ [1..y], p i assigns to FD i [x].leader (line 05) the xth process index (as defined from the previous order).

Let us observe that, due to the weak eventual leadership property of Ω y , there is a correct process p ℓ that, after some finite time, belongs permanently to all local variables leaders i . It follows from this observation and the rel_broadcast() operation that all the local variables susp_nb i [ℓ] will stop increasing and stabilize to the very same value. As Ω y outputs sets of y processes, this is true for m processes p ℓ1 , p ℓ2 , ..., with 1 ≤ m ≤ y. It then follows from line 05 that, for all the processes p i and for each z ∈ [1..m], the local variables FD i [z].leader stabilizes to the very same process index and there is one entry j such that we eventually have forever FD i [j].leader = ℓ such that p ℓ is a correct process. As, when considering the distributed object FD[j], all processes have the same correct leader p ℓ , the eventual partial leadership property of ΠΣ x is satisfied (more precisely, whatever the value of the left part of the implication, the right part of the implication is satisfied). Consequently the vector liveness property of ΠΣ x,y is also satisfied, which concludes the proof of the lemma.

✷ Lemma 1 Theorem 1. Let 1 ≤ y ≤ n -1. ΠΣ 1,y ≃ AMP Σ 1 , Ω y .
Proof Taking x = 1 in Lemma 1 we have ΠΣ 1,y AMP Σ 1 , Ω y . Hence, we have only to show that Σ 1 , Ω y AMP ΠΣ 1,y . Let qr i of Σ 1 be the output of FD i [START_REF] Afek | The k-Simultaneous Consensus Problem[END_REF].qr. Hence, the quorums qr i inherit the liveness and intersection properties of FD i [START_REF] Afek | The k-Simultaneous Consensus Problem[END_REF].qr that trivially satisfy the properties defining Σ 1 .

Let leaders i be any subset of size y that contains ∪ 1≤j≤y {FD i [j].leader}. Due to the vector liveness property of ΠΣ 1,y , there is an entry j such that FD[j] satisfies the eventual partial leadership (Observation O1). Moreover, as x = 1, any pair of quorums output by FD[j] do intersect (Observation O2). It follows from O1 and O2 that there is a correct process p ℓ such that, for each correct process p i , there is a time after which the predicate FD i [j].leader = ℓ remains forever true. Consequently, there is a finite time after which the predicate ℓ ∈ leaders i remains forever true at any correct process p i , from which follows the weak eventual leadership property of Ω y .

✷ T heorem 1

Theorem 2. Let 1 ≤ x ≤ n -1. ΠΣ x,n-1 ≃ AMP Σ x .
Proof Taking y = n -1 in Lemma 1 we have ΠΣ x,n-1 AMP Σ x , Ω n-1 . Hence, we have only to show that Σ x , Ω n-1

AMP ΠΣ x,n-1 .
It is shown in [START_REF] Bonnet | On the Road to the Weakest Failure Detector for k-Set Agreement in Message-passing Systems[END_REF] (Corollary 2 in [START_REF] Bonnet | On the Road to the Weakest Failure Detector for k-Set Agreement in Message-passing Systems[END_REF]) that

Σ x AMP Σ x+1 AMP • • • AMP Σ n-1 AMP Ω n-1 .
Moreover, it follows directly from their definitions that Ω n-1 AMP Ω n-1 . It follows that Σ x AMP Σ x , Ω n-1 which completes the proof of the theorem.

✷ T heorem 2 Lemma 2. Let 1 ≤ y < n. ΠΣ y+1,1 AMP Ω y .
Collection des Publications Internes de l'Irisa c IRISA

The proof of this lemma is given in Appendix A.

Theorem 3. Let 1 < y < x < n. ΠΣ x,y ≺ AMP Σ x , Ω y .
Proof ΠΣ x,y AMP Σ x , Ω y follows from Lemma 1. Hence, we have to show that ΠΣ x,y AMP Σ x , Ω y . Let us first observe that ΠΣ y+1,1 AMP ΠΣ y+1,y . This is easily obtained by providing each FD[j] of the array FD[1.

.y] of ΠΣ y+1,y with the outputs supplied by ΠΣ y+1,1 . On an other side, (as shown in [START_REF] Bonnet | On the Road to the Weakest Failure Detector for k-Set Agreement in Message-passing Systems[END_REF]) Σ z is strictly stronger than Σ z+1 for 1 ≤ z < n -1 and, consequently, ΠΣ y+1,y AMP ΠΣ x,y for y < x. It follows from Lemma 2 (i.e., ΠΣ y+1,1 AMP Ω y ) that, as ΠΣ y+1,1 is stronger than ΠΣ x,y , we have ΠΣ x,y AMP Ω y which proves the theorem. ✷ T heorem 3

Remark A main difference between ΠΣ x,y and Σ x , Ω y lies in the fact that the eventual correct leader elected by Ω y has to be the same for all correct processes, while ΠΣ x,y requires only that the correct processes of a subset (dynamically defined by one of the y Σ x failure detectors) agree on a common leader. Hence, the scope of the leadership provided by ΠΣ x,y is not required to be the whole system but only a subset of it.

5 Solving k-Set agreement in AMP[ΠΣ x,y ]

This paper presents an algorithm that solves the k-set agreement problem in AMP[ΠΣ x,y ]. This algorithm is similar to the one presented in [START_REF] Bouzid | Anti-Ω k × Σ k )-Based k-Set Agreement Algorithms[END_REF] which in turn is an adaptation of the algorithms described in [START_REF] Guerraoui | The Alpha of Indulgent Consensus[END_REF][START_REF] Raynal | In Search of the Holy Grail: Looking for the Weakest Failure Detector for Wait-free Set Agreement[END_REF].

The Alpha x abstraction

This abstraction has been introduced in [START_REF] Guerraoui | The Alpha of Indulgent Consensus[END_REF] to capture the safety property of consensus and generalized in [START_REF] Raynal | In Search of the Holy Grail: Looking for the Weakest Failure Detector for Wait-free Set Agreement[END_REF] to capture the safety property of k-set agreement in crash-prone systems. Corresponding implementations in read/write shared memory systems and send/receive message-passing systems can be found in [START_REF] Guerraoui | The Alpha of Indulgent Consensus[END_REF][START_REF] Raynal | In Search of the Holy Grail: Looking for the Weakest Failure Detector for Wait-free Set Agreement[END_REF].

Let ⊥ be a default value that cannot be proposed by processes. Alpha x is an object initialized to ⊥ that may store up to x different values proposed by processes. It is an abstraction (object) that provides processes with a single operation denoted propose(r, v) (where r is a round number and v a proposed value) that returns a value to the invoking process. The round number plays the role of a logical time that allows identifying the propose() invocations. It is assumed that distinct processes use different round numbers and successive invocations by the same process use increasing sequence numbers. Alpha x is a kind of abortable object in the sense that propose() invocations are allowed to return the default value ⊥ (i.e., abort) in specific concurrency-related circumstances (as defined from the obligation property, see below). More precisely, the Alpha x objects used in this paper are defined by the following specification in which the obligation property takes explicitly into account the fact that we are interested into an Alpha x object that will be implemented on top of AMP[Σ x ] (which is a strictly stronger underlying model than AMP[∅]). Differently from the obligation property stated in [START_REF] Bouzid | Anti-Ω k × Σ k )-Based k-Set Agreement Algorithms[END_REF][START_REF] Guerraoui | The Alpha of Indulgent Consensus[END_REF][START_REF] Raynal | In Search of the Holy Grail: Looking for the Weakest Failure Detector for Wait-free Set Agreement[END_REF] the previous obligation property is Σ x -aware which allows for a weaker property (the Alpha x object used in [START_REF] Bouzid | Anti-Ω k × Σ k )-Based k-Set Agreement Algorithms[END_REF] is implemented on top of AMP[Σ x ] but its specification is not Σ x -aware). More precisely, our obligation property allows concurrent invocations of propose() to return non-⊥ values as soon as the quorums of the invoking processes do not intersect during these invocations.

An algorithm implementing the previous Alpha x object in AMP[Σ x ] is described in Appendix B.

k-set agreement in AMP[ΠΣ x,y ]

This section presents a simple algorithm that implements k-set agreement in AMP[ΠΣ x,y ] for k ≥ xy. It is as the algorithm presented in [START_REF] Bouzid | Anti-Ω k × Σ k )-Based k-Set Agreement Algorithms[END_REF]: it uses a base algorithm (similar to the one introduced in [START_REF] Guerraoui | The Alpha of Indulgent Consensus[END_REF]) that solves x-set agreement in AMP[ΠΣ x,1 ] and then assuming k ≥ xy (as in [START_REF] Afek | The k-Simultaneous Consensus Problem[END_REF][START_REF] Bouzid | Anti-Ω k × Σ k )-Based k-Set Agreement Algorithms[END_REF]) it uses y instances of this base to solve k-set agreement in AMP[ΠΣ x,y ].

x-Set agreement in AMP[ΠΣ x,1 ] Algorithm 2 solves x-set agreement in AMP[ΠΣ x,1 ]. A process p i invokes ks_propose x,1 (v i ) where v i is the value it proposes. It decides a value d when it executes the statement return (d) which terminates its invocation. The local variable r i is the local round number (as it is easy to see, each process uses increasing round numbers and no two distinct processes use the same round numbers).

A process loops until it decides. If during a loop iteration p i is such that leader i = i (leader i is one of the two local outputs provided by ΠΣ x,1 ), p i invokes the Alpha x object to try to deposit its value v i into it (the success depends on the concurrency and quorums pattern). If a non-⊥ value is returned by this invocation, p i broadcasts it (with the reliable broadcast operation). A process decides as soon as it is delivered a DECISION() message.

operation ks_propose x,1 (v i ): (01) dec i ← ⊥; r i ← i; (02) while (dec i = ⊥) do (03) if (leader i = i) then Alpha x .propose(r i , v i ); r i ← r i + n end if (04) end while; (05) rel_broadcast DECISION(dec i ).
when DECISION(d) is delivered: return (d). [START_REF] Afek | The k-Simultaneous Consensus Problem[END_REF][START_REF] Bouzid | Anti-Ω k × Σ k )-Based k-Set Agreement Algorithms[END_REF], a simple k-set algorithm can be obtained by launching concurrently y instances of Algorithm 2, the jth one relying on the component F D[j] of the failure detector AMP[ΠΣ x,y ]. A process decides the value returned by the first of the y instances that locally terminates. As there are y instances of Algorithm 2 and at most x values can be decided in each of them, it follows that at most xy different values can be decided. Moreover, as at least one F D[j] is a ΠΣ x,y failure detector, it follows that the correct processes decide (if not done before) in at least one of the y instances of Algorithm 2. Let us observe that, in such a "worst" case where the processes decide in the same instance, at most x values are decided).

The proof of this theorem is given in

Appendix C. k-Set agreement in AMP[ΠΣ x,y ] As in
6 Ω k is not necessary for k-set agreement when 1 < k < n -1

Lemma 3. Let 1 < k < n -1. Ω k cannot be built in AMP[ΠΣ k,1 ].
Proof Preliminaries. Let us first observe that (1 < k < n -1) ⇔ (n ≥ k + 2 ≥ 4). The proof is by contradiction. It consists in building distinct runs that are indistinguishable for some processes. The impossibility will follow from the fact that, while each of these runs is provided with correct outputs from ΠΣ k,1 , there are runs in which Ω k has to provide each process with a set containing infinitely often k + 1 process identities.

Hence, let us assume that there is an algorithm A that builds Ω k in AMP[ΠΣ x,1 ]. Let us remember that leaders i denotes the output of Ω k while qr i and ld i (instead of leader i to prevent confusion) are the output provided to p i by ΠΣ x,1 .

The runs considered in the proof are such that the processes p 1 , p 2 and p 3 on one side and the processes p i with i ∈ [4..k + 2] on another side play special roles. Moreover, (if it exists) each process p j with j ∈ [k + 3..n] is initially crashed in all runs.

The "α" runs. For all i ∈ [4..k + 2], let α i be a run in which all processes but p i have initially crashed and p i does not crash. Hence, ∀ τ , qr τ i = {i} and ld τ i = i are correct outputs of ΠΣ x,1 in the run α i . As p i is the only correct process in α i , it follows from the very existence of algorithm A that there is a time τ i such that ∀τ ≥ τ i : i ∈ leaders τ i . Let α [1..3] be a run in which p 1 , p 2 and p 3 do not crash and all other processes have initially crashed. For each i ∈ [1..3] and any time τ , qr τ i = {1, 2, 3} and ld τ i = lead α (where lead α ∈ {1, 2, 3}) are correct outputs of ΠΣ x,1 in the run α [1..3] . Due to the existence of A, there is a correct process p ℓα (with ℓα ∈ [1..3]) and a time τ

[1..3] such that ∀τ ≥ τ [1..3] , ∀ i ∈ {1, 2, 3}, ℓα ∈ leaders τ i . Let τ α = max({τ i } i∈[4..k+2] , τ [1..3]
) and α be a run in which (1) all processes p i such that i > k + 2 have initially crashed, (2) the other processes are correct, (3) all messages but the ones exchanged by p 1 , p 2 and p 3 are delayed until τ α , and (4), up to τ α , the outputs of ΠΣ x,1 are the same in α and α [1..3] for p 1 , p 2 and p 3 and the same in α and α i for p i with i ∈ [4..k + 2] (the important point to observe here is that, due to the fact that the processes p j with k + 2 < j ≤ n have initially crashed, the intersection property of ΠΣ x,1 is satisfied). Considering the runs previously defined, we have the following:

• For any i ∈ [4..k + 2], p i cannot distinguish α and α i up to time τ α .

• Each of p 1 , p 2 and p 3 cannot distinguish α and α [1..3] up to time τ α .

It follows that, considering the outputs of algorithm A in run α, we have ℓα ∈ leaders τα i for i ∈ {1, 2, 3} and i ∈ leaders τα

i for i ∈ [4..k + 2].
The "β" runs. Let τ f α be a time in run α after which all messages sent before τ α have been received. Moreover, for each i ∈ [4..k + 2], let β i be a run in which all processes take the same steps as in run α until τ f α and then all processes but p i crash. Let us observe that, in the run β i , correct outputs of ΠΣ x,1 at p i can still be ∀τ : qr τ i = {i} and ld τ i = i. Let β [1..3]\{ℓα} be the same run as α until τ f α and where all processes but p i such that i ∈ [1..3] \ {ℓα} crash just after τ f α . In

β [1..3]\{ℓα} , ∀τ ≥ τ f α , qr τ i = [1..3] \ {ℓα} and ld τ i = lead β (with lead β ∈ [1..3] \ {ℓα}) are correct outputs of ΠΣ x,1 at each process p i such that i ∈ [1..3] \ {ℓα}.
Due to the existence of A, there is a finite time τ β such that (a) in the run β [1..3]\{ℓα} , there is ℓβ such that ℓβ ∈ [1..3] \ {ℓα} and ℓβ ∈ leaders j for each j ∈ [1..3] \ {ℓα} (let us remember that p ℓα has crashed just after τ f α ) and (b) due to the very definition of each run

β i for i ∈ [4..k + 2], we have i ∈ leaders τ β i in run β i .
Let β be a run that is the same as run α until time τ f α and where the messages sent after τ f α (1) by or to the processes p i where i ∈ [4..k + 2] and ( 2) by p ℓα are delayed until after τ β (this means that each process i where i ∈ [1..3] \ {ℓα} cannot distinguish if p ℓα is alive or crashed; differently, as it receives their messages p ℓα does not suspect these two processes).

In the run β, let the outputs of ΠΣ x,1 be the same as in the run α until time τ f α , and then forever be (1) the same as in β [1..3]\{ℓα} for p i with i ∈ [1..3] \ {ℓα}, (2) the same as in β i for p i with i ∈ [4..k + 2], and (3) qr ℓα = {1, 2, 3} and ld ℓα = lead β for p ℓα (as before, the important point to observe here is that, due to the fact that the processes p j with k + 2 < j ≤ n have initially crashed, the intersection property of ΠΣ x,1 is satisfied). Considering the runs previously defined, we have the following:

• For any i ∈ [4..k + 2], p i cannot distinguish β and β i .

• For each i ∈ [1..3] \ {ℓα}, p i cannot distinguish β and β [1..3]\{ℓα} .
It follows that, considering the outputs of algorithm A in the run β, we have ℓβ ∈ leaders

τ β i for i ∈ [1..3] \ {ℓα} and i ∈ leaders τ β i for i ∈ [4..k + 2].
The "γ" runs. Let τ f β be a time in the run β after which all the messages sent before τ β have been received. In a similar way to the one used to build the run β from the run α, it is possible to build a run γ from the run β in which, for each i ∈ [1..3] \ {ℓβ} there is ℓγ ∈ [1..3] \ {ℓβ} such that we eventually have forever ℓγ ∈ leaders i .

This construction can be repeated to obtain an infinite run in which at least k+1 process identities (namely, the identities 4, . . . , k+2, and at least two among the identities {1, 2, 3}) are infinitely often in the set variables leaders i which contradicts the strong eventual leadership property of Ω k while the outputs produced by ΠΣ x,1 at each process p i satisfy the specification of ΠΣ x,1 (in particular, the intersection property of ΠΣ x,1 are satisfied in all the runs that have been built).

✷ Lemma 3 Theorem 5. Let 1 < k < n -1. Ω k is not necessary for solving k-set agreement in AMP[∅].
Proof The theorem follows directly from Lemma 3 and the fact that k-set agreement can be solved in

AMP[ΠΣ k,1 ]. ✷ T heorem 5
Let X(k) denote the (still unknown) weakest failure detector such that k-set agreement can be solved in AMP[X(k)]. The following corollary shows that, when 1 < k < n -1, Ω k is neither necessary nor sufficient for solving the k-set agreement problem.

Corollary 1. Let 1 < k < n -1. Ω k ≃ AMP X(k).
Proof The proof is by contradiction. Let us first assume that

Ω k AMP X(k). It that case k-set agreement can be solved from Ω k . But it is impossible to solve k-set agreement in AMP[ Σ k , Ω k ] [3].
Let us now assume that X(k) AMP Ω k . Due to the definition of X(k), we have ΠΣ k,1 AMP X(k), hence ΠΣ k,1 AMP Ω k (by transitivity). But, for 1 < k < n -1, this is contradicted by Lemma 3 which has shown that ΠΣ k,1 AMP Ω k . It follows that Ω k and X(k) cannot be compared.

✷ Corollary 1

Conclusion

As indicated in the abstract, this paper is a new step in the quest for discovering the weakest failure detector for k-set agreement in asynchronous message-passing systems prone to any number of process failures. It has presented a new failure detector denoted ΠΣ x,y which enjoys many noteworthy features and an associated algorithm that solves k-set agreement for k ≥ xy. It has also shown that the weakest failure detector (that still remains to be discovered) and Ω k (a well-studied failure detector) cannot be compared. More generally, an important issue that remains to be solved lies in capturing the "weakest" type of shared memory that has to be emulated for solving k-set agreement in asynchronous message-passing systems.

A Proof of Lemma 2 Lemma 2 Let 1 ≤ y < n. ΠΣ y+1,1 AMP Ω y .

Proof Supposing that there exists an algorithm A y that builds Ω y in AMP[ΠΣ y+1,1 ] we show a contradiction, namely, there is an infinite run of A y in which it is impossible to provide a valid output for Ω y . Let R be the set of the infinite runs of A y such that :

• all the processes p i with i > y + 1 have initially crashed,

• the outputs of ΠΣ y+1,1 at each p i , i ≤ y + 1, are such that we always have qr i = {i} and leader i = i.

We show the following claim by induction on the number m of alive processes at time τ in a run of R.

Claim C(m). For each run r of R in which, at time τ , the only processes alive are p i , 1 ≤ i ≤ m, there is a run r ′ ∈ R, similar to r until τ , in which ∃τ ′ ≥ τ, ∃i 0 ∈ {1, . . . , m} : leaders τ ′ i0 ⊇ {1, . . . , m}.

Base case. Let r be a run of R in which p 1 is the only alive process at τ . The weak eventual leadership property of Ω y ensures that there is a time τ ′ after which leaders 1 ∋ 1, consequently, C(1) is verified.

Induction step. Assuming that C(m) is true for an m ≥ 1, we show that it entails C(m + 1). Let r ∈ R be a run in which, at τ , the only alive processes are p i , 1 ≤ i ≤ m + 1. Let r ′ be a run of R similar to r until τ in which p 1 crashes after τ . According to the induction hypothesis (applied on renamed processes), there is a run r ′ 1 of R similar to r ′ until τ in which there is i 1 ∈ {2, . . . , m + 1} and τ 1 ≥ τ such that leaders τ1 i1 ⊇ {2, . . . , m + 1}. Let now r 1 be a run of R, similar to r until τ , in which messages from p 1 are delayed until τ 1 . r ′ 1 and r 1 are indistinguishable for processes p i , i ∈ {2, . . . , m + 1}. Hence, in r 1 , we also have leaders τ1 i1 ⊇ {2, . . . , m + 1}. Repeating the same construction, we can now define a run r 2 similar to r 1 until τ 1 , in which there exist τ 2 ≥ τ 1 and i 2 ∈ {1, . . . , m+ 1} \ {2} such that leaders τ2 i2 ⊇ {1, . . . , m + 1} \ {2}. We iterate the process, by delaying the messages from each process, one after the other. Thus, we obtain an infinite run of R in which, for all processes p j , j ∈ {1, . . . , m + 1}, there is infinitely often a process p i that verifies leaders i ⊇ {1, . . . , m + 1} \ {j}. Consequently, if in this run no process ever verifies leaders ⊇ {1, . . . , m + 1}, then every process disappears infinitely often from a set leaders. That contradicts the weak eventual leadership property of Ω y which ends the induction step.

Contradiction. By induction, the claim C(m) is true for all m ∈ {1, . . . , y + 1}. But C(y + 1) entails that, there is a run of R in which a process verifies leaders ⊇ {1, . . . , y + 1}. That contradicts the validity property of Ω y and proves the lemma.

✷ Lemma 2

Another look at that proof could be the following : (1) ΠΣ y+1,1 provides no information on failures in the runs of R, (2) A y simulates Ω y in a wait-free manner among y + 1 processes in the runs of R. The contradiction then comes from the non-triviality of Ω y in a system of y + 1 processes.

B Implementation of Alpha x in AMP[Σ x ]

This appendix presents an implementation of an Alpha x object on top of AMP[Σ x ]. This implementation is obtained from a modification of the algorithm proposed in [START_REF] Bouzid | Anti-Ω k × Σ k )-Based k-Set Agreement Algorithms[END_REF] which is first described.

B.1 The Alpha x object used by Bouzid and Travers [START_REF] Bouzid | Anti-Ω k × Σ k )-Based k-Set Agreement Algorithms[END_REF] The obligation property used in [START_REF] Bouzid | Anti-Ω k × Σ k )-Based k-Set Agreement Algorithms[END_REF] The Alpha x object used in [START_REF] Bouzid | Anti-Ω k × Σ k )-Based k-Set Agreement Algorithms[END_REF] has the same specification as the one defined in Section 5.1 (which is close to the one defined in [START_REF] Guerraoui | The Alpha of Indulgent Consensus[END_REF][START_REF] Raynal | In Search of the Holy Grail: Looking for the Weakest Failure Detector for Wait-free Set Agreement[END_REF]) but for the obligation property which (similarly to [START_REF] Guerraoui | The Alpha of Indulgent Consensus[END_REF]) is defined as follows.

• Obligation. Let I = propose(r, -) be a terminating invocation. If every invocation I ′ = propose(r ′ , -) that starts before I returns is such that r ′ < r, then I returns a non-⊥ value.

It is easy to see that this specification is not Σ x -aware. In presence of concurrent invocations, it directs at most one process to decide a non-⊥ value, namely, the one with the highest round number. The current outputs of Σ x are irrelevant in this statement.

Principles: establish a priority on values Each process p i manages a local variable est i (initialized to ⊥) that represents its current estimate v of the value it will decide and a pair (lre i , pos i ) that defines the priority associated with v from p i 's point of view (the aim is to decide values with the highest priority); lre i = r means that r is the highest round seen by p i and pos i = ρ ∈ [1..2 r ] is the position of v in round r. The pairs r, ρ are used to establish a priority on proposed values. The function g(ρ, δ) = 2 δ (ρ -1) + 1 (where δ is a difference between two round numbers) is used to compute the priority of a value in the following rounds. More precisely, let (r, ρ) and (r ′ , ρ ′ ) (such that r ≤ r ′ ) be the pairs associated with the values v and v ′ , respectively. Value v has lower priority than value v ′ at round

r ′ iff g(ρ, r ′ -r) < ρ ′ or (g(ρ, r ′ -r) = ρ ′ ) ∧ (v < v ′ ).
Our description of Bouzid-Travers's algorithm (algorithm 3) is schematic. The reader will refer to [START_REF] Bouzid | Anti-Ω k × Σ k )-Based k-Set Agreement Algorithms[END_REF] for more detailed presentation and a proof. The implementation of the operation propose() is made up of two sequential phases: a read phase followed by write phase.

init lre i ← 0; est i ← ⊥; pos i ← 0. operation propose(r, v i ): (01) broadcast REQ_R(r); (02) repeat Q i ← qr i (03) until (∀j ∈ Q i : RSP_R(r, lre j , pos j , est j ) received from p j ) end repeat; (04) let rcv i = { lre j , pos j , est j : RSP_R(r, lre j , pos j , est j ) received }; (05) if (∃lre : lre, -, -∈ rcv i : lre > lre i ) then return(⊥) end if;

(06) pos i ← max{pos | r, pos, v ∈ rcv i }; est i ← max{v | r, pos i , v ∈ rcv i }; (07) if (est i = ⊥) then est i ← v i end if; (08) while(pos i < 2 r ) do (09)
pos i ← pos i + 1; pst i ← pos i ; % this line is executed atomically % [START_REF] Chaudhuri | More Choices Allow More Faults: Set Consensus Problems in Totally Asynchronous Systems[END_REF] broadcast REQ_W(r, pst i , est i ); [START_REF] Delporte-Gallet | Tight Failure Detection Bounds on Atomic Object Implementations[END_REF] repeat Q i ← qr i [START_REF] Delporte-Gallet | The Weakest Failure Detector for Message Passing Set-Agreement[END_REF] until (∀j ∈ Q i : RSP_W(r, pst i , lre j , pos j , est j ) received from p j ) end repeat; [START_REF] Gafni | The Weakest Failure Detector for Solving k-Set Agreement[END_REF] let rcv i = { lre j , pos j , est j : RSP_W(r, pst i , lre j , pos j , est j ) received}; [START_REF] Guerraoui | The Alpha of Indulgent Consensus[END_REF] if (∃lre : lre, -, -∈ rcv i : lre > r) then return(⊥) end if; [START_REF] Herlihy | The Topological Structure of Asynchronous Computability[END_REF] pos i ← max{pos | r, pos, v ∈ rcv i }; est i ← max{v | r, pos i , v ∈ rcv i } (16) end while; (17) return(est i ).

when REQ_R(rd) received from p j : [START_REF] Mostéfaoui | k-Set Agreement with Limited Accuracy Failure Detectors[END_REF] if rd > lre i then pos i ← g(pos i , rdlre i ); lre i ← rd end if; [START_REF] Mostéfaoui | Randomized Set Agreement[END_REF] send RSP_R(rd, lre i , pos i , est i ) to p j .

when REQ_W(rd, pos, est) received from p j : [START_REF] Mostéfaoui | Relations Linking Failure Detectors Associated with k-Set Agreement in Message-passing Systems[END_REF] if rd ≥ lre i then pos i ← g(pos i , rdlre i ); lre i ← rd [START_REF] Neiger | Failure Detectors and the Wait-free Hierarchy[END_REF] case pos j > pos i then est i ← est; pos i ← pos [START_REF] Raynal | Rump Session at 26th ACM Symposium on Principles of Distributed Computing (PODC'07)[END_REF] pos j = pos i then est i ← max{v i , est} [START_REF] Raynal | Set agreement. Encyclopedia of Algorithms[END_REF] pos j < pos i then nop [START_REF] Raynal | Failure Detectors for Asynchronous Distributed Systems: an Introduction[END_REF] end case (25) end if; [START_REF] Raynal | Fault-Tolerant Agreement in Synchronous Message-Passing Systems[END_REF] send RSP_W(rd, pos, lre i , pos i , est i ) to p j . Algorithm 3: Alpha k in AMP[Σ k ]: Bouzid-Travers's implementation [START_REF] Bouzid | Anti-Ω k × Σ k )-Based k-Set Agreement Algorithms[END_REF] Succinct description of the algorithm: the read phase When it invokes propose(r, v), a process p i first broadcasts a read-request message (line 01) to (a) obtain information on values proposed in previous rounds (if any) and (b) learn if other processes have started higher rounds.

When a process p j receives such a message REQ_R(rd) (where rd is a round number) it redefines its pair (lre j , pos j ) if rd > lre j (line 18) (the new position pos j of est j is re-computed according to the values of rd and lre j ). In all cases, p j sends back an answer to p i carrying its current value est j and the associated pair lre j , pos j (line [START_REF] Mostéfaoui | Randomized Set Agreement[END_REF].

Then, when it has received a response from each process in its current quorum qr i as supplied by Σ x (lines 02-03), p i returns ⊥ if it has received an answer indicating that another process has started a round higher than lre i (lines 04-05). Otherwise, lre i = r is the greatest round number known by p i . In that case, p i update pos i to the greatest position associated with round r it has seen and adopts the corresponding value v as its current estimate est i (line 06). Moreover, if v = ⊥, p i adopts v i into est i , namely, the value it proposes to the Alpha x object (line 07).

Succinct description of the algorithm: the write phase Process p i enters then a loop that it will exit either by returning ⊥ (line 14) or its current estimate value (line 17). The maximum number of times that this loop can be executed depends on the round number r and the current position value pos i (line 08). The part of the loop body defined by lines 10-15 is the same as lines 01-06. The difference is that, instead of obtaining information on the current state, p i cooperate with the processes of its current quorum qr i in order to try to increase the priority of its current est i . Hence instead of a read-request, p i broadcasts write-request messages.

Each time a process p j receives such a message that carries a triplet rd, pos, val it updates its current state in order this local state contains the value with the highest priority (and the associated control data). Operationally, if rd ≥ lre j , p j first updates pos j and lre j (line 20) exactly as it did at line 18 when it received a read-request message. Then, according to the value of pos j and pos (lines 21-24), p j updates est j and pos j if pos > pos j or updates only est j if pos j = pos. In all cases, p j sends back a response carrying its local state to the process that sent the write-request.

Collection des Publications Internes de l'Irisa c IRISA Proof It is easy to see that the lines that are new or modified do not add spurious values, hence the proof of the validity property is the same as the one given in [START_REF] Bouzid | Anti-Ω k × Σ k )-Based k-Set Agreement Algorithms[END_REF].

The same holds for the quasi-agreement property. This follows from the observation that, as the channels are asynchronous, the messages that are sent in Algorithm 3 and not sent in Algorithm 4 can be received too late in Algorithm 3, namely, after the processes have invoked the return() statement and decided. The quasi-agreement property follows from this observation and the proof given in [START_REF] Bouzid | Anti-Ω k × Σ k )-Based k-Set Agreement Algorithms[END_REF].

As far as the termination property is concerned, let us first observe that, due to line 09, a process will exit the while loop (lines 08-16) if it does not loop forever in the repeat loop of lines 11-12. Hence, the proof of the termination property consists in showing that no correct process loops forever in the repeat loop of lines 02-03 or the repeat loop of lines 11-12. Let us first consider the repeat loop of lines 02-03 and assume that a correct process p i loops forever. It follows from the liveness property of Σ x that there is a time τ after which qr i contains only correct processes. Hence, due to lines 02-03 and the fact that the number of processes is finite, it follows that there is a time τ ′ ≥ τ after which p i has sent a read-request message REQ_R(r) to each correct process that belongs to qr i (whatever the value of qr i ). As each correct process sends by return a matching response message RESP_R(r, -), it follows that p i eventually receives from each process in Q i a message RESP_R(r, -) matching its REQ_R(r) request, which completes the proof that the repeat loop of the read phase always terminates.

For the repeat loop of lines 11-12, let us first observe that the local variable pst i (which is initialized to the current value of pos i before entering the loop, line 09) is not modified during the execution of that repeat loop. Observing that p i repeatedly sends then a write-request message WRITE_W(r, pst i , -) and wait for matching response messages RESP_W(r, pst i , -), the same reasoning as previously applies from which we conclude that p i eventually exits the repeat loop of the write phase.

For the obligation property, let us remember the following definition: p ℓ being a correct process Q(ℓ, τ ) denotes the set {i ∈ C | ∀ τ i , τ ℓ ≥ τ : qr τi i ∩ qr τ ℓ ℓ = ∅}. We have to show that if, after some time τ , (a) only p ℓ and processes of Q(ℓ, τ ) invoke propose() and (b) p ℓ invokes propose() infinitely often, then at least one invocation issued by p ℓ returns a non-⊥ value.

Let Π(ℓ, τ ) = ∪ τ ′ ≥τ qr τ ′ ℓ and Π(ℓ, τ ) = ∪ τ ′ ≥τ,i∈Q(ℓ,τ ) qr τ ′ i . It follows from the definitions of the qr i sets and Q(ℓ, τ ) that Π(ℓ, τ ) ∩ Π(ℓ, τ ) = ∅.

Let τ 0 > τ be a time instant such that each invocation of the operation propose() issued before τ has returned or crashed and all the request and response messages generated by these invocations have been received and processed.

Let us observe that in Algorithm 4, a process sends requests and receives responses only to or from processes in its quorum. Consequently, after time τ 0 , (a) process p ℓ sends requests and receives responses only to or from processes in Π(ℓ, τ ); and (b) processes in Q(ℓ, τ ) sends requests and receives responses only to or from processes in Π(ℓ, τ ). Moreover, as Π(ℓ, τ ) ∩ ∪Π(ℓ, τ ) = ∅, for the processes in Π(ℓ, τ ) such a run R cannot be distinguished from a run R ′ in which the processes in Π(ℓ, τ ) have crashed by time τ 0 (Observation OB).

Since after τ 0 (a) p ℓ invokes infinitely often propose(), (b) the processes in Π(ℓ, τ ) do not invoke propose(), and (c) the invocations propose() issued by p ℓ are done with strictly increasing round numbers, it follows that one of these invocations I = propose() carries a round number greater than all those seen before τ by the processes in Π(ℓ, τ ).

Let us consider the run in which the processes whose identities belong to Π(ℓ, τ ) have crashed by τ 0 . When, in that run, p ℓ issues invocation I, the round-based obligation property used in [START_REF] Bouzid | Anti-Ω k × Σ k )-Based k-Set Agreement Algorithms[END_REF] is satisfied and p ℓ returns a non-⊥ value (Lemma 5 in [START_REF] Bouzid | Anti-Ω k × Σ k )-Based k-Set Agreement Algorithms[END_REF]). Due to Observation OB on the indistinguishability between R and R ′ for process p ℓ , it follows that p ℓ returns the same non-⊥ value in run R, which concludes the proof of the obligation property. Proof Validity and agreement properties. Let us first observe that, due to the test of line 02, the default value ⊥ cannot be decided. The fact that a decided value is a proposed value follows then from the validity of the underlying Alpha x object. Similarly, the fact that at most k non-⊥ values are decided follows directly from the quasi-agreement property of the underlying Alpha x object.

Termination property. It follows from the reliable broadcast operation that, at soon as a process decides (invokes return()) each correct process eventually delivers the same DECISION(d) message and decides (if not yet done). The proof is by contradiction: assuming that no process decides, we show that at least one correct process executes rel_broadcast() (and consequently, all correct processes decide).

Let p ℓ be a correct process that appears in the definition of the eventual partial leadership property of ΠΣ x . It follows from the definition of p ℓ that we eventually have forever leader ℓ = ℓ.

Let R ℓ be the set of the identities of the processes p j (with j = ℓ) such that we have leader j = j infinitely often. It follows from the contrapositive of the eventual partial leadership property of ΠΣ x that there is a time τ R ℓ such that ∀ j ∈ R ℓ , ∀ τ 1, τ 2 ≥ τ R ℓ : qr τ 1 j ∩ qr τ 2 ℓ = ∅, from which we conclude that R ℓ ⊆ Q(ℓ, τ R ℓ ) (this is the set defined in the obligation property of Alpha x ).

Let us notice that, due to test of line 03, there is a finite time τ a after which the only processes that invoke Alpha x .propose() are the processes in R ℓ ∪ {ℓ}. Moreover (as by the contradiction assumption no process decides) it follows that, after τ a , p ℓ invokes Alpha x .propose() infinitely often. Let τ b be a time greater than max(τ R ℓ , τ a ) from which we have R ℓ ⊆ Q(ℓ, τ R ℓ ) ⊆ Q(ℓ, τ b ).

As after τ b (a) only processes in R ℓ ∪ {ℓ} invoke Alpha x .propose(), (b) p ℓ invokes Alpha x .propose() infinitely often and (c) R ℓ ⊆ Q(ℓ, τ b ), we conclude from the obligation property of Alpha x that at least one invocation of p ℓ returns a value d = ⊥ and consequently executes rel_broadcast DECISION(d). This contradicts the fact that no process decides and concludes the proof of the theorem.

✷ T heorem 4

  [j].qr and a process index FD i [j].leader. Let FD[j] denote the corresponding distributed object. The failure detector ΠΣ x,y consists of an array FD[1..y] that satisfies the following properties:• Vector safety. ∀j ∈ [1..y]: FD[j].qr satisfies the liveness and intersection properties of ΠΣ x .• Vector liveness. ∃j ∈ [1..y]: FD[j] satisfies the eventual partial leadership property of ΠΣ x .

•

  Termination. Any invocation of propose() by a correct process terminates. • Validity. If propose(r, v) returns v ′ = ⊥, then propose(r ′ , v ′ ) has been invoked with r ′ ≤ r. • Quasi-agreement. At most k different non-⊥ values can be returned by propose() invocations. • Obligation. p ℓ being a correct process let Q(ℓ, τ ) = {i ∈ C | ∀ τ i , τ ℓ ≥ τ : qr τi i ∩ qr τ ℓ ℓ = ∅}. If, after time τ , (a) only p ℓ and processes of Q(ℓ, τ ) invoke propose() and (b) p ℓ invokes propose() infinitely often, then at least one invocation issued by p ℓ returns a non-⊥ value.

Algorithm 2 :

 2 x-Set agreement in AMP[ΠΣ x,1 ] (code for p i ) Theorem 4. Algorithm 2 solves the x-set agreement in AMP[ΠΣ x,1 ].

✷ T heorem 6 C Proof of Theorem 4 Theorem 4

 644 Algorithm 2 solves the x-set agreement problem in AMP[ΠΣ x,1 ].

In synchronous systems with more severe failures such as general omission failures, ⌊ t k ⌋ + 1 is still an upper bound on the number of rounds but k-set agreement can be solved if and only if t < k n k+1[START_REF] Raynal | Fault-Tolerant Agreement in Synchronous Message-Passing Systems[END_REF].Collection des Publications Internes de l'Irisa c IRISA

Collection des Publications Internes de l'Irisa c IRISA

Acknowledgments

The authors want to thank Martin Biely, Peter Robinson and Ulrich Schmid for interesting discussions on failure detectors suited to the k-set agreement problem in asynchronous message-passing systems.

As already indicated, a proof that this algorithm implements an Alpha x object that satisfies the round-based obligation property stated at the beginning of this section is given in [START_REF] Bouzid | Anti-Ω k × Σ k )-Based k-Set Agreement Algorithms[END_REF].

B.2 An implementation of Alpha x as defined in Section 5.1 Algorithm 4 describes an implementation of the Σ x -aware specification of Alpha x defined in Section 5.1. This algorithm is an appropriate improvement of Algorithm 3.

To make the presentation easier, the line numbers are the same in both algorithms. The lines that are new or modified are prefixed by the letter N. These modifications concern message filtering. This filtering is used to prevent a process p i from sending read or writerequests to the processes p j such that p i does not need information from p j to complete its current invocation of propose(). Hence, such a process p j cannot direct p i to return ⊥ while it could return a non-⊥ value (and additionally the values not sent by p i cannot force other processes to return ⊥).

Modification of the read phase A process p i records in r_req_set i the set of processes to which it has already sent a REQ_R(r) message (lines N01 and N02-2) and sends read-request messages REQ_R(r) only to the processes p j that belong to its quorum qr i (line N02-1).

Then, when it stops waiting for response messages, it considers only the responses sent by the processes of its last quorum plus its own response (line N04).

Modification of the write phase

The message exchange pattern of that phase is modified similarly to what has been done for the read phase (lines N10, N12-1, N12-2 and N13).

until (∀j ∈ Q i : RSP_R(r, lre j , pos j , val j ) received from p j ) end repeat; (N04) let rcv i = { lre j , pos j , est j : RSP_R(r, lre j , pos j , est j ) received from Q i }; (05) if (∃lre : lre, -, -∈ rcv i : lre > lre i ) then return(⊥) end if; (06)

while (pos i < 2 r ) do (09) pos i ← pos i + 1; pst i ← pos i ; % this line is executed atomically % (N10)

until (∀j ∈ Q i : RSP_W(r, pst i , lre j , pos j , val j ) received from p j ) end repeat; (N13) rcv i ← { lre j , pos j , est j : RSP_W(r, pst i , lre j , pos j , est j ) received from Q i }; [START_REF] Guerraoui | The Alpha of Indulgent Consensus[END_REF] if (∃lre : lre, -, -∈ rcv i : lre > r) then return(⊥) end if; (15)

end while; [START_REF] Lynch | Distributed Algorithms[END_REF] return(est i ).

when REQ_R(rd) received from p j :