A Mostéfaoui

S Rajsbaum
email: rajsbaum@math.unam.mx

M Raynal
email: raynal@irisa.fr

C Travers
email: ctravers@irisa.fr

The Combined Power of Conditions and Information on Failures to Solve Asynchronous Set Agreement

Keywords: Asynchronous System, Condition, Consensus, Failure Detection, Input Vector, Legal condition, Set Agreement, Process Crash, Shared Memory, Snapshot Systèmes répartis asynchrones, Condition, Problèmes d'accord, Crash de processus, Oracle oméga, Détecteur de fautes

To cope with the impossibility of solving agreement problems in asynchronous systems made up of n processes and prone to t process crashes, system designers tailor their algorithms to run fast in "normal" circumstances. Two orthogonal notions of "normality" have been studied in the past through failure detectors that give processes information about process crashes, and through conditions that restrict the inputs to an agreement problem. This paper investigates how the two approaches can benefit from each other to solve the k-set agreement problem, where processes must agree on at most k of their input values (when k = 1 we have the famous consensus problem). It proposes novel failure detectors for solving k-set agreement, and a protocol that combines them with conditions, establishing a new bridge among asynchronous, synchronous and partially synchronous systems with respect to agreement problems. The paper proves also a lower bound when solving the k-set agreement problem with a condition.

.

THE COMBINED POWER OF CONDITIONS AND INFORMATION ON FAILURES TO SOLVE ASYNCHRONOUS SET AGREEMENT

A. MOSTÉFAOUI S. RAJSBAUM M. RAYNAL C. TRAVERS

Introduction

Distributed services have to run efficiently and reliably in complex environments with unpredictable processing and communication delays, where components can fail in various ways. It is unavoidable to encounter scenarios where the system performance will degrade, or even manual intervention will be required. Therefore, system designers tailor their applications to run fast in "normal" circumstances while having expensive recovery procedures in the rare cases of "abnormal" circumstances. Two complementary notions of "normality" have been considered, mirroring the traditional computer science duality of control and data. On the control side we have the failure detector approach [START_REF] Chandra | Unreliable Failure Detectors for Reliable Distributed Systems[END_REF], that abstracts away useful failure pattern information, available in common operating scenarios. On the data side, we have the condition-based approach [START_REF] Mostefaoui | Conditions on Input Vectors for Consensus Solvability in Asynchronous Distributed Systems[END_REF], that looks at common input data patterns of a certain distributed problem we are interested in. The aim of this paper is to study how the two approaches interact, and can benefit from each other, with respect to solving agreement problems.

Context of the Paper

Distributed services often rely on an underlying agreement protocol. The most popular and fundamental of the agreement problems is consensus, which is actually indispensable for a lot of services. This paper investigates the possibilities and limitations of solving consensus, and other weaker agreement problems, in a system with failure detectors and conditions.

Agreement problems

The consensus problem can informally be stated as follows. Each process proposes a value and the processes that are not faulty have to decide the same value, such that the value decided is one of the proposed values. As a familiar example, it is easy to see that the atomic broadcast problem relies on consensus as it requires that all the processes deliver the messages they broadcast in the same order: they have consequently to agree in one way or another on the same message delivery order. However, it is well-known that the consensus problem has no solution in message passing asynchronous systems made up of n processes that need to tolerate a single process crash failure [START_REF] Fischer | Impossibility of Distributed Consensus with One Faulty Process[END_REF].

The k-set agreement problem [START_REF] Chaudhuri | More Choices Allow More Faults: Set Consensus Problems in Totally Asynchronous Systems[END_REF] relaxes the consensus requirement to allow up to k different values, out of the proposed values, to be decided; when k = 1 we have the consensus problem. Set agreement is an abstraction of problems that are weaker than consensus. Its discovery was motivated by the search for a problem that is solvable when k -1 processes can crash, but not when k can crash, in an asynchronous system. Since then, it has been very valuable in the development of the foundations of distributed computing. The proofs in [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] showing that k-set agreement is not solvable in a system of k + 1 processes where k can crash uncovered a deep connection between distributed computing and topology, and motivated a significant amount of subsequent research.

The situation is totally different in synchronous systems, where both consensus and k-set agreement can be solved for any value of t (the maximum number of process crashes) [START_REF] Chaudhuri | Tight Bounds for k-Set Agreement[END_REF][START_REF] Raynal | Consensus in Synchronous Systems: a Concise Guided Tour[END_REF]. However, there are limitations on how fast these problems can be solved in a synchronous system, as a function of the number of failures t to be tolerated. It has been shown that consensus requires t + 1 rounds in the worst case [START_REF] Fischer | A Lower Bound for the Time to Assure Interactive Consistency[END_REF][START_REF] Lamport | Byzantine Generals and Transaction Commit Protocols[END_REF], and there are protocols that meet this lower bound. These results have been generalized for the set agreement problem in [START_REF] Chaudhuri | Tight Bounds for k-Set Agreement[END_REF][START_REF] Gafni | From a Static Impossibility to an Adaptive Lower Bound: The Complexity of Early Deciding Set Agreement[END_REF][START_REF] Parvédy | Strongly-terminating Early-Stopping k-set Agreement in Synchronous Systems with General Omission Failures[END_REF].

The following two complementary notions of "normality" have been considered 1 to cope with the consensus and set agreement asynchronous impossibility results and synchronous lower bounds.

Control: Enriching the underlying system

The first approach focuses on the behavior of the underlying system. In this case "normal circumstance" means a period during which the system behaves in a relatively synchronous way. Namely, periods during which upper bounds on process execution speeds and on message transmission delays hold (various such partially synchronous models have been considered, e.g., [START_REF] Dwork | Consensus in the Presence of Partial Synchrony[END_REF]), or periods during which message exchange patterns satisfy some properties (e.g., the notion of winning/losing responses introduced in [START_REF] Mostefaoui | Asynchronous Implementation of Failure Detectors[END_REF]) that allow solving consensus. A failure detector abstracts away such low-level assumptions by providing processes with a primitive they can invoke, that returns information on process failures. One of the noteworthy features of failure detectors is the modular approach they favor: one can independently, on one side, solve a problem with the help of a particular class of failure detector, and, on another side, implement the assumed failure detector with the help of the underlying timing or order assumptions. The design, transportability and proof of protocols then become modular and easier to achieve.

Chandra and Toueg introduced the failure detector notion [START_REF] Chandra | Unreliable Failure Detectors for Reliable Distributed Systems[END_REF] and defined eight classes that can be used to solve asynchronous consensus. Together with Hadzilacos, they later showed that one of these classes is the weakest class of failure detectors to solve consensus when t < n/2 [START_REF] Chandra | The Weakest Failure Detector for Solving Consensus[END_REF] (n being the total number of processes, and t an upper bound on the number of faulty processes). The weakest failure detector for consensus and any value of t was identified in [START_REF] Delporte-Gallet | The Weakest Failure Detectors to Solve Certain Fundamental Problems in Distributed Computing[END_REF]. These results are of great theoretical interest because they identify the minimum knowledge about failures that needs to be abstracted to solve consensus. Failure detectors to solve set agreement have also been proposed [START_REF] Herlihy | Tight Bounds for k-Set Agreement with Limited Scope Accuracy Failure Detectors[END_REF][START_REF] Mostefaoui | k-Set Agreement with Limited Accuracy Failure Detectors[END_REF][START_REF] Yang | Structured Derivations of Consensus Algorithms for Failure Detectors[END_REF] but we do not know yet what is the minimum knowledge about failures that needs to be abstracted to solve this problem.

The failure detector approach has favored the design of indulgent protocols [START_REF] Guerraoui | Indulgent Algorithms[END_REF]. A protocol is indulgent with respect to its failure detector if it never violates its safety property. This means that when the underlying failure detector satisfies its specification (normal circumstances), the protocol terminates correctly; and, when the underlying failure detector does not satisfy its specification (abnormal circumstances), it is possible that the protocol does not terminate, but if it terminates, it does so correctly. Various indulgent failure detector-based consensus protocols have been proposed (e.g., [START_REF] Chandra | Unreliable Failure Detectors for Reliable Distributed Systems[END_REF][START_REF] Guerraoui | The Information Structure of Indulgent Consensus[END_REF][START_REF] Hurfin | A Versatile Family of Consensus Protocols Based on Chandra and Toueg's Unreliable Failure Detectors[END_REF][START_REF] Mostéfaoui | Solving Consensus Using Chandra and Toueg's Unreliable Failure Detectors: a General Quorum-Based Approach[END_REF][START_REF] Mostefaoui | Leader-Based Consensus[END_REF][START_REF] Schiper | Early Consensus in an Asynchronous System with a Weak Failure Detector[END_REF]).

Data: Restricting the inputs

The condition-based approach [START_REF] Mostefaoui | Conditions on Input Vectors for Consensus Solvability in Asynchronous Distributed Systems[END_REF] consists in looking at certain combinations of input values of a given distributed problem. It is often the case in practice that some combinations of input values of processes occur more frequently than others. For example, in an election, it is often the case that the difference in the number of votes that candidates receive is significant. More precisely, an input vector contains the values proposed by the processes in an execution. A condition C is a set of input vectors, each representing a common combination of inputs to the problem. If a protocol solves k-set agreement for C, then whenever the input vector belongs to C, all the correct processes decide. The solution should be indulgent in the sense that if correct processes decide while the input vector does not belong to the condition, they do not decide more than k values.

It was discovered in [START_REF] Mostefaoui | Conditions on Input Vectors for Consensus Solvability in Asynchronous Distributed Systems[END_REF] that there is a family of conditions, called x-legal, that tie together asynchronous and synchronous systems with respect to consensus solvability. Informally, in an x-legal condition any two input vectors I1, I2 that force different decisions have d(I1, I2) > x (Hamming distance); assuming n > x. Thus, in a sense, x is the "power" of the condition; larger values of x make it easier to solve consensus. Assuming up to t process crashes, and d ≤ t (d can have a negative value), let S

[d]

t be the set of all x-legal conditions, x = td (e.g., S

[0] t consists of the t-legal conditions). Then

S [-t] t ⊂ • • • ⊂ S [-1] t ⊂ S [0] t ⊂ S [1] t ⊂ • • • ⊂ S [t] t ,
where S

[t]

t includes the condition made up of all the possible input vectors. For a condition C ∈ S

[d]

t , -t ≤ d ≤ t and a system prone to t process crashes, we have:

• For values of d ≤ 0, for inputs in C consensus is solvable by more and more efficient protocols in a shared memory asynchronous system as we go from d = 0 to d = -t [START_REF] Mostefaoui | Condition-based Consensus Solvability: a Hierarchy of Conditions and Efficient Protocols[END_REF].

• For values of d > 0, consensus is not solvable in an asynchronous system, but, for inputs in C, it is solvable in a message passing synchronous system with more and more rounds, as we go from d = 1 (two rounds) to d = t (t + 1 rounds), and this is tight [START_REF] Mostefaoui | Synchronous Condition-Based Consensus[END_REF] (namely, when C ∈ S , (d + 1) rounds are sufficient, and necessary in worst case scenarios).

• d = 0 is the borderline case. On one hand, asynchronous consensus can be solved (despite up to t faulty processes) for a condition C if, and only if, C is t-legal [START_REF] Mostefaoui | Conditions on Input Vectors for Consensus Solvability in Asynchronous Distributed Systems[END_REF]. On the other hand, consensus can be solved optimally (2 rounds) in a message passing synchronous system [START_REF] Mostefaoui | Synchronous Condition-Based Consensus[END_REF] for any t-legal condition.

The condition-based approach has been considered also for set agreement (and for other problems), but a characterization of the conditions that allow solving set agreement was not known (see Section 1.3 for more about this and other related works).

Irisa

Motivation and Results

As we have seen, failure detectors and conditions are two orthogonal approaches to cope with the impossibility of solving agreement problems in asynchronous systems prone to t process crashes. So, the natural question that comes to mind is: What is the relation between the condition-based approach and the failure detection-based approach when solving asynchronous agreement problems?

More specifically, we are interested in studying how the two approaches can cooperate to solve set agreement problems. We would like to understand which combinations of failure detectors and conditions can be used to solve k-set agreement for a given value of k.

For a given condition C, what is a failure detector that abstracts away the synchrony needed to solve k-set agreement?

These and similar questions are the topic addressed in the paper.

The paper contains three main contributions. While trying to answer the previous questions, we discovered a new class of failure detectors. We present an asynchronous condition-based set agreement protocol based on this kind of failure detectors. We present a lower bound showing that our protocol is optimal. The next three sections describe these results in more detail.

A new class of failure detectors

The first contribution of the paper is the definition of a new class of failure detectors that we denote φ y t , 0 ≤ y ≤ t. A failure detector of φ y t provides a primitive, denoted QUERY y (S), that can be invoked by a process with a set of process ids S to be informed whether they have crashed or not. Roughly speaking, QUERY y (S) returns true only when all the processes in S have crashed. If at least one process in S is alive the output should be false. If |S| is outside the range ty < |S| ≤ t, the query returns no useful information.

Notice that the nature of our failure detectors is different from the standard failure detectors of [START_REF] Chandra | Unreliable Failure Detectors for Reliable Distributed Systems[END_REF], that return a set of processes suspected to have crashed, and accept no input parameter. The motivation is that often a process p i is interested in the failures of only a specific part of the network, namely S, while the standard failure detectors must find out the failure status of all processes in the network, even if p i cares only about the state of a single process p j .

For each value of y between 0 and t, there is a class of failure detectors, φ y t . The class φ y t provides more information on failures than the class φ y-1 t . So, the class φ t t is the most powerful, while φ 0 t is the weakest (it actually provides no dependable information on failures). Indeed, as shown in the paper, φ y t can be used to solve k-set agreement for smaller values of k than φ y-1 t . The paper also compares the power of the φ y t failure detectors and of the classic failure detector classes introduced by Chandra and Toueg [START_REF] Chandra | Unreliable Failure Detectors for Reliable Distributed Systems[END_REF]. It is shown that it is possible to build any class φ y t , 0 ≤ y ≤ t, from a perfect failure detector as defined in [START_REF] Chandra | Unreliable Failure Detectors for Reliable Distributed Systems[END_REF]. (A perfect failure detector eventually detects all crashed processes, and never suspects erroneously a non-crashed process.) In contrast, none of the other classes of classic failure detectors can be used to build a failure detector of a class φ y t , 1 ≤ y ≤ t. When we consider the construction in the other direction, we show that no class φ y t , 0 ≤ y < t, can be used to build any of the classic failure detector classes. When y = t, φ t t can be used to build a failure detector of the class P.

A condition-based set agreement algorithm using failure detectors

A second contribution of the paper is the design of a condition-based set agreement protocol with access to a failure detector of the class φ y t , 0 ≤ y ≤ t. The considered model is the classical asynchronous read/write shared memory distributed system prone to at most t process crashes. The protocol can be instantiated with any condition C ∈ S

[d]

t , 0 ≤ d ≤ t. As we have seen, x = td represents the power of the condition. That is, once n and t are fixed, the protocol is parameterized by the power of the failure detector (captured by y), and the power of the condition (captured by x = td).

We use the following terminology. We say that "a protocol solves k-set agreement problem" if the correct processes always decide; and we say that "a protocol solves the condition-based k-set agreement" problem" if the correct PI n ˚1897 processes decide at least "in normal circumstances", where "normal circumstances" means when (1) the input vector belongs to the condition C, or when (2) a process decides, or less than k processes crash, or when (3) at least td processes crash initially.

The proposed protocol solves condition-based k-set agreement for k = 1 + max(0, dy). Making more explicit the power y of the failure detector, and the power x = td of the condition, we have k = 1 + max(0, t -(x + y)). This shows how, by adding the power of the condition, and the power of the failure detector, we can counterbalance the power t of the "adversary", in order to reduce the value of k. When we consider the boundary values of y and d, the protocol solves the following problems:

• d = t corresponds to the case where there is no additional power provided by the condition, as then the condition C may contain all possible input vectors. But, as any input vector belongs to this trivial condition, all correct processes always decide, and consequently the protocol solves the k-set agreement problem. More precisely:

-If y = t (strongest failure detector), the protocol solves the consensus problem, k = 1.

-If y = 0 (no failure detector), the protocol solves the trivial (t + 1)-set agreement problem.

-If 0 < y < t, protocol solves k-set agreement with k = t + 1y. When we compare to the previous case, this shows the benefit provided by a failure detector of the class φ y t . The number of decided values linearly decreases according to the power of the failure detector, as measured by y.

• d = 0 means that the condition C is t-legal, which means that condition-based consensus can be solved despite asynchrony and up to t crashes, with no failure detector. So, at most one value is decided, and all the correct processes terminate in normal circumstances. So, the protocol then solves condition-based consensus. (Let us notice that this is independent of the value of y.) • y = 0 (no failure detector), the protocol then relies only on the condition and solves the condition-based kset agreement problem for k = d + 1. No more than (d + 1) values are decided, and the termination of the correct processes is guaranteed at least in normal circumstances: the number of decided values decreases linearly according to the parameter d defining the condition.

This case is particularly interesting as it exhibits a new link relating synchronous and asynchronous systems. More precisely, when the condition C belongs to S

[d]

t , and the input vector belongs to C, (1) it is possible to solve consensus in at most (d + 1) rounds in a synchronous system [START_REF] Mostefaoui | Synchronous Condition-Based Consensus[END_REF]; and (2) it is possible to solve (d + 1)-set agreement in an asynchronous system, both systems being prone to t crashes. The optimal time bound for synchronous condition-based consensus is equal to the number of decided values in asynchronous condition-based set agreement. This time (in synchronous systems) vs number of decided values (in asynchronous systems) relation sheds a new light on the global picture concerning the relations between synchronous and asynchronous systems.

When we look at the general case, where the condition-based k-set agreement problem is solved with k = 1 + max(0, dy), we see that when y ≥ d, condition-based consensus is solved. This means that, if d is fixed, we only need to take a failure detector of the class φ d t to solve condition-based consensus (failure detectors of any class φ y t with y > d are stronger than necessary). A similar reasoning can be done when y is fixed, and we have the choice of the condition class.

The proposed protocol is indulgent [START_REF] Guerraoui | Indulgent Algorithms[END_REF][START_REF] Guerraoui | The Information Structure of Indulgent Consensus[END_REF]: it never violates its safety requirement (no more than k = 1 + max(0, dy) values are decided), and the correct processes always terminate when the input vector belongs to the condition ("normal circumstances"). Interestingly, a simple modification provides a protocol version in which all the correct processes always terminate. This is obtained at the price of an increase in the number of values that can be decided when the input vector does not belong to the (td)-legal condition C, namely up to k = t + 1y different values can then be decided. When the system is equipped with a failure detector of the class φ t t , this protocol variant solves the consensus problem whatever the condition it is instantiated with.

A lower bound

A third contribution of the paper is a lower bound result showing that no protocol with access to a failure detector of the class φ y t can solve k-set condition-based agreement for k ≤ max(0, dy), if the condition is in S

[d]

t . The proof is by reduction to the standard t-resilient k-set agreement problem, that is known to be impossible if t ≥ k [START_REF] Borowsky | Generalized FLP Impossibility Results for t-Resilient Asynchronous Computations[END_REF][START_REF] Herlihy | Algebraic Spans[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]. This lower bound result has two nice corollaries. One states that (in the absence of a failure detector) Irisa there is no condition-based k-set agreement protocol such that k ≤ d for any (td)-legal condition (a previously open problem). The second one states that among all the failure detector classes of the family (φ y t ) 0≤y≤t , the class φ y t is the weakest that allows solving the k-set agreement problem for k > ty.

Related Work

The condition-based approach for consensus and set agreement The condition-based approach has been applied to problems other than consensus, like interactive consistency [START_REF] Friedman | Distributed Agreement Problems and their Connection with Errorcorrecting Codes[END_REF], and more related to our work, set agreement [START_REF] Attiya | Wait-Free n-Set Consensus when Inputs are Restricted[END_REF][START_REF] Mostefaoui | Condition-Based Protocols for Set Agreement Problems[END_REF].

The paper [START_REF] Attiya | Wait-Free n-Set Consensus when Inputs are Restricted[END_REF] characterizes the set of input vectors that allow to solve (n -1)-set agreement, wait-free, namely, when t = n -1. Their notion of solvability is different from ours, since they assume a protocol never receives input vectors outside of the condition. In [START_REF] Mostefaoui | Condition-Based Protocols for Set Agreement Problems[END_REF] another family of conditions for set agreement is defined, but no general lower bounds were proved. Randomization as a means of circumventing the set agreement asynchronous impossibility result has been considered in [START_REF] Mostefaoui | Randomized k-Set Agreement[END_REF].

Failure detectors Most of the research about failure detectors has been directed at solving consensus, but there have also been proposals of failure detectors for solving other problems. Failure detectors for implementing various objects and for solving non-blocking atomic commit have been studied (e.g., [START_REF] Delporte-Gallet | The Weakest Failure Detectors to Solve Certain Fundamental Problems in Distributed Computing[END_REF][START_REF] Guerraoui | Non-Blocking Atomic Commit in Asynchronous Systems with Failure Detectors[END_REF][START_REF] Neiger | Failure Detectors and the Wait-Free Hierarchy[END_REF]). The weakest class of failure detectors to solve consensus was identified in [START_REF] Chandra | The Weakest Failure Detector for Solving Consensus[END_REF][START_REF] Delporte-Gallet | The Weakest Failure Detectors to Solve Certain Fundamental Problems in Distributed Computing[END_REF]. For our work, weaker classes of failure detectors are especially relevant, since set agreement is an easier problem than consensus (and if conditions are considered, it becomes even easier). Weaker classes of failure detectors were considered in [START_REF] Friedman | The Notion of Veto Number for Distributed Agreement Problems[END_REF][START_REF] Mostefaoui | k-Set Agreement with Limited Accuracy Failure Detectors[END_REF][START_REF] Neiger | Failure Detectors and the Wait-Free Hierarchy[END_REF][START_REF] Yang | Structured Derivations of Consensus Algorithms for Failure Detectors[END_REF].

Failure detectors for set agreement Among the failure detectors which are not strong enough to solve consensus, the limited scope accuracy failure detectors [START_REF] Guerraoui | Gamma-accurate Failure Detectors[END_REF][START_REF] Mostefaoui | k-Set Agreement with Limited Accuracy Failure Detectors[END_REF][START_REF] Yang | Structured Derivations of Consensus Algorithms for Failure Detectors[END_REF] have been studied with respect to set agreement. To illustrate this notion, let us consider the class denoted S x . A failure detector of that class satisfies the following two properties.

The completeness property states that the processes that crash are eventually suspected in a permanent way. The limited scope accuracy property states that there is a correct process that is not suspected by a set -cluster-of x processes (some of these x processes may be correct, while others may be faulty). An S x -based k-set agreement protocol is presented in [START_REF] Mostefaoui | k-Set Agreement with Limited Accuracy Failure Detectors[END_REF]. This protocol assumes t < k + x -1 (which means that (t + 1) -(x -1) is the smallest value of k that it can tolerate). Using topological methods, it has been shown in [START_REF] Herlihy | Tight Bounds for k-Set Agreement with Limited Scope Accuracy Failure Detectors[END_REF] that this is actually a lower bound for any S x -based k-set agreement protocol (from which it follows that the previous protocol is optimal with respect to the number of faulty processes that can be tolerated). When the limited scope accuracy property has to hold only after some unknown but finite time, we get the class denoted 3S x . It is shown in [START_REF] Herlihy | Tight Bounds for k-Set Agreement with Limited Scope Accuracy Failure Detectors[END_REF] that any 3S x -based k-set agreement protocol requires t < min(n/2, k + x -1). A 3S x -based protocol meeting this lower bound is also presented in [START_REF] Herlihy | Tight Bounds for k-Set Agreement with Limited Scope Accuracy Failure Detectors[END_REF].

It is shown in [START_REF] Anceaume | Necessary and Sufficient Conditions for Transforming Limited Accuracy Failure Detectors[END_REF] that t < x is a necessary and sufficient requirement to transform any failure detector of the class 3S x into a failure detector of the class 3S y for y > x.

The Class of Anonymously Perfect Failure Detectors A failure detector of our class φ y t returns a binary output and can be invoked with a parameter S, that contains a set of process ids. In contrast, the classic failure detectors of [START_REF] Chandra | Unreliable Failure Detectors for Reliable Distributed Systems[END_REF] return a set of ids, and are invoked with no parameter. A failure detector class whose output is binary has been introduced by Guerraoui to solve the non-blocking atomic commit problem [START_REF] Guerraoui | Non-Blocking Atomic Commit in Asynchronous Systems with Failure Detectors[END_REF], but differently from ours, a failure detector of this class does not accept a parameter to invoke it. This class, called anonymously perfect failure detectors and denoted ?P, is defined as follows. Each process has a flag (initially equal to false) that is eventually set to true if and only if a process has crashed (the identity of the crashed process is not necessarily known, hence the name "anonymous").

The definition of ?P has been extended in [START_REF] Friedman | The Notion of Veto Number for Distributed Agreement Problems[END_REF] to take into account the fact that processes have crashed (instead of a single one). This class, denoted ?P , provides each process with a flag that is eventually set to true if and only if at least processes have crashed (observe that ?P is ?P 1 ).

So, a failure detector of the class ?P answers true only if there is a set S of processes that have crashed. The set S is not known to the processes. Differently, when we consider φ y t , the set S is user-defined and specific to each invocation.

A variant of Ω A generalization of the class of leader failure detectors denoted Ω has been introduced in [START_REF] Neiger | Failure Detectors and the Wait-Free Hierarchy[END_REF]. More explicitly, Ω z is the class of all failure detectors that provide the processes with a primitive LEADER() satisfying the PI n ˚1897 following properties. First, LEADER() always returns a set of at most z process identities. Second, there is a time τ such that, after τ , all the invocations of LEADER() by the correct processes return the same set of processes and this set includes at least one correct process. It is easy to see that Ω 1 is Ω, and Ω n provides no information on failures. That is, in general, Ω z is weaker than the weakest failure detector for consensus. However, Neiger introduced them to study questions about augmenting the synchronization power of types in the wait-free hierarchy [START_REF] Herlihy | Wait-Free Synchronization[END_REF], and their relation to set agreement was not studied.

In a follow up paper [START_REF] Mostefaoui | On the Computability Power and the Robustness of Set Agreementoriented Failure Detector Classes[END_REF], we study the relation of Ω z to set agreement. Moreover, we study our new failure detectors, with respect to 3S x , Ω z , and show which reductions among these classes are possible and which are not.

Organization of the Paper

The paper is made up of 9 sections. After this introduction, and a short section introducing the computation model considered in the paper, Section 3 presents the new failure detector classes φ y t . (Section 8 compares them to classic failure detectors by Chandra and Toueg.) Section 4 provides a quick overview of the most relevant notions (for this paper) of the condition-based approach, including a definition of the condition-based k-set agreement problem. Section 5 presents a generic k-set agreement protocol that is based on the combined power of a failure detector of the class φ y t and a condition of the class S

[d]

t . The protocol is discussed in Section 6 where, at the price of an increase of the number of decided values, an always terminating version is presented. Section 7 focuses on the lower bound result. Finally, Section 9 summarizes the content of the paper.

About the Model of Computation

This paper considers the usual asynchronous model with n processes p 1 , . . . , p n , where at most t can crash, 1 ≤ t < n. The processes communicate through a shared memory made up of single-writer, multi-readers atomic registers.

We assume processes have access to an oracle that provides possibly unreliable information on process failures. A failure detector provides processes with a primitive they can invoke to get information from the oracle on process failures.

3 The Failure Detector Classes {φ y t } 0≤y≤t

Definition

This section introduces a new class of failure detectors, parameterized by an integer y, 0 ≤ y ≤ t, denoted φ y t . (A comparison to classic failure detectors is done in Section 8.) The power of a such a failure detector depends on the value of y. As we are about to see, a failure detector is more powerful for larger values of y, because it can return information about more specific regions of the network, namely, about smaller sets S of processes with |S| > ty.

More precisely, a failure detector of the class φ y t provides a primitive QUERY y (S) that returns a boolean answer. A process invokes it with the parameter S, a set of processes specific to each invocation. Intuitively, if p i invokes QUERY y (S) the answer will be true only when all processes in S have crashed. In that sense, these failure detectors are different from the standard failure detectors introduced by Chandra and Toueg [START_REF] Chandra | Unreliable Failure Detectors for Reliable Distributed Systems[END_REF], that return a set of processes suspected to have crashed, and do not accept an input parameter2 . The motivation is that often a process p i is interested in the failures of only a specific sector of the network, namely S, while the Chandra-Toueg failure detectors must find out the failure state of all processes in the network, even if p i cares only about the state of only one process p j .

A query QUERY y (S) such that ty < |S| ≤ t is relevant, otherwise it is irrelevant. Intuitively, "relevant" means that it provides dependable information on failures. The class φ y t is defined by the following properties: • Triviality property. If |S| ≤ ty, then QUERY y (S) returns true. If |S| > t, then QUERY y (S) returns false.

• Safety property. If QUERY y (S) is relevant, then if at least one process in S has not crashed when QUERY y (S) is invoked, the invocation returns false.

• Liveness property. Let QUERY y (S) be a relevant query. Let τ be a time such that, at time τ , all the processes in S have crashed. There is a time τ ≥ τ such that all the invocations of QUERY y (S) after τ return true.

The triviality property says that the invoking process gets back a true output when the set S is too small, because in this case the failure detector is not powerful enough to answer reliably on a region of the network that is too focused. If the set S is too big, the output is false, because by definition, no more than t processes can fail. The safety property states that if the output of a relevant query is true, then all the processes in S have crashed. The liveness property states that QUERY y (S) eventually outputs true when all the processes in S have crashed (and the query is relevant). We shall see that φ y1 t is stronger than φ y2 t if y1 > y2, since φ y1 t provides more information about failures than φ y2 t . Given a run of the processes, let QUERY y (S) be a failure detector query invocation that from some time on is indefinitely repeated. Let us examine the outputs returned by the infinite sequence of queries when the failure detector belongs to φ y1 t and φ y2 t , respectively. Notice that t -y2 > t -y1 (since y1 > y2).

Ranking the

• Case 1: |S| > t. Both outputs are systematically equal to false.

• Case 2: |S| ≤ t -y1. Both outputs are systematically equal to true.

• Case 3: t -y2 < |S| ≤ t (so, we also have t -y1 < |S| ≤ t), for a relevant query. If at least one process of S never crashes, both outputs are always equal to false. If all the processes of S crash, eventually both outputs are permanently equal to true.

• Case 4: t -y1 < |S| ≤ t -y2. In this case, the output is always true if the failure detector belongs to the class Φ y2 t . If it belongs to Φ y1 t , the output is as in Case 3 (it depends on the failures).

The last case, namely, when t -y1 < |S| ≤ t -y2, exhibits a noteworthy difference between φ y1 t and φ y2 t : φ y1 t provides information on failures while φ y2 t does not. Indeed, for y1 > y2, it is impossible to build a failure detector in φ y1 t from one in φ y2 t . On the other hand, any failure detector in φ y1 t can be used to build a failure detector in φ y2 t , by returning true if |S| ≤ t -y2; returning false if |S| > t; and returning the output of φ y1 t if t -y2 < |S| ≤ t. (Formally, the next theorem is a consequence of Corollary 2 of Section 7.)

Theorem 1 (y1 > y2) ⇒ (φ y2 t < φ y1 t ).

The Condition-Based Approach

The condition-based approach was introduced in [START_REF] Mostefaoui | Conditions on Input Vectors for Consensus Solvability in Asynchronous Distributed Systems[END_REF] to study conditions restricting the inputs to consensus that make the problem solvable in an asynchronous system where t processes can crash. This line of research has been extended to study conditions for other problems, and in other distributed computing models [START_REF] Attiya | Wait-Free n-Set Consensus when Inputs are Restricted[END_REF][START_REF] Friedman | Distributed Agreement Problems and their Connection with Errorcorrecting Codes[END_REF][START_REF] Izumi | Condition Adaptation in Synchronous Consensus[END_REF][START_REF] Mostefaoui | Conditions on Input Vectors for Consensus Solvability in Asynchronous Distributed Systems[END_REF][START_REF] Mostefaoui | Synchronous Condition-Based Consensus[END_REF][START_REF] Mostefaoui | Condition-Based Protocols for Set Agreement Problems[END_REF][START_REF] Zibin | Condition-Based Consensus in Synchronous Systems[END_REF]. In this paper, we are interested in conditions for the set agreement problem in an asynchronous system.

PI n ˚1897

Conditions

Let V be the set of values that can be proposed by the processes. Moreover, let ⊥ / ∈ V be a default value. An input vector is a size n vector over V ∪ {⊥}. The input vector J proposed in an execution has in its i-th entry J[i] the value of V proposed by p i , or ⊥ if p i did not take any step in the execution. We usually denote by I an input vector with all entries in V, and with J an input vector that may have some entries equal to ⊥; such a vector J is called a view. The set V n

x consists of all the input vectors with at most x entries equal to ⊥, and

V n = V n 0 . Definition 2 A condition C is a subset of V n .
Notation For any pair of vectors J1, J2

∈ V n x , J1 is contained in J2, denoted J1 ≤ J2, if ∀k : J1[k] = ⊥ ⇒ J1[k] = J2[k]. Moreover, J1 < J2 if J1 ≤ J2 and J1 = J2,
which means that J 2 has at least one non-⊥ values that J1 does not have. Also, # a (J) denotes the number of occurrences of a value a in the vector J, with a ∈ V ∪ {⊥}. For a set of input vectors C ⊆ V n , C x is the set of all vectors J with at most x entries equal to ⊥, and such that J ≤ I for some I ∈ C. Finally, dist(J, J ) is the Hamming distance separating J and J , where J and J are two vectors of V n

x .

Legality of a Condition

The main result of the condition-based approach to solve asynchronous consensus is based on the following definition as formulated in [START_REF] Friedman | Distributed Agreement Problems and their Connection with Errorcorrecting Codes[END_REF][START_REF] Zibin | Condition-Based Consensus in Synchronous Systems[END_REF]:

Definition 3 A condition C is x-legal if
there exists a function h : C → V with the following properties:

• ∀I ∈ C: h(I) = a ⇒ # a (I) > x, and • ∀I1, I2 ∈ C: h(I1) = h(I2) ⇒ dist(I1, I2) > x.
A fundamental result of the condition-based approach is a characterization of the conditions C for which consensus can be solved (for a precise definition of solving consensus for C see Definition 5, with k = 1):

Theorem 2 [START_REF] Mostefaoui | Conditions on Input Vectors for Consensus Solvability in Asynchronous Distributed Systems[END_REF] There is a t-fault tolerant protocol solving consensus for C if and only if C is t-legal.

A general method to define t-legal conditions is described in [START_REF] Mostefaoui | Condition-based Consensus Solvability: a Hierarchy of Conditions and Efficient Protocols[END_REF], and two natural t-legal conditions are described in [START_REF] Mostefaoui | Conditions on Input Vectors for Consensus Solvability in Asynchronous Distributed Systems[END_REF].

It is convenient to extend h to vectors J with ⊥ values. The lemma that follows shows that this is easy, provided J ∈ C x .

Lemma 1 Let C be an x-legal condition, and I1, I2 ∈ C, J ∈ C x such that J ≤ I1 and J ≤ I2. Then h(I1) = h(I2).

Proof Assume for contradiction that h(I1) = h(I2). We have dist(I1, I2) > x because C is x-legal. From the fact that J has at most x entries equal to ⊥ and J ≤ I1, we have dist(J, I1) ≤ x (similarly, we also have dist(J, I2) ≤ x). From these inequalities, the fact that the entries of J that differ in I1 and I2 are only its ⊥ entries, and again the fact that J has at most x entries equal to ⊥, we conclude that dist(I1, I2) ≤ x. A contradiction.

2 Lemma 1

Using this lemma we have a consistent definition:

Definition 4 Let C be an x-legal condition, and J be any vector in C x . The function h is extended to J by taking any I ∈ C with J ≤ I and letting h(J) = h(I).

Assuming up to t process crashes, and

-t ≤ d ≤ t, let S [d]
t be the set of all (td)-legal conditions (thus S

[0] t consists of the t-legal conditions). It is easy to check that

S [-t] t ⊂ • • • ⊂ S [-1] t ⊂ S [0] t ⊂ S [1] t ⊂ • • • ⊂ S [t] t ,
where S

[t]

t includes the condition made up of all the possible input vectors.

Irisa

The

The k-Set Agreement Problem

k-Set agreement Consensus is a fundamental problem in distributed computing that is impossible in an asynchronous system even with a single crash failure. While consensus requires all processes to decide on the same value, k-set agreement [START_REF] Chaudhuri | More Choices Allow More Faults: Set Consensus Problems in Totally Asynchronous Systems[END_REF] permits the processes to choose up to k different values. The problem is solvable when k -1 processes can crash, but not when k can crash. The proofs [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] of this result uncovered a deep connection between distributed computing and topology, and motivated a significant amount of subsequent research.

The set of values V that can be proposed is assumed to be such that |V| > k. Each process starts an execution with an arbitrary input value from V, the value it proposes, and all correct processes have to decide on a value such that (1) any decided value has been proposed, and (2) no more than k different values are decided. The consensus problem is k-set agreement for k = 1.

Condition-based set agreement

We are interested in conditions C that, when satisfied, make k-set agreement solvable in an asynchronous system where at most t process can crash. As we shall see, k-set agreement is solvable for

C ∈ S [d] t , if k ≥ d + 1.
Notice that if an input vector J ∈ C t occurs in an execution of a protocol, then as far as the processes with non-⊥ values in J can tell, the input vector could belong to I ∈ C, because they cannot distinguish from another execution where the other processes wake-up and propose their values after the former processes have made their decision. Given The first two are the safety requirements of the standard set agreement problem, and they should hold even if the input pattern does not belong to C. The third item requires termination under "normal" operating scenarios: (1) inputs that could belong to C or at least td processes crash, and (2.a) executions where a process decides, or (2.b) fewer than k processes crash (a situation where k-set agreement is solvable without conditions).

C ∈ S [d] t , we say that C is d-satisfied for input vector J if J ∈ C t or # ⊥ (J) ≥ t -d.
Notice that if set agreement is solvable for a condition C, then it is solvable for any C contained in C: the same protocol works. As mentioned above, when t < k, k-set agreement is solvable for V n , hence for any condition C.

Combining Conditions with φ y t to Solve Set Agreement

This section presents a set agreement protocol with access to a failure detector of the class φ y t , 0 ≤ y ≤ t, and instantiated with the function

h of a (t -d)-legal condition C ∈ S [d] t , 0 ≤ d ≤ t. It is a t-fault tolerant protocol that solves k-set agreement for C d t ,
where k = 1 + max(0, dy) (recall Definition 5). Thus, all the pairs (d, y) such that d ≤ y allow solving condition-based consensus.

Base Objects

In order to make the protocol simpler to understand, it is presented in a modular way. More specifically, it relies on the following base objects: three arrays of atomic registers, a consensus object, an adopt-commit-abort object, and a condition-set agreement object. An adopt-commit-abort object and a condition-set agreement object can always be implemented on top of base read/write registers. As far as the consensus object is concerned, as we will see, it can always be implemented in the particular context in which it is used by the processes. .n] can be read by any process, but only p i can write to the i-th component X[i]. To simplify the presentation we assume that, in addition to these atomic read and write operations, a process p i can also invoke the non-primitive operation snapshot(X) that allows it to read the content of all the registers of the array X as if this reading was done instantaneously. (Such an operation can be implemented in shared memory systems made up of single-writer, multi-readers atomic registers despite any number of process crashes (1 ≤ t < n) [START_REF] Afek | Atomic Snapshots of Shared Memory[END_REF][START_REF] Attiya | Atomic Snapshots in O(n log n) Operations[END_REF].) In accordance with the terminology defined in [START_REF] Herlihy | Linearizability: a Correctness Condition for Concurrent Objects[END_REF], the read, write and snapshot() operations are linearizable (i.e., they appear as if they had been executed one after the other, in agreement with their real-time occurrence order).

The shared memory

The underlying consensus object A consensus object is accessed by a process p i when p i invokes the operation alg cons(v i ) where v i is the value proposed by p i . Such an object allows any subset of processes to invoke alg cons(). Its properties are the following:

• Termination. Any correct participating process decides a value.

• Validity. A decided value is a proposed value.

• Agreement. No two different values are decided.

As we will see, the underlying consensus object is used when more than t-y process crash. It is shown in Theorem 8 that, in this case, a failure detector of the class P (the class of perfect failure detectors [START_REF] Chandra | Unreliable Failure Detectors for Reliable Distributed Systems[END_REF], see Section 8) can be built from a failure detector of the class φ y t (such a construction is described in the proof of Theorem 8), and consensus can be solved in a single-writer multi-reader atomic register asynchronous system enriched with such a failure detector 4 .

The underlying adopt-commit-abort object

The adopt-commit-abort object we use here is a simple variant of the adopt-commit-abort object introduced in [START_REF] Gafni | Round-by-round Fault Detectors: Unifying Synchrony and Asynchrony[END_REF][START_REF] Yang | Structured Derivations of Consensus Algorithms for Failure Detectors[END_REF] in the context of shared memory systems, and an object introduced in [START_REF] Mostéfaoui | Solving Consensus Using Chandra and Toueg's Unreliable Failure Detectors: a General Quorum-Based Approach[END_REF] in the context of message-passing systems 5 . Such an object has a single operation, denoted adopt commit(). A process p i invokes adopt commit(v i ) where v i is the value it proposes to the adopt-commit-abort object, and obtains a pair (d, v) as a result, where d is control tag and v a value. The object is defined by the following properties.

• Termination. Any correct participating process decides a pair (d, v).

• Validity. If a process decides (d, v), then d ∈ {commit, adopt, abort}, and v is a proposed value.

• Agreement. If a process decides (commit, v), then any other process that decides, decides (d, v) with d ∈ {commit, adopt}. • Obligation. If all the participating processes propose the same value v, then only the pair (commit, v) can be decided.

Intuitively, the adopt-commit-abort object is an abortable variant of consensus. Let us observe that a process that decides (abort, -), can conclude that no process decides (commit, -). However, when a process decides (adopt, -), it cannot conclude which control tag has been decided by the other processes.

The underlying condition-set agreement object

A condition-set agreement object has a single operation, denoted cond algo(). This object is designed to solve a set agreement problem with the help of a (td)-legal condition C. A process uses this object only in the particular context where the input vector J is such # ⊥ (J) ≤ ty.

A process p i invokes cond algo(V i ) where V i is its local view of the input vector J (we have then V i ≤ J and # ⊥ (V i ) ≤ ty), and only when the views can be ordered by containment, V i ≤ V j or V j ≤ V i for all i, j. If it returns from that invocation, p i obtains a value v. The object is defined by the following properties.

• Termination. Every correct process decides if (1) J ∈ C t or # ⊥ (J) ≥ td (C is d-satisfied for J) or (2.a) a process decides, or (2.b) more than (nk) correct processes invoke cond algo(). • Validity. A decided value is a value that has been proposed by a process in its input view.

• Agreement. At most k = 1 + max(0, dy) values are decided.

The Set agreement Protocol Description of the protocol The k-set agreement protocol based on a condition in C ∈ S [d]

t and a failure detector of the class φ y t is described in Figure 1. The variables subscripted with i are local variables of p i . A process is made up of two tasks: a main task T 1, and a background task T 2. The behavior of the task T 1 can be decomposed into four parts.

• A process first writes the value v i it proposes into V [i] (line 1). Then, using the snapshot() operation, it reads the array of proposed values until that array contains "enough" values (line 2). "Enough" means here that there are no more than (ty) missing values, or there are more than (ty) process that have crashed; this is known from the invocation QUERY y (S i ). (Let us recall that, when |S i | ≤ ty, QUERY y (S i ) answers always true). • Then, the behavior of p i depends on the number of values it knows. If there are too many crashes (line 4) p i sets a local variable prop i to the value CONS to try to decide a value from the underlying consensus algorithm (let us remind that, when there are more than (ty) crashes, it is possible to solve consensus from φ y t ). In the other case, p i knows enough proposed values to decide from the condition (line 5); p i computes consequently a value w i that could be decided from the condition, and sets prop i to COND.

• The process then uses the underlying adopt-commit-abort object (line 7) in order to try agreeing on the same tag, namely CONS or COND. Moreover, each p i deposits in the array W [1.

.n] the value it has computed at line 4 or line 5, and reads that array with the snapshot() operation. • The last part depends on the result returned by the adopt-commit-abort object.

-If p i obtains d i = abort or res i = CONS , it concludes that no value can be decided from the condition.

It consequently uses the consensus object to decide a value (lines 8-9). -If p i obtains res i = COND, at least one entry of W i is not equal to ⊥. Then, if additionally, d i = commit, p i concludes that any value deposited in W can be decided from the condition, and it decides it (lines 10-11). -If p i obtains res i = COND together with d i = adopt, it does not know if the other processes p j have obtained d j = commit or d j = abort. So, to be consistent, p i participates in the underlying consensus to which it proposes a value that could be decided from the condition (lines 12-14). It then decides the value returned by the consensus object.

The aim of the task T 2 is to guarantee that a correct process always decides as soon as a process decides. To that end, when a process p j is about to decide in task T 1 (execution of the return(v) statement), it first writes v in DEC [j]6 . The task T 2 of a process p i is then a simple loop statement that terminates when the predicate (∃j : DEC [j] = ⊥) becomes true. The execution of the return() statement by a process p i terminates its execution of k-set agreement

[d,y] n,t (v i ).

Proof of Correctness

Theorem 3 When instantiated with a failure detector of the class φ y t and a condition C in S

[d] t , the protocol described in Figure 1 Proof Validity property (a decided value has been proposed by a process). Let us observe that a decided value dec i is either an initial value v j proposed to the consensus by a process p j (line 9) or a value w i obtained by a process p i from the condition-set agreement object (lines 11 and 14). The validity property follows immediately from the corresponding validity property of the consensus object and the condition-set agreement object, and hence line 18 preserves validity.

Agreement property (at most k different values are decided). Let us observe that, due to the agreement property of the adopt-commit-abort object, it is not possible for two processes p i and p j that have invoked adopt commit() at line 7, to be such that both the predicate (res i = CON S) ∨ (d i = abort) and the predicate (res j = CON D) ∧ (d j = commit) are true. It follows from that observation that it is not possible for a process p i to execute line 9 while another process p j executes line 11. So, there are only two cases to consider (in addition to the trivial case of line 18). • No process begins executing 9 or 14. In that case, these processes decide the value returned by the consensus object. Due to the consensus agreement property, there is a single such value. • No process begins executing line 11 or 14. In that case, these processes decide a value returned from the condition-set agreement object . Due to the condition agreement property, there are at most k = 1 + max(0, dy) such values, which proves the case.

Function k-set agreement [d,y] n,t (v i ) task T 1: (1) V [i] ← v i ; (2) repeat V i ← snapshot (V ); S i ← {j | V i [j] = ⊥} (3) until QUERYy (S i ) end repeat; (4) case (# ⊥ (V i ) > t -y) then prop i ← CONS ; w i ← ⊥ (5) (# ⊥ (V i ) ≤ t -y) then prop i ← COND; w i ← cond algo(V i ) (6) end case; (7) W [i] ← w i ; (d i , res i ) ← adopt commit(prop i ); W i ← snapshot(W ); (8) case (res i = CON S) ∨ (d i = abort) (9) then DEC [i] ← cond algo(v i ); return (DEC [i]) (10) (res i = CON D) ∧ (d i = commit) (11) then DEC [i] ← W i [j] such that W i [j] = ⊥; return(DEC [i]) (12) (res i = CON D) ∧ (d i = adopt) (13) then est i ← W i [j] such that W i [j] = ⊥; (14) DEC [i] ← cond algo(est i ); return(DEC [i]) (15) end case task T 2: (16) j ← 0; (17) repeat forever j ← (j mod n) + 1; (18) if (DEC [j] = ⊥) then return(DEC [j]) end if (19) end repeat
Termination property. Let J be the input vector. We have to show that every correct process decides if (1) the condition C is d-satisfied for J, or (2.a) a process decides, or (2.b) fewer than k processes crash.

Let us notice that, as there are at most t process crashes (model assumption), the repeat loop of lines 2-3 always terminates. Moreover, let us also observe that, due to the termination property of the adopt-commit-abort object, any invocation of adopt commit() issued by a correct process terminates (observation O1).

Let us also observe that the underlying consensus protocol is used only when the number of crashes is greater than ty (line 4), i.e., when a failure detector of the class P can be built from a failure detector of the class φ y t (Item 3 of Theorem 8). The termination property of the consensus object ensures that all the correct processes that invoke cons alg() terminate their operation (observation O2). Let us now proceed by a case analysis.

• Case (1): We have to show that any correct process decides when the condition C is d-satisfied for J, where J is the input vector.

In that case, it follows from Item (1) of the termination property of the condition-set agreement object that any invocation cond algo() issued by a correct process terminates. This, combined with the observations O1 and O2, allows to conclude that any correct process terminates when C is d-satisfied for J.

• Case (2.a): We have to show that any correct process decides, as soon as a process decides.

This property is trivially guaranteed by the management of the array DEC [1.

.n] and task T 2.

• Case (2.b): We have to show that any correct process decides when fewer than k processes crash.

If no correct process accesses the condition-set agreement object, the fact that any correct process decides follows from the observations O1 and O2. So, let us consider the case where correct processes access the condition object. As k = 1+max(0, d-y) and fewer than k processes crash, this means that at most max(0, d-Irisa y) processes crash. Moreover, as t ≥ d, we have ty ≥ dy. It follows (from the properties of the failure detector φ y t ) that all the processes p i that execute the repeat loop (lines 2-3) and do not crash while executing that loop, eventually exit it, and we have then # ⊥ (V i ) ≤ ty. They consequently all access the condition-set agreement object at line 5. It follows that all the correct processes (there are more than (nk) of them) invoke the condition-set agreement object. Due to item (2.b) of the termination property of the condition-set agreement object, it follows that any correct process decides in the k-set agreement protocol.

2 T heorem 3

Implementation of a Condition-Set Agreement Object

Description of the protocol A t-fault tolerant protocol implementing a condition-set agreement object is described in Figure 2. This protocol is instantiated with a function h associated with a (td)-legal condition C. It uses a deterministic function F () and a predicate P (). The function F () takes a view J as a parameter and returns a non-⊥ value of the vector J. The value is a default value not in V and different from ⊥. It is assumed that the function h is extended to all views J of C with at most td entries equal to ⊥ as in Definition 4. The predicate P () is true on all such views:

P (V i ) ≡ ∃I ∈ C such that V i ≤ I .
Thus, P () is used to test if p i 's current view V i of the input vector could originate from a vector of the condition 7 .

Function cond algo (V i ) % We have # ⊥ (V i ) ≤ t -y, and V i ≤ V j or V j ≤ V i for all i, j % (1) if (# ⊥ (V i ) ≤ t -d) (2) then if P (V i ) (3)
then % The processes executing this line decide the same value % ( 4)

w i ← h(V i ); D[i] ← w i ; return (w i ) (5) else if (# ⊥ (V i ) = t -d) (6)
then % The processes executing this line decide the same value % ( 7)

w i ← F (V i ); D[i] ← w i ; return (w i ) (8)
else % If processes execute these lines, at most k value can be decided % ( 9)

D[i] ← ; (10) repeat D i ←snapshot (D) until (∃j : D i [j] = ⊥, ) ∨ (# ⊥ (D i ) < k) ¡ ; (11) if (∃j : D i [j] = ⊥, ) then return (D i [j] such that D i [j] = ⊥, ) (12)
else ∀j : if

(D i [j] = ) then Y i [j] ← V [j] (13) else Y i [j] ← ⊥ end if; (14) w i ← F (Y i ); D[i] ← w i ; return (w i ) (15)
end if [START_REF] Fischer | Impossibility of Distributed Consensus with One Faulty Process[END_REF] end if [START_REF] Friedman | Distributed Agreement Problems and their Connection with Errorcorrecting Codes[END_REF] end if [START_REF] Friedman | The Notion of Veto Number for Distributed Agreement Problems[END_REF]

else w i ← F (V i ); D[i] ← w i ; return (w i ) % Here (t -d) < (# ⊥ (V i ) ≤ t -y) % (19)
% The processes executing that line decide at most max(0, dy)) values % end if

Figure 2: A condition protocol

The protocol can be seen as a case analysis. The first step is for p i to check whether # ⊥ (V i ) ≤ td in order to benefit from the condition. If # ⊥ (V i ) > td, p i cannot benefit from it and consequently decides a value from its local view V i at line 18 (the processes executing that line decide at most max(0, dy) different values).

Otherwise we have # ⊥ (V i ) ≤ td, and then p i has enough non-⊥ entries in its view V i to test if the condition can help it decide. So, p i enters the lines 2-17. There are three cases. If P (V i ) is satisfied (first case), p i decides the value from the condition and writes it in the shared array D to help other processes decide (line 4).

If

P (V i ) is not satisfied (second case) p i first checks if # ⊥ (V i ) = t -d.
If so (second case), it knows that no other process will evaluate P to true in the previous line, and that any other process p j with # ⊥ (V j ) = td has V i = V j , so it deterministically decides F (V i ) (line 7).

In the third case, # ⊥ (V i ) < td and p i writes in D[i] to indicate it cannot decide from its local view V i (so, D[j] = ⊥ means that p j has not yet finished executing its protocol or has crashed). Then, as it cannot decide by itself, p i starts the "best effort termination" part of the protocol (lines 9-15). It enters a loop (line 10), during which it looks for a decided value (∃j : D i [j] = ⊥, ) and decides it if there is one (line 11), or a configuration where # ⊥ (D i ) < k (this is the only place where k is used in the protocol). If the condition ( ∃j

: D i [j] = ⊥, ) ∧ (# ⊥ (D i ) < k) is satisfied, p i
builds a local view of the input vector corresponding to the processes that have executed at least until line 9. As we will see in the proof, if several such views (Y i , Y j , etc.) are computed, due to the invocations of snapshot(D) at line 10 that precede their construction the associated containment property implies these views (Y i , Y j , etc.) are also ordered by containment. The process p i then decides the value F (Y i ). Let us notice that, as # ⊥ (D i ) < k, the vector Y i has at most k -1 entries equal to ⊥. It follows that at most k different values can be decided at line 14. Let α be the number of values decided at line 4, 7, 11 and 18, and β be the number of values decided at lines 14. The proof will show that α + β ≤ k.

Correctness proof

Theorem 4 When instantiated with a (td)-legal condition C, the protocol described in Figure 2 implements a condition-set agreement object with k = 1 + max(0, dy).

Proof Validity property (a decided value is a value proposed in the input view of a process). This property follows directly from the fact that both the function h() and the function F () extracts a non-⊥ value from the vector they are applied to.

Agreement property (at most k = 1 + max(0, dy) different values are decided). The processes that decide, do it at line 4, 7, 11, 14, or 18. We determine the maximum number of values that are decided by the processes at each of these lines of the protocol.

• Consider the processes that decide at line 4.

These processes p i are such that (# ⊥ (V i ) ≤ td) and P (V i ) is satisfied. We show that a single value can be decided at line 4.

Let p i and p j be two processes that decide at line 4. Due to the use of a snapshot operation, we have either

V i ≤ V j or V j ≤ V i . Let us consider that V i ≤ V j . We then have (1) # ⊥ (V i ) ≤ t -d and # ⊥ (V j ) ≤ t -d, (2)
both P (V i ) and P (V j ) are satisfied, i.e., ∃I1 ∈ C such that V i ≤ I1, and ∃I2 ∈ C such that V i ≤ V j ≤ I2, (3) and the condition is (td)-legal. It follows from these three items and Lemma 1 that h(V i ) = h(V j ) = h(I 1 ) = h(I 2 ). Consequently, no more than one value can be decided by the processes executing line 4.

• Consider the processes that decide at line 7. These processes p i are such that (# ⊥ (V i ) = td) and P (V i ) is not satisfied. In this case at most one value is decided at line 7, because due to the snapshot containment property, all processes that execute this line have exactly the same view V i . Moreover, if a process executes this line, no process executes line 4. This is because any process p j that executes line 4 has a view V j such that (# ⊥ (V j ) ≤ td = # ⊥ (V i )) and as we have either V i < V j or V j < V i we conclude that V i < V j . Consequently, if p i executes line 7, P (V i ) is false, and hence P (V j ) is also false as V i ≤ V j , by definition of the predicate P ().

• Consider the processes that decide at line 18. These processes

p i are such that (t -y ≥ # ⊥ (V i ) > t -d).
We show that these processes decide at most max(0, dy) different values.

Due to the containment property on the vectors provided by the snapshot operation, any pair of processes p i and p j that execute line 18 are such that V i ≤ V j (or V j ≤ V i ). We conclude from that observation that the processes that execute line 18 have at most max(0, (ty) -(td))=max(0, dy) different vectors. As F is deterministic, at most max(0, dy) different values can be decided by the processes that decide at line 18.

It follows that, when we consider the processes that decide at line 4, 7 or 18, at most k = 1 + max(0, td) different values can be decided.

Irisa

• Consider the processes that decide at line 11.

A process p i that decides at line 11, decides a value (that it retrieves in D[j]) that has been decided by another process p j (p j has deposited that value in D[j] at line 4, 7, 14 or 18). Consequently, no additional value can be decided at line 11.

• Finally, consider the processes that decide at line 14.

Let β be the number of different values decided by the processes that execute line 14. Let α be the number of values decided by the processes that execute line 4, 7 or 18. We claim that α + β ≤ k = 1 + max(0, td).

It follows from this case analysis that at most k = 1 + max(0, td) different values can be decided, which proves the theorem.

Proof of the claim. Let us consider two time instants t 0 and t 1 defined as follows:

-

t 0 = first time instant where # ⊥ (D) = k -1 (or +∞ if it never happens), -t 1 = first time instant where ∃ D[j] / ∈ { , ⊥} (or +∞ if it never happens) 8 .
Let us first consider t 1 ≤ t 0 . Let us notice that a process p i stops the repeat loop of line 10 as soon as

(∃ D i [j] / ∈ { , ⊥} ∨ # ⊥ (D i ) < k).
As the test that (at line 11) immediately follows the exit of the repeat loop privileges the case (∃ D i [j] / ∈ { , ⊥}) with respect to the case (# ⊥ (D i ) < k) when both are satisfied, it follows that p i immediately executes the return () statement at line 11. Consequently, when t 1 ≤ t 0 , any process p i that enters the loop of line 10 and then decides, decides at line 11. We then have β = 0 (no process decides at line 14).

Let us now consider the case t 0 < t 1 . Let us first observe that, since the function F () is deterministic and each Y i computed at lines 12-13 contains at most (k -1) entries equal to ⊥, it follows that the β values decided at line 14 correspond to (at least) β different Y i vectors, which means (due to line 12) at least β different D i vectors.

Due to the containment property of the invocations of the snapshot (D) invocations at line 10, the previous β D i vectors are totally ordered (see the definition of "<" in Section 4.1), e.g.,

D i1 < D i2 < • • • < D iβ < • • •
and contain only ⊥ and entries. Moreover, for any pair of such vectors there is at least one entry which is equal to ⊥ in one vector and to in the other. As D is initialized to [⊥, . . . , ⊥], and there are at least β different D ix , we conclude that at least (β -1) values have been written into D after t 0 (because, due to the snapshot (D) operations, we have

# ⊥ (D i1 ) ≤ k -1 at time t 0 , # ⊥ (D i2 ) ≤ k -2 at time t 0 , t 0 > t 0 , etc.).
Before being decided, the α different values decided at lines 4, 7 and 18 have been written into the array D (they are decided after t 1 ). Due to the definition of t 1 , they have been written into D at or after t 1 , i.e. (from the case assumption), after t 0 .

Hence, after t 0 , α entries of D have been set to proposed values by lines 4, 7 and 18, and (β -1) entries have been set to . As, at t 0 , the number of entries of D that were equal to ⊥ was equal to (k -1), it follows that α + (β -1) ≤ (k -1), i.e., α + β ≤ k, which proves the claim when t 0 < t 1 . End of the proof of the claim.

Termination property (let J be the actual input vector. Every correct process decides if (1) J ∈ C t or # ⊥ (J) ≥ t-d -C is d-satisfied for Jor (2.a) a process decides, or (2.b) more than (nk) correct processes invoke cond algo()).

If the input vector V i , V i ≤ J, is such that # ⊥ (V i ) > td, the process p i trivially decides at line 18. When # ⊥ (V i ) = td, the test on line 5 leads to termination. On another side, if # ⊥ (V i ) ≤ td and J ∈ C t , then P (V i ) is satisfied and p i decides at line 4. So, the case (1) is done.

Let us consider case (2.a). Before deciding a value at line 4, 7, 14, or 18, a process deposits that value in the array D. It follows that, after a process has decided, the repeat loop of line 10 always terminates, and any process that executes line 11 decides, which proves the case.

Let us finally consider case (2.b). Let us assume that more than (nk) correct processes invoke the object and no one decides. This means that none of them executes line 4, 7, or 18. They all consequently enter the repeat loop at line 10, from which we conclude that eventually the predicate # ⊥ (D i ) < k becomes true. It follows that the correct processes exit the repeat loop and decide.

2 T heorem 4 6 Discussion

Initial Crashes: No Condition is Needed

The theorem that follows considers a particular case, namely the case where the faulty processes crash before the protocol starts its execution.

Theorem 5 Consider an execution of the protocol described in Figure 1 instantiated with a failure detector of the class φ y t . Let us assume that more than (ty) processes have crashed before the protocol starts. The protocol then solves the consensus problem (whatever the (td)-legal condition it is instantiated with).

Proof If more than (ty) processes have initially crashed, due to the property of the QUERY y () invocations at line 3, we have (# ⊥ (V i ) > ty) for any process p i . It follows that, for any process p i , we have prop i = CONS (line 4). Due to the obligation property of the adopt-commit-abort object, every process p i obtains (commit, CONS ). Consequently, all the processes invoke the underlying consensus object, which proves the theorem.

2 T heorem 5

Remark The previous theorem considers the case where the faulty processes have crashed before the protocol starts.

It is interesting to observe that a similar result appears in [START_REF] Fischer | Impossibility of Distributed Consensus with One Faulty Process[END_REF], where a consensus protocol is presented for asynchronous systems where a majority of processes are correct, and the faulty processes crash before the protocol starts its execution.

An Always Terminating Version of the Protocol

It is possible to trade safety for liveness by providing a version of the protocol where every correct process always decides. This can be obtained at the price of an enlarged set of possibly decided values. More precisely, let I be an input vector, and C the (td)-legal condition the protocol is instantiated with. When I ∈ C, at most k = 1 + max(0, dy) values are decided; when I / ∈ C, up to k = t + 1y values can be decided. Interestingly, this always terminating version of the protocol provides a new insight into the way the parameters t, y (power of the failure detection) and d (power of the condition) are related.

In the protocol described in Figure 2, the statement that can prevent a correct process p i from terminating is the repeat loop at line 10. This occurs when p i enters the lines 9-15, V i being such that # ⊥ (V i ) ≤ min(ty, td) (assumption on the input parameter and line 1), while P (V i ) is equal to false (line 2). The modification to get an always terminating cond algo() protocol is very simple: it consists in replacing the lines 9-15 in Figure 2 by a weakened statement that always terminates, namely: Proof Every correct process trivially terminates, and a decided value comes from a proposed vector (same proof as in Theorem 4).

As far as the number of values that are decided is concerned, let us first consider the case where the input vector belongs to the condition. In that case, when a process p i executes line 2, P (V i ) is trivially satisfied. It follows that the new line [START_REF] Chaudhuri | More Choices Allow More Faults: Set Consensus Problems in Totally Asynchronous Systems[END_REF][START_REF] Chaudhuri | Tight Bounds for k-Set Agreement[END_REF][START_REF] Chu | Reducing Ω to 3[END_REF][START_REF] Delporte-Gallet | The Weakest Failure Detectors to Solve Certain Fundamental Problems in Distributed Computing[END_REF][START_REF] Prisco | On k-Set Consensus problems in Asynchronous Systems[END_REF][START_REF] Dwork | Consensus in the Presence of Partial Synchrony[END_REF][START_REF] Fischer | A Lower Bound for the Time to Assure Interactive Consistency[END_REF]' is never executed. Consequently, Theorem 4 remains valid when I ∈ C, and at most k = 1+max(0, d-y) values are then decided.

Considering now the case where the input vector does not belong to the condition, let us first observe that if a process p i decides at line [START_REF] Chaudhuri | More Choices Allow More Faults: Set Consensus Problems in Totally Asynchronous Systems[END_REF][START_REF] Chaudhuri | Tight Bounds for k-Set Agreement[END_REF][START_REF] Chu | Reducing Ω to 3[END_REF][START_REF] Delporte-Gallet | The Weakest Failure Detectors to Solve Certain Fundamental Problems in Distributed Computing[END_REF][START_REF] Prisco | On k-Set Consensus problems in Asynchronous Systems[END_REF][START_REF] Dwork | Consensus in the Presence of Partial Synchrony[END_REF][START_REF] Fischer | A Lower Bound for the Time to Assure Interactive Consistency[END_REF]' a value D[j] such that D[j] = ⊥, it does not decide a new value as D[j] is counted as a decided value at line 4, 7, 18 or in the else part of the new if statement. So, let us count the number of values that can be decided by the processes executing line 4 or the else part of the new line [START_REF] Chaudhuri | More Choices Allow More Faults: Set Consensus Problems in Totally Asynchronous Systems[END_REF][START_REF] Chaudhuri | Tight Bounds for k-Set Agreement[END_REF][START_REF] Chu | Reducing Ω to 3[END_REF][START_REF] Delporte-Gallet | The Weakest Failure Detectors to Solve Certain Fundamental Problems in Distributed Computing[END_REF][START_REF] Prisco | On k-Set Consensus problems in Asynchronous Systems[END_REF][START_REF] Dwork | Consensus in the Presence of Partial Synchrony[END_REF][START_REF] Fischer | A Lower Bound for the Time to Assure Interactive Consistency[END_REF]'. For each such process p i we have # ⊥ (V i ) ≤ tmax(y, d + 1). Moreover (due to the containment property on the vectors V i provided by Irisa the cond algo() invocations we have V i ≤ V j (or V j ≤ V i ) for two processes executing line 4 or the else part of line [START_REF] Chaudhuri | More Choices Allow More Faults: Set Consensus Problems in Totally Asynchronous Systems[END_REF][START_REF] Chaudhuri | Tight Bounds for k-Set Agreement[END_REF][START_REF] Chu | Reducing Ω to 3[END_REF][START_REF] Delporte-Gallet | The Weakest Failure Detectors to Solve Certain Fundamental Problems in Distributed Computing[END_REF][START_REF] Prisco | On k-Set Consensus problems in Asynchronous Systems[END_REF][START_REF] Dwork | Consensus in the Presence of Partial Synchrony[END_REF][START_REF] Fischer | A Lower Bound for the Time to Assure Interactive Consistency[END_REF]'. It then follows that there are at most k1 = tmax(y, d + 1) + 1 different vectors V i for the processes that execute line 4 or the else part of line [START_REF] Chaudhuri | More Choices Allow More Faults: Set Consensus Problems in Totally Asynchronous Systems[END_REF][START_REF] Chaudhuri | Tight Bounds for k-Set Agreement[END_REF][START_REF] Chu | Reducing Ω to 3[END_REF][START_REF] Delporte-Gallet | The Weakest Failure Detectors to Solve Certain Fundamental Problems in Distributed Computing[END_REF][START_REF] Prisco | On k-Set Consensus problems in Asynchronous Systems[END_REF][START_REF] Dwork | Consensus in the Presence of Partial Synchrony[END_REF][START_REF] Fischer | A Lower Bound for the Time to Assure Interactive Consistency[END_REF]'. Let us observe that if a process p j decides at line 4, the same vector V j will not be used to decide another value at line [START_REF] Chaudhuri | More Choices Allow More Faults: Set Consensus Problems in Totally Asynchronous Systems[END_REF][START_REF] Chaudhuri | Tight Bounds for k-Set Agreement[END_REF][START_REF] Chu | Reducing Ω to 3[END_REF][START_REF] Delporte-Gallet | The Weakest Failure Detectors to Solve Certain Fundamental Problems in Distributed Computing[END_REF][START_REF] Prisco | On k-Set Consensus problems in Asynchronous Systems[END_REF][START_REF] Dwork | Consensus in the Presence of Partial Synchrony[END_REF][START_REF] Fischer | A Lower Bound for the Time to Assure Interactive Consistency[END_REF]'. Finally, due to that observation and the fact that F () is deterministic, at most k1 different values can be decided by the processes executing line 4 or the else part of line [START_REF] Chaudhuri | More Choices Allow More Faults: Set Consensus Problems in Totally Asynchronous Systems[END_REF][START_REF] Chaudhuri | Tight Bounds for k-Set Agreement[END_REF][START_REF] Chu | Reducing Ω to 3[END_REF][START_REF] Delporte-Gallet | The Weakest Failure Detectors to Solve Certain Fundamental Problems in Distributed Computing[END_REF][START_REF] Prisco | On k-Set Consensus problems in Asynchronous Systems[END_REF][START_REF] Dwork | Consensus in the Presence of Partial Synchrony[END_REF][START_REF] Fischer | A Lower Bound for the Time to Assure Interactive Consistency[END_REF]'. On the other side, the processes that execute line 18 decide at most k2 = max(0, dy) different values (the proof is the same as the corresponding proof in Theorem 4). Recall that all the processes that execute line 7 decide the same value. Finally, summing up, we get k = k1 + k2 + 1, i.e., k = tmax(y, d + 1) + 1 + max(0, dy) + 1), which can be simplified to provide k = t + 1y.

2 T heorem 6

Let us notice that when the input vector does not belong to the condition, the maximal number of values that can be decided, namely, k = t + 1y, does not depend on d. If the information on failure is maximal (y = t), the protocol solves consensus. At the other extreme, if there is no information on failures (y = 0), and there is no power provided by the condition, the protocol solves the trivial version of the set agreement problem, namely k = t + 1.

A Lower Bound

This section presents a lower bound matching Theorem 3.

Theorem 7

When instantiated with a failure detector of the class φ y t and a (td)-legal condition, no protocol solves the condition-based k-set agreement problem for k ≤ max(0, dy).

Proof Assume for contradiction that a protocol solves the k-set agreement problem for k ≤ max(0, dy). Hence, d > y and max(0, dy) = dy. Partition the processes in two groups, the main processes p 1 , . . . , p n-t+d and the secondary processes, p n-t+d+1 , . . . , p n . Consider the executions where the secondary processes crash before taking any steps. These are executions with at least td failures. By Definition 5, all correct process must decide whatever the input vector. Now, consider the subset of these executions with at most dy additional failures. The total number of failures is at most ty failures. Recall that any relevant query is invoked with a set the size of which is greater than (ty). So, all relevant invocations QUERY y () issued by the main processes will include at least one correct process and thus will return false and all other invocations return the trivial output. Thus, in these executions, the failure detector gives no information, and therefore, the main processes have to solve the standard set agreement problem (i.e. terminate for every input vector), tolerating dy failures. The results of [START_REF] Borowsky | Generalized FLP Impossibility Results for t-Resilient Asynchronous Computations[END_REF][START_REF] Herlihy | Algebraic Spans[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] (more specifically, Corollary 5.5 in [START_REF] Herlihy | Algebraic Spans[END_REF]) imply that in one of these executions at least dy + 1 different values are decided, a contradiction.

2 T heorem 3

The following corollaries are direct consequences of the previous theorem. They consider the extreme cases where there is either no failure detector (i.e., y = 0), or no condition (i.e., d = t). The first corollary answers an open problem stated in [START_REF] Attiya | Wait-Free n-Set Consensus when Inputs are Restricted[END_REF][START_REF] Mostefaoui | Condition-Based Protocols for Set Agreement Problems[END_REF]. The second corollary shows the optimality 9 This section presents the failure detectors introduced by Chandra and Toueg, used in this paper. These classes are defined from the following completeness and accuracy properties [START_REF] Chandra | Unreliable Failure Detectors for Reliable Distributed Systems[END_REF]:

-Strong (Weak) completeness. Eventually, every process that crashes is permanently suspected by every (some) correct process.

-Perpetual strong accuracy. No process is suspected before it crashes.

-Eventual strong accuracy. There is a time after which no correct process is suspected.

-Perpetual weak accuracy. Some correct process is never suspected.

-Eventual weak accuracy. There is a time after which some correct process is never suspected.

The classes we are interested in are the following [START_REF] Chandra | Unreliable Failure Detectors for Reliable Distributed Systems[END_REF]. They are collectively called "Chandra and Toueg's failure detector classes" in the rest of the paper.

• P: The class of perfect failure detectors. It includes all the failure detectors satisfying strong completeness and perpetual strong accuracy.

• S: The class of strong failure detectors. It includes all the failure detectors satisfying strong completeness and perpetual weak accuracy. We have P ⊆ S.

• 3P: The class of eventually perfect failure detectors. It includes all the failure detectors satisfying strong completeness and eventual strong accuracy. We have P ⊆ 3P.

• 3S: The class of eventually strong failure detectors. It includes all the failure detectors satisfying strong completeness and eventual weak accuracy. We have 3P ⊆ 3S, and S ⊆ 3S.

The class 3S is the weakest that allows solving the consensus problem, and is equivalent to the class 3W in shared memory systems and in message passing systems with reliable channels [START_REF] Chandra | Unreliable Failure Detectors for Reliable Distributed Systems[END_REF][START_REF] Chandra | The Weakest Failure Detector for Solving Consensus[END_REF]. It has also been shown that 3S and the class of leader failure detectors, denoted Ω, are equivalent in systems where each process initially knows all the process identities [START_REF] Chandra | The Weakest Failure Detector for Solving Consensus[END_REF][START_REF] Chu | Reducing Ω to 3[END_REF][START_REF] Mostefaoui | From 3W to Ω: a Simple Bounded Quiescent Reliable Broadcastbased Transformation[END_REF].

Figure 3 summarizes Chandra and Toueg's failure detector classes. Following Definition 1, an arrow from A to B means that A ≥ B (any failure detector of the class A can be used to build a failure detector of the class B). The absence of a path from A to B means that it is not the case A ≥ B (given any failure detector of the class A, it is not possible to build a failure detector of the class B). Finally, A ≡ B if A ≤ B and B ≤ A. The figure follows from [START_REF] Chandra | The Weakest Failure Detector for Solving Consensus[END_REF][START_REF] Chandra | Unreliable Failure Detectors for Reliable Distributed Systems[END_REF].

Irisa

Proof Let us first consider item (1). The construction described in Figure 4 constructs a perfect failure detector from a failure detector of the class φ t t . This construction works as follows. A process that queries the perfect failure detector obtains the current value of the set suspected i . As y = t, QUERY t (S) -where S is made up of a single process peventually returns true if and only p has crashed. The strong completeness and strong accuracy properties defining the class P follow. Moreover, φ t t ≤ P follows directly from their definitions. Therefore, P is equivalent to φ t t .

init: suspected i ← ∅ repeat forever for all j such that p j ∈ ({p 1 , . . . , pn} \ suspected i ) do if QUERYt({p j }) then suspected i ← suspected i ∪ {p j } end if end repeat Figure 4: From φ t t to P (algorithm for p i )

For proving item (2), let us first observe that an implementation that systematically suspects all the processes trivially satisfies the completeness property of any of Chandra and Toueg's failure detector classes, but prevents its accuracy property from being satisfied. So, assuming that φ y t (0 ≤ y ≤ t -1) allows implementing the accuracy property of any of Chandra and Toueg's failure detector classes, we show that it does not allow implementing the associated (weak or strong) completeness property.

Let us consider any run during which no more than x = ty (1 ≤ x ≤ t) processes crash. Due to the definition of φ y t , we have the following:

• Any QUERY t (S) where |S| ≤ ty = x always returns true whatever the x (≥ 1) processes composing S. This follows from the triviality property of φ y t , |S| ≤ ty = x. • Any QUERY t (S) where |S| > x always returns false whatever the processes composing S. This follows from the safety property of φ y t , as at least one process among these processes has not crashed. These observations show that, when no more than x = ty (1 ≤ x ≤ t) processes crash, the boolean value returned by a query depends only on the number of processes defining S (it depends neither on which processes are in S, nor on the failure pattern). It follows that, when no more than x = ty (1 ≤ x ≤ t) processes crash, there is no way for a process to know if a given process has crashed or not, thereby making impossible to implement the (weak or strong) completeness property of any of Chandra and Toueg's failure detector classes.

The proof of item (3) consists in designing an algorithm that, in runs where f > ty, builds a failure detector of the class P from a failure detector of the class φ y t . Let us first observe that, as f > ty, there is a set S such as |S| = ty + 1 and, after some finite time, QUERY y (S) returns true forever. The algorithm is the following.

• Each set suspected i is initialized to ∅. Initially, each process p i issues QUERY y (X) for all the possible sets X of size |X| = ty + 1 until such a query returns true. Due to the fact that all the queries are relevant (ty < |X| ≤ t), and the previous observation, this eventually happens. When it occurs, p i considers the corresponding set (say S) and executes suspected i ← S. • Then, for each p j / ∈ suspected i , p i regularly executes QUERY y (S ∪ {p j }). If the query returns true, p i can conclude from the property of φ y t that p j has crashed. It consequently adds p j to suspected i . Otherwise p i keeps on issuing QUERY y (S ∪ {p j }).

It follows from the definition of S and the safety and liveness properties of φ y t that the sets suspected i of the correct processes eventually include all the crashed processes, and never includes a "not yet" crashed process, i.e., they satisfy the properties that define the class P of perfect failure detectors [START_REF] Chandra | Unreliable Failure Detectors for Reliable Distributed Systems[END_REF].

2 T heorem 8 In contrast, we show that there is no protocol transforming any failure detector of the class φ y t , for y < t, into a failure detector of the class P. Proof The triviality property of φ y t is ensured by the first two case statements. The safety property follows from the fact that, due to the perpetual strong accuracy of the underlying failure detector, suspected i contains only crashed processes. Finally, the liveness property of φ y t follows from the fact that, due to completeness of the underlying failure detector, the set suspected i eventually contains all crashed processes.

2 T heorem 9

The next theorem states that there is no protocol transforming a failure detector of the class S, 3P, 3S or 3W into a failure detector of the class φ y t for 0 < y. It is surprising that these failure detectors are not strong enough to implement φ y t even when y < t, as in this case φ y t cannot solve consensus (Corollary 2), while these failure detectors can solve consensus. (In the case of y = t both φ t t and those failure detectors can solve consensus.)

Theorem 10 For 1 ≤ y ≤ t, φ y t ≤ S, φ y t ≤ 3P, φ y t ≤ 3S, and φ y t ≤ 3W.

Proof The impossibility comes from the fact that nothing prevents the sets suspected i from containing correct processes for an unbounded amount of time. As 3S < 3P and 3W < 3P, it is sufficient to prove it for 3P, as far as 3S, 3W and 3P are concerned. The proof for S is verbatim the same as the one for 3P (replacing only 3P by S).

The proof consists in assuming (for contradiction) that there is a protocol transforming a failure detector of the class 3P into a failure detector of the class φ y t . Let us consider a run where an infinite sequence of relevant queries is issued, all of the form QUERY y (S), for the same S, ty < |S| ≤ t, and suppose that all processes in S are initially crashed. The answers returned by the protocol define then a sequence consisting of a finite prefix of false answers followed by an infinite suffix of true answers (by the safety and liveness property of φ y t ). Let τ be a time instant after which all the invocations of QUERY y (S) return true.

However, it could be that no process ever crashes, and no process in S takes a step until after τ + δ (where δ > 0 is an arbitrary finite period), with 3P suspecting each process exactly as in the previous fault-prone run from the very beginning until τ + δ.

As 3P provides each process with the same outputs in both runs until time τ + δ, it follows that the queries QUERY y (S) issued between τ and τ + δ returns true in both runs. This contradicts the safety property of φ y t in the failure-free run.

2 T heorem 10

Conclusion

This paper focused on the combination of two approaches to solve the k-set agreement problem, namely failure detectors and conditions. It has proposed novel failure detectors for solving the k-set agreement problem, that, when combined with a condition, establish a new bridge among asynchronous, synchronous and partially synchronous systems with respect to agreement problems. The paper has presented three main contributions. The first is the new class of failure detectors denoted φ y t , 0 ≤ y ≤ t. The processes can invoke a primitive QUERY y (S) with any set S of process ids. Roughly speaking, QUERY y (S) returns true only when all processes in S have crashed, provided ty < |S| ≤ t. These failure detectors seem interesting in their own right. They have been thoroughly investigated, and compared to the classical failure detectors introduced by Chandra and Toueg.

The second contribution of the paper is a condition-based protocol that solves the k-set agreement problem, with k = 1 + max(0, t -(x + y)), for a condition C of power x and a failure detector of power y, with termination guaranteed for inputs in C. By "power" we mean: C is x-legal if and only if it can be used to solve x-fault tolerant Irisa asynchronous consensus, and the failure detector is in the class φ y t , 0 ≤ y ≤ t. Several noteworthy properties and variants of this protocol (that provides a new way to solve asynchronous set agreement and in particular consensus) have been studied.

The third contribution is a corresponding lower bound, showing that there is no φ y t -based k-set agreement protocol for (td)-legal conditions with k ≤ max(0, dy). It follows from this lower bound that there is no condition-based k-set agreement protocol such that k ≤ d for any (td)-legal condition.

  A T O I R E S P U B L I C A T I O N I N T E R N E N° 1897 I R I S A CAMPUS UNIVERSITAIRE DE BEAULIEU -35042 RENNES CEDEX -FRANCE ISSN 1166-8687

Definition 5 A

 5 t-fault tolerant protocol solves the k-set agreement problem for a condition C ∈ S [d] t if in every execution with input vector J, the protocol satisfies the following properties: • Validity. Every decided value is a proposed value 3 . • Agreement. No more than k different values are decided. • Termination. Every correct process must decide if (1) C is d-satisfied for J and no more than t processes crash, or (2.a) a process decides, or (2.b) fewer than k processes crash.

  The shared memory is made up of three arrays (denoted V [1..n], W [1..n] and DEC [1..n]) of single-writer multi-reader atomic registers. All are initialized to [⊥, . . . , ⊥]. The j-th entry of an array X[1.

  solves the condition-based k-set agreement problem where k = 1 + max(0, dy).

Figure 1 :

 1 Figure 1: A k-set agreement protocol with k = 1 + max(0, dy)

[ 9 -Theorem 6

 96 15]' if (∃j : D[j] = ⊥) then return (D[j] such that D[j] = ⊥) else w i ← F (V i ); D[i] ← w i ; return (w i ) end if Let us consider the protocol depicted in Figure 2 instantiated with a (td)-legal condition C, where the lines 9-15 are replaced by the statement [9-15]'. Every correct process decides. Let I be an input vector. If I ∈ C, at most k = 1 + max(0, dy) values are decided. If I / ∈ C, at most k = t + 1y values can be decided.

Figure 3 :

 3 Figure 3: Relations among Chandra-Toueg's failure detector classes

8. 3 FromFigure 5

 35 Figure5presents a simple protocol transforming any failure detector of the class P into a failure detector of the class φ y t . The underlying set suspected i satisfies (by assumption) the properties defining the class P. In contrast, we show that there is no protocol transforming any failure detector of the class φ y t , for y < t, into a failure detector of the class P.

Figure 5 :Theorem 9

 59 Figure 5: From P to φ y t (algorithm for p i )

  Classes {φ y t } 0≤y≤tA failure detector of the class φ 0 t provides no information related to failures as the invocation QUERY y (S) answers always true if |S| ≤ t, and false if |S| > t. At the other extreme, with a failure detector of the class φ t t a process can query about the failure status of a single specific process, since QUERY y (S) may return significant failure information about sets S of any size, 1 ≤ |S| ≤ t. That is, φ 0 t and φ t t are two extreme classes. This section compares the power of distinct classes of failure detectors denoted φ y1 t and φ y2 t .

Definition 1 For two classes of failure detectors A, B, we denote A ≤ B, and say that B is at least as strong as A, if any failure detector in B can be used to build a failure detector in A. We also say that B is stronger than A (denoted A < B), if A ≤ B and B ≤ A. The classes A and B are equivalent, (denoted A ≡ B), if A ≤ B and B ≤ A.

Combined Power of Conditions and Information on Failures to Solve Asynchronous Set Agreement 11

  NotationIn the rest of the paper, C d t denotes a condition that belongs to S

	[d]

t .

the Chandra and Toueg's Failure Detector Classes 8.1 Chandra and Toueg's Failure Detector Classes

  When considering the family (φ y t ) 0≤y≤t of failure detector classes, φ y t with y = tk + 1, is the weakest that allows solving the k-set agreement problem.

	8 Comparing φ y t with

of φ y t . Corollary 1 Let C be a (td)-legal condition. There is no condition-based k-set agreement protocol for C when k ≤ d. Corollary 2

Respect to Chandra and Toueg's Failure Detector Classes

	8.2 φ y t with This section studies the relation between φ y t and the classic failure detectors introduced by Chandra and Toueg. We show that φ t t allows building a perfect failure detector, namely, P ≤ φ t t (Theorem 8). Therefore, P is equivalent to φ t t as φ t t ≤ P (from their definitions).
	Theorem 8 (1) P ≡ φ t t . Let f denote the actual number of process crashes in a run. (2) If f ≤ t-y, φ y t , 0 ≤ y ≤ t-1
	does not allow building a failure detector of any of Chandra and Toueg's failure detector classes (e.g. 3S, 3P, Ω). (3) If f > t -y, φ y t , 0 ≤ y ≤ t -1 allows building a failure detector of the class P.

when

  QUERYy (S) is invoked by p i : case (|S| ≤ ty) then return (true) (|S| > t) then return (false) (ty < |S| ≤ t)then return (S ⊆ suspected i ) end case

There are other approaches, like randomization or stronger shared memory primitives.PI n ˚1897

We have shown in[START_REF] Mostefaoui | On the Computability Power and the Robustness of Set Agreementoriented Failure Detector Classes[END_REF] that there are transformations between the φ failure detectors and a version with no input parameter. It is consequently possible to define them according to the failure pattern only.Irisa

It is shown in[START_REF] Prisco | On k-Set Consensus problems in Asynchronous Systems[END_REF] that the solvability of k-set agreement is highly sensitive to the validity property adopted.PI n ˚1897

For completeness, a 3P-based alg cons() protocol is described in Appendix A. (Trivially, any failure detector in P is also in 3P.) Others shared memory consensus algorirhms based on failure detectors can be found in[START_REF] Attiya | Distributed Computing, Fundamentals, Simulation and Advanced Topics[END_REF][START_REF] Guerraoui | The Alpha of Asynchronous Consensus[END_REF][START_REF] Lo | Using failure Detectors to solve Consensus in Asynchronous Shared Memory Systems[END_REF].

A wait-free implementation of an adopt-commit-abort object from single-writer multi-reader atomic registers can be found in[START_REF] Yang | Structured Derivations of Consensus Algorithms for Failure Detectors[END_REF]. An implementation in message-passing systems where a majority of processes is correct is presented in[START_REF] Mostéfaoui | Solving Consensus Using Chandra and Toueg's Unreliable Failure Detectors: a General Quorum-Based Approach[END_REF]. For completeness an implementation of an adopt-commit-abort object is described in Appendix B.Irisa

This write plays the same role as the reliable broadcast of the decided value in message-passing systems (e.g., see the consensus protocols in[START_REF] Chandra | Unreliable Failure Detectors for Reliable Distributed Systems[END_REF][START_REF] Guerraoui | The Information Structure of Indulgent Consensus[END_REF][START_REF] Mostéfaoui | Solving Consensus Using Chandra and Toueg's Unreliable Failure Detectors: a General Quorum-Based Approach[END_REF][START_REF] Schiper | Early Consensus in an Asynchronous System with a Weak Failure Detector[END_REF]). Their aim is to prevent a process from deadlocking.PI n ˚1897

It is shown in[START_REF] Mostefaoui | Conditions on Input Vectors for Consensus Solvability in Asynchronous Distributed Systems[END_REF] that, for some conditions, there are very efficient ways to compute the predicate P (). As an example, for the (td)-legal condition C1 (defined in Section 4.2), we haveP (V i ) ≡ # max(J ) (V i ) > (td) -# ⊥ (V i ).PI n ˚1897

If both t 0 and t 1 are equal to +∞, no process decides and the claim is trivially true.PI n ˚1897

This result complements another k-set agreement minimality result[START_REF] Herlihy | Tight Bounds for k-Set Agreement with Limited Scope Accuracy Failure Detectors[END_REF] which shows that, among the family (Sx) 1≤x≤t+1 of perpetual failure detectors (introduced in[START_REF] Mostefaoui | k-Set Agreement with Limited Accuracy Failure Detectors[END_REF][START_REF] Yang | Structured Derivations of Consensus Algorithms for Failure Detectors[END_REF]), Sx is the weakest to solve the k-set agreement problem for k > tx + 1.PI n ˚1897

PI n ˚1897

Acknowledgments

We would like to thank Rachid Guerraoui for interesting questions during PODC 2005 that helped us refine our approach, and Matthieu Roy and Xavier Defago for discussions on the set agreement problem and the implementation of failure detectors. Finally, we want to thank the anonymous referees for their very careful reading and valuable comments.

This work will work has been supported by grants from LAFMI (Franco-Mexican Lab in Computer Science), DGAPA-UNAM and the European Network of Excellence ReSIST. Centre National de la Recherche Scientifique Institut National de Recherche en Informatique (UMR 6074)

A A 3P-based shared memory consensus protocol A.1 Description of the Protocol

The protocol uses the following shared registers.

• D [1..n] is an array of write-once single-writer multi-reader atomic registers. D[i], initialized to ⊥, can be read by all the processes but written only by p i ; p i sets D[i] to a non-⊥ value v to indicate that the value v can be decided.

• PART [1..n] is an array of boolean write-once single-writer multi-reader atomic registers, initialized to [false, . . . , false].

The process p i sets PART [i] to true to indicate that it participates in the consensus. • AC [1..) is an unbounded array of adopt-commit-abort objects. Each adopt-commit-abort object is associated with a round.

PI n ˚1897

A. Mostefaoui & S. Rajsbaum & M. Raynal & C. Travers

The 3P-based consensus protocol is described in Figure 6 (this code is for a process p i , where v i is the value proposed by that process). First, p i sets its estimate of the decision value to v i , registers in the protocol, and sets its local round number r i to 0 (line 1). The design principle of the protocol relies on the combined use of an eventual common leader (as the Ω-based consensus protocols, e.g., [START_REF] Chandra | The Weakest Failure Detector for Solving Consensus[END_REF][START_REF] Guerraoui | The Information Structure of Indulgent Consensus[END_REF][START_REF] Mostefaoui | Randomized k-Set Agreement[END_REF]) and adopt-commit-abort objects.

A process p i executes a sequence of rounds until it decides. Before starting a new round, a process first looks if a value has been decided and decides it if any (lines 3-4). Otherwise, p i considers as the current leader the process p with the smallest identity, among the processes perceived as participating and not currently suspected ( = min{j | PART i [j ] ∧ j / ∈ suspected i } at line 5). If i = (line 6) p i considers it is the leader and starts the next round (line 7), during which it invokes the adopt-commit-abort object associated with that round, namely AC [r]. If this object returns commit, p i decides the value it has been provided with by AC [r]. If AC [r] returns adopt or abort, p i enters again the repeat loop. Let us notice that, if AC [r] returns commit or adopt, the local estimate value est i has possibly been modified. This is a crucial point for the consensus agreement property.

end if [START_REF] Chaudhuri | Tight Bounds for k-Set Agreement[END_REF] end if [START_REF] Chu | Reducing Ω to 3[END_REF] end repeat Proof Let CP be the set of correct processes that participate in the protocol. Let us assume by contradiction that no process of CP decides (it is easy to see that if one of them decides, the predicate (∃j : D[j] = ⊥) is satisfied, and consequently the other correct processes also decide).

Due to the failure model (crash), and the properties of the failure detector class 3P, there is a time τ after which (1) only the processes of CP execute the protocol, and (2) their sets suspected i contains all the crash processes and only them.

After τ , the array PART [1.

.n] is no longer modified, and the sets suspected i are all equal. It follows that there is a single process p such that, for any process p i ∈ CP , we have = min{j | PART [j ] ∧ j / ∈ suspected i }. Consequently, there is a finite round r such that only p invokes AC[r].adopt commit(est i ) (lines 6-7). Due to the properties of the AC[r] commit-object, p obtains (commit, v), and consequently deposits v in D[ ] and decides. A contradiction with the assumption which proves the lemma.

2 Lemma 2

Lemma 3 If a correct process p i invokes cons alg(), it decides a value.

Proof It follows from the text of the protocol (line 8 -"direct" decision-, and line 3 -"indirect" decision-) that, to be decided, a value v has first to be returned by an adopt-commit-abort object together with the tag commit. So, observing that the processes that invoke the adopt-commit-abort objects, do it in the same sequential order, let us define r as the smallest round number such that AC[r] returns (commit, v) to a process p i . We show that only v can be decided.

Let us first notice that, as p i obtains (commit, v) from AC[r], any other process p j can obtain only (commit, v) or (adopt, v) from AC[r] (agreement property of AC[r]). If p j obtains (commit, v), it can decide only v. If p j obtains (adopt, v), its local estimate est j is set to v (line 7).

Irisa

The Combined Power of Conditions and Information on Failures to Solve Asynchronous Set Agreement

27

It follows that all the processes that execute the round r + 1 are such that their estimates values are equal to v, which means that only v can be proposed to the object AC[r + 1]. It then follows from the obligation property of the adopt-commit-abort object AC[r + 1] that the only pair that can be returned by that object is (commit, v). 2 Lemma 3 Theorem 11 The protocol described in Figure 6 solves the consensus problem for all the participating processes.

Proof The proof of the termination and agreement properties of the consensus problem follows from Lemma 2 and Lemma 3, respectively. The proof of the validity property (the decided value is a proposed value) follows directly from the validity property of the adopt-commit-abort objects (they do not create new values).

2 T heorem 11

B An adopt-commit-abort object implementation

As announced in the paper, this appendix describes an implementation of an adopt-commit-abort protocol. The implementation described in Figure 7 is a merge of the one described in [START_REF] Yang | Structured Derivations of Consensus Algorithms for Failure Detectors[END_REF] (designed for an asynchronous shared memory system) and the one described in [START_REF] Mostéfaoui | Solving Consensus Using Chandra and Toueg's Unreliable Failure Detectors: a General Quorum-Based Approach[END_REF] designed for an asynchronous message-passing system). It uses two arrays of one-writer multi-reader atomic registers denoted PHASE 1[1.

.n] and PHASE 2[1.

.n], both initialized to [⊥, . . . , ⊥].

Then, an entry of such an array contains a pair or remains equal to ⊥.

(single, v) / ∈ set2 i then return (abort, v i ) (10) end case. The behavior of a process p i can be decomposed into three phases.

• Phase 1 (lines 1-2). A process p i first deposits its input value v i in PHASE 1[i] to make public the fact that v i has been proposed to the adopt-commit-abort object. Then, it reads (asynchronously) the whole array PHASE 1[1.

.n] to know if other values have been proposed. The local set set1 i is used to keep these values.

• Phase 2 (lines 3-6 • Phase 3 (lines 7-10). Finally, p i computes the final value it will return as the result of its invocation.

-If set2 i contains only the pair (single, v), p i returns (commit, v): it "commits" the value v.

-If set2 i contains several pairs, and one of them is (single, v), then p i "adopts" that value v by returning (adopt, v). -Finally, when set2 i does not contain (single, v), p i has seen no value to be adopted or committed. It consequently "aborts", returning the value v i it has initially proposed.

The proof of the termination, validity and obligation properties of the adopt-commit-abort object are trivial. A proof of the agreement property for the shared memory model can be found in [START_REF] Yang | Structured Derivations of Consensus Algorithms for Failure Detectors[END_REF]. A proof for a message-passing model can be found in [START_REF] Mostéfaoui | Solving Consensus Using Chandra and Toueg's Unreliable Failure Detectors: a General Quorum-Based Approach[END_REF] (that proof assumes a majority of correct processes). That proof consists in showing that, for any pair of processes p i and p j that execute line 6, we have set2 i = {(single, v)} ⇒ (single, v) ∈ set2 j (i.e., line 7 and line 9 are "mutually exclusive"). Irisa