Zohir Bouzid
email: zohir.bouzid@labri.fr

Corentin

Anonymity-Preserving Failure Detectors

Keywords: failure detectors, shared memory, anonymous computing

The paper investigates the consensus problem in anonymous, failures prone and asynchronous shared memory systems. It introduces a new class of failure detectors, called anonymitypreserving failures detectors suited to anonymous systems. As its name indicates, a failure detector in this class cannot be relied upon to break anonymity. For example, the anonymous perfect detector AP , which gives at each process an estimation of the number of processes that have failed belongs to this class.

The paper then determines the weakest failure detector among this class for consensus. This failure detector, called C, may be seen as a loose failures counter: (1) after a failure occurs, the counter is eventually incremented, and (2) when at least two processes do not fail, it eventually stabilizes. Finally, the paper also introduces failure detector C k , a simple generalization of C and shows that it can be used to solve k-set-agreement, a generalization of consensus in which up to k distinct values may be decided.

Introduction

Anonymous computing The vast majority of the literature about distributed computing assumes that each process is provided with an unique identifier. We consider in this work anonymous computing in which processes have no identifiers and are programmed identically. Besides intellectual curiosity, anonymous computing might be of practical interest [START_REF] Guerraoui | Anonymous and fault-tolerant shared-memory computing[END_REF]. For example, for privacy reasons, a set of distributed processes may be willing to compute some function on their inputs without revealing their identity. Or the distributed computation might be performed on top of an anonymous communication system [START_REF] Danezis | A survey of anonymous communication channels[END_REF], and thus using ids is forbidden.

Specifically, we consider the totally anonymous shared memory model of distributed computing. The shared memory consists only in basic shared objects, namely read/write registers. We assume that there is no way to uniquely assign registers to the processes as this would provide a way to differentiate the processes. Previous works [START_REF] Attiya | Computing in totally anonymous asynchronous shared memory systems[END_REF][START_REF] Guerraoui | Anonymous and fault-tolerant shared-memory computing[END_REF] have shown that the lack of unique identifiers limits the computational power of the shared memory model. Similarly, starting from the pioneering work of Angluin [START_REF] Angluin | Local and global properties in networks of processors (extended abstract)[END_REF], the computational power of anonymous message passing system in the failurefree case has been investigated for particular or general graph topologies, e.g., [START_REF] Attiya | Computing on an anonymous ring[END_REF][START_REF] Attiya | Better computing on the anonymous ring[END_REF][START_REF] Yamashita | Computing on anonymous networks: Part i-characterizing the solvable cases[END_REF][START_REF] Yamashita | Computing on anonymous networks: Part ii-decision and membership problems[END_REF].

Consensus, failure and asynchrony Besides the unavailability of unique identifiers, a major difficulty is coping with failures and asynchrony. Many simple distributed tasks cannot be solved in asynchronous and failures-prone distributed system. A prominent example is consensus, which is a cornerstone task in fault-tolerant distributed computing. Informally, the processes, each starting with a private value, are required to agree on one value chosen among their initial values. In systems with identities, it is well known that asynchronous fault tolerant consensus is impossible as soon as at least one process may fail by crashing [START_REF] Michael | Impossibility of distributed consensus with one faulty process[END_REF][START_REF] Mc Loui | Memory requirements for agreement among unreliable asynchronous processes[END_REF]. This impossibility trivially extends to anonymous systems.

Failure detectors Failure detectors [START_REF] Deepak | Unreliable failure detectors for reliable distributed systems[END_REF] are a popular approach to circumvent impossibilities stemming from asynchrony and failures. A failure detector is a distributed device that provides each processes with perhaps unreliable information about which other processes have crashed. In non-anonymous systems, several classes of failure detectors have been defined [START_REF] Felix | The failure detector abstraction[END_REF]. In many cases, their specification involves processes identities. For example, the perfect detector P provides each process with a list of the identities of some of the processes that have crashed. The list is eventually complete in the sense that it eventually includes the identity of each crashed process. The leader failure detector Ω eventually outputs the same identity at every process, which is the identity of a non-faulty process.

Given a distributed task T , a natural question is to determine the weakest failure detector for T , that is a failure detector D which is both sufficient to solve the task -there is an asynchronous, fault tolerant protocol that uses D to solve T -and necessary, in the sense that any failure detector D that can be used to solve T can also be used to emulate D. For example, is well-known that Ω is the weakest failure detector for consensus [START_REF] Deepak | The weakest failure detector for solving consensus[END_REF] in shared memory systems when processes are provided with unique identifiers.

Failures detector in anonymous systems Bonnet and Raynal initiated the study of failure detectors in anonymous message passing systems [START_REF] Bonnet | Anonymous asynchronous systems: the case of failure detectors[END_REF]. In particular, they identify identity-free counterpart of classical failure detectors including Ω and P . AΩ, an identity-free failure detector 1. It first defines (Section 3) the class of anonymity-preserving failure detectors and a new failure detector denoted C. Failure detector C might be seen as a shared loose failure counter. It guarantees that after each new failure the counter is eventually incremented, and in case two or more processes are non-faulty, the counter eventually stabilizes. Let us notice that even if several failures occur, the counter might be incremented only once. C is thus far from providing an accurate tally of failures.

2. The paper shows that C is powerful enough to solve consensus while tolerating any number of failures (Section 4). The algorithm is uniform, in the sense that it does not require the total number of processes n to be known. Striving to not reinvent the wheel, the protocol relies on standard shared memory constructs, namely adopt-commit [START_REF] Gafni | Round-by-round fault detectors: Unifying synchrony and asynchrony (extended abstract)[END_REF] and safe-agreement [START_REF] Borowsky | The BG distributed simulation algorithm[END_REF] objects.

3. It is then shown that C can be emulated using any anonymity-preserving failure detector D powerful enough to solve consensus (Section 5). The extraction algorithm reuses in part the techniques developed by Zielinski [START_REF] Zielinski | Anti-Omega: the weakest failure detector for set agreement[END_REF] for proving statement of this type in the shared memory model with identities. Interestingly, the proof does not rely on the specifics of the impossibility of fault-tolerant consensus but rather on the fact this task cannot be solved non-anonymously wait-free among two processes.

4. Finally, it focuses on k-set agreement [START_REF] Chaudhuri | More choices allow more faults: Set consensus problems in totally asynchronous systems[END_REF], a task that generalizes consensus by allowing up to k distinct values to be decided. A generalization denoted C k of failure detector C is introduced and a C k -based algorithm is presented (Section 6).

Anonymous, asynchronous crash-prone shared memory model We consider an asynchronous and crash-prone shared-memory system consisting in n ≥ 2 processes. Each process p has a unique index i in the range [1, n]. The indexes are used only for modeling purpose. The process with index i is denoted by p i . Processes are anonymous in the sense that they run the same code and are not aware of their index. Hence, in an execution, processes may behave differently only as a result of the underlying schedule or because their initial states differ. Processes communicate via a shared memory that consists in an unbounded number of multi-writer/multi-reader atomic registers. Processes are asynchronous, e.g., each process runs at its own speed, independently of the other processes. Processes may fail by crashing. A process that crashes stops executing its code and never recovers.

Failure detector For modeling failure detectors, we assume the existence of a global clock whose values are the non-negative integers. The clock is not accessible to the processes. Let Π = {p 1 , . . . , p n } be the set of processes. A process may fail by crashing, i.e., prematurely stops executing its code. A process that has crashed never recover. A failure pattern is a function F : N → 2 Π that specifies the set of processes that have failed at each time τ ∈ N. Let faulty(F) denote the set of processes that fail in F, i.e., faulty(F) = τ ≥0 F(τ ). The set of processes that do not fail is correct(F) = Π \ faulty(F). When the failure pattern is clear from the context, we say that a process p i is correct is p i ∈ correct(F) and faulty otherwise. An environment is a set of failure patterns. Unless specified otherwise, we assume the wait-free environment that contains every failure pattern in which at least one process is correct. A failure detector [START_REF] Deepak | Unreliable failure detectors for reliable distributed systems[END_REF] provides at each process some information on the underlying failure pattern. Each process can query its local failure detector module. Such a query returns a value in some (possibly infinite) range R. The outputs of the failure detector during an execution is described by a failure detector history. A failure detector history is a function H : Π × N → R that maps each pair (process index, time) to a value in the failure detector range R. The value returned by the failure detector at process p i at time τ is H(p i , τ ). A failure detector D with range R associates a non-empty set of histories D(F) to each failure pattern F.

Protocol and executions A distributed algorithm or a protocol consists in n copies of a local algorithm A, one per process. An execution or a run is a finite or infinite sequence of steps. In a step, a process (1) queries the failure detector or (2) reads or (3) writes a shared register and performs some local computation. A configuration describes the local state of each process and the state of each shared register.

An execution or a run of a protocol A using failure detector D in environment E is a tuple e = (F, H, I, S, T ) where F is a failure pattern in E, H a failure detector history in D(F), I is an initial configuration of A, S a sequence of steps of A and T a non-decreasing sequence of times. S is called a schedule and the ith step S[i] of S takes place at time T [i]. A tuple e = (F, H, I, S, T ) represents an execution of A if and only if (1) S and T are both finite in which case they have the same length, or are both infinite, (2) no processes take a step after it has crashed, (3) if step S[i] is a failure detector query by process p j that returns d, then d = H(p j , T [i]), i.e., the failure detector queries return values that are consistent with the history H, (4) the steps taken in S are consistent with A, (5) the timings of read and write steps, together with the values written or read in these steps are consistent with the atomic semantic of the shared registers and, (6) if S is infinite, every correct process takes infinitely many steps in S. Condition (5) can be reformulated as follows [START_REF] Gafni | On set consensus numbers[END_REF]:

For any i, j, if step S[i] causally precedes step S[j], T [i] < T [j]
. Formalizing these conditions is not difficult but tedious. We refer to prior work [START_REF] Delporte-Gallet | Wait-freedom with advice[END_REF][START_REF] Gafni | On set consensus numbers[END_REF][START_REF] Zielinski | Anti-Omega: the weakest failure detector for set agreement[END_REF] on failure detector in the shared memory model for a formal treatment.

Consensus and k-set agreement Consensus and k-set agreement are examples of distributed tasks. In the consensus task, each process starts with a value taken from some set V and is required to decide a value subject to the following requirements: (Validity) any decided value is the initial value of some process, (Agreement) no two distinct values are decided and (Termination) every non-faulty process decides. In binary consensus, the set of possible initial values is restricted to V = {0, 1}. The k-set agreement task has the same validity and termination requirement of consensus but relaxes agreement as follows: (k-agreement) no more than k distinct values are decided.

Let A be a protocol that uses a failure detector D. We assume that each process p is equipped with two local variables, one, read-only in p and the other, write-once out p whose purpose is to store the input and decision values, respectively, of p. Let T be the consensus or k-set agreement tasks. We say that protocol A solves T using failure detector D in environment E if in any infinite execution e = (F, H, I, S, T ) of A where F ∈ E and for every process p, in p is initialized to some value v ∈ V, every process q ∈ correct(F) eventually decides, i.e. writes a value = ⊥ to out p and the values written satisfy the validity and (k)-agreement requirements of T .

Comparing failure detectors Let D and D be two failure detectors. D is said to be as least as weak as D in environment E, denoted D ≤ E D if there is a protocol T D →D that emulates D using D . Specifically, such a protocol maintains at each process p a local variable out-D p whose successive values are in the range of D. T D →D emulates D if for every failure pattern F ∈ E, in any execution with failure pattern F, there exists an history H ∈ D(F) such that for every process p and every time τ , H(p, τ ) = out-D τ p where out-D τ p denotes the value of the variable out-D at p at time τ . D and D are said to be equivalent in environment

E if D ≤ E D and D ≤ E D .
Finally, a failure detector D is said to be a weakest failure detector for a task T in environment E if [START_REF] Afek | The ksimultaneous consensus problem[END_REF] there is a protocol that solves T using D in E and (2) for every failure detector D that can be used to solve T , D ≤ E D . For example, Ω is a weakest failure detector for consensus [START_REF] Deepak | The weakest failure detector for solving consensus[END_REF] in asynchronous systems with identities.

Anonymity-preserving failure detectors

This section introduces the class of anonymity preserving failure detectors and defines the new failure detector C.

The class of anonymity-preserving failure detectors Intuitively, a failure detector is anonymity preserving if it cannot be relied upon to break symmetry among the processes. In the context of anonymous systems, a failure detector history H is anonymity-preserving if for every time τ and every processes indexes i, j, H(p i , τ ) = H(p j , τ ). That is, two queries at the same time by different processes return the same value. Hence, in such history, the value output by the failure detector only depends on the time at which the failure detector is queried, and does not depend on the querying process. An anonymity preserving history is thus a function H : N → R that maps time to values in the failure detector range.

A failure detector is anonymity preserving if for every failure pattern F, for every p i ∈ Π and every history H ∈ D(F), the anonymity-preserving history H :

∀p j ∈ Π, ∀τ, H (p j , τ ) = H(p i , τ )
also belongs to D(F). Intuitively, any sequence of values output by the failure detector at process p i may have been returned at every other process. That is, if d = d 1 , d 2 , . . . is a legal sequence of output for process p i for some failure pattern F, then d is also a valid sequence at any process p j = p i , for the same failure pattern F.

For instance, the failure detector AΩ [START_REF] Bonnet | Anonymous asynchronous systems: the case of failure detectors[END_REF] eventually distinguish a unique correct process. It provides to each process a single bit whose value eventually is 0 except for one correct process. More precisely, the range of AΩ is {0, 1} and, for every failure pattern F, the history H : Π × N → {0, 1} belongs to AΩ(F) if and only if:

Eventual leadership. there exists a time τ and a process p i ∈ correct(F) such that for every τ ≥ τ and every process p j , H(p j , τ ) = 1 ⇐⇒ j = i.

Clearly, AΩ is not an anonymity-preserving failure detector. In every legal history, there is a time after which distinct values are output at least two processes. An example of an anonymity-preserving failure detector is an identity-free variant [START_REF] Mostéfaoui | The combined power of conditions and information on failures to solve asynchronous set agreement[END_REF] of the perfect failure detector, denoted AP in [START_REF] Bonnet | Anonymous asynchronous systems: the case of failure detectors[END_REF]. The range of AP is N and, for any failure pattern F the history H : Π × N → N belongs to AP (F) if and only if:

Accuracy. For every time τ and every process p i , H(p i , τ ) ≤ |F(τ )| Completeness. There exists a time τ such that for all τ ≥ τ ,

H(p i , τ ) = |F(τ )|
AP is an anonymity-preserving failure detector. If for failure pattern F d = f 1 , f 2 , . . . is a valid sequence of outputs for process p i , so it is for any process p j = p i .

Failure detector C Failure detector C is somewhat related to the signaling failure detector FS [START_REF] Guerraoui | The weakest failure detectors to solve quittable consensus and nonblocking atomic commit[END_REF]. The range of failure detector FS is {green,red }. While no failures occur, the output of FS is green. Once a failure occurs, and only if it does, the failure detector must eventually output red at every correct process.

Failure detector C might be seen as an unreliable variant of FS. The range of failure detector C is the integers. At each process, the sequence of integers output by C is non-decreasing, and after each new failure, the output of the failure detector is eventually increased. However, when at least two processes are correct in the underlying failure pattern, C output eventually stabilizes. That is, after some time, every query to C by process p i returns the same value, for each process p i . More formally, for every failure pattern F, history H : Π × N → N belongs to C(F) if and only if:

1. Monotonicity. For every process p i , for every times τ ≤ τ , H(p i , τ ) ≤ H(p i , τ ); 2. Signaling For every times τ, τ : τ < τ , for every processes

p i , p j , if |F(τ )| < |F(τ )|, there exists a time τ , τ ≤ τ such that H(p i , τ ) < H(p j , τ ); 3. Convergence. If |correct(F)| > 1,
for every process p i , there exists a time τ such that for every τ τ ≤ τ , H(p i , τ ) = H(p i , τ ).

A C-based consensus protocol

This section presents a consensus protocol based on failure detector C. To simplify the presentation, we concentrate on binary consensus in which the set of possible inputs is {0, 1}. Multivalued consensus can be solved from binary consensus by successively agreeing on the bits of one of the proposed value. The protocol is depicted in Figure 1. Besides registers, it relies on standard shared memory constructs, namely adopt-commit [START_REF] Gafni | Round-by-round fault detectors: Unifying synchrony and asynchrony (extended abstract)[END_REF] and safe agreement [START_REF] Borowsky | Generalized FLP impossibility result for t-resilient asynchronous computations[END_REF][START_REF] Borowsky | The BG distributed simulation algorithm[END_REF] objects, that we describe next.

Base objects An adopt-commit object supports a single operation denoted propose(v) where v is a value from some finite set V. Such an operation returns a couple (b, u) where b is either adopt or commit and u is a value in V, subject to the following requirements [START_REF] Gafni | Round-by-round fault detectors: Unifying synchrony and asynchrony (extended abstract)[END_REF][START_REF] Mostéfaoui | The combined power of conditions and information on failures to solve asynchronous set agreement[END_REF][START_REF] Aspnes | Tight bounds for adopt-commit objects[END_REF]:

1. Validity. If an operation returns (d, v) then v is the input of a propose() operation.
2. Agreement. If an operation returns (commit, v) then each output is either (adopt, v) or (commit, v).

3.

Convergence. If the input of every operation is v, then every output is (commit, v).

Termination. Each operation by a non-faulty process produces an output.

A shared-memory implementation of an adopt-commit object that tolerates an arbitrary number of crash-failures can be found in [START_REF] Aspnes | Tight bounds for adopt-commit objects[END_REF]. The implementation ([4], Algorithm 2) uses two multiwriter/multi-reader registers and a conflict-detector, which in turn can be implemented in a wait-free manner using only fact -1 (|V|) multi-writer/multi-reader registers ([4], Algorithm 3). Algorithms 2 and 3 do not use processes identities, and are thus suitable for the anonymous shared-memory model.

The safe agreement object, originally introduced by Borowsky and Gafni [START_REF] Borowsky | Generalized FLP impossibility result for t-resilient asynchronous computations[END_REF] allows the processes to propose values and to agree on a single value. It is at the heart of the BG-simulations [START_REF] Borowsky | Generalized FLP impossibility result for t-resilient asynchronous computations[END_REF][START_REF] Gafni | The extended bg-simulation and the characterization of t-resiliency[END_REF] in which it is used by simulators to agree on each step of the simulated processes. Different specifications of a safe agreement object can be found in the literature, e.g., [START_REF] Attiya | Adapting to point contention with long-lived safe agreement[END_REF][START_REF] Borowsky | The BG distributed simulation algorithm[END_REF][START_REF] Imbs | Visiting gafni's reduction land: From the BG simulation to the extended BG simulation[END_REF]. Our specification below closely follows [START_REF] Attiya | Adapting to point contention with long-lived safe agreement[END_REF].

A safe agreement object supports two operations propose(v) where v is a value in {0, 1} 1 and read(). Both operations return either a value u ∈ {0, 1} or ⊥. Each process can invoke propose() at most once, while read() can be invoked arbitrarily many times. An execution is well-formed if (1) each process calls propose() at most once and, (2) no processes start a read() or propose() operation before its previous operation (if any) has returned. It is required that in any well-formed execution, the following properties are satisfied:

1. Validity. If an operation returns a value v = ⊥, v is the input of a propose() operation. 2. Agreement. If values v, v ∈ {0, 1} are returned by some operation, v = v .

Termination. Every operation performed by a non-faulty process terminates.

We say that a propose() operation is successful if it returns a value = ⊥.

Consistent reads. Any read() operation that terminates and starts after a successful propose()

operation has completed returns a non-⊥ value.

5. Non-triviality. Not every propose() operations return ⊥.

Observe that the non-triviality property is satisfied in executions in which a process fails while performing a propose() operation. In the case in which no processes fail while performing propose(), it follows from the termination and non-triviality properties that at least one propose() operation is successful. Nevertheless, it is not guaranteed that every propose() operation is successful. However, the consistent reads property implies that if, after its propose() operation has returned, a process keeps reading the object, it eventually gets back a non-⊥ value.

When processes have unique identity, safe agreement objects can be implemented with registers, e.g., [START_REF] Borowsky | Generalized FLP impossibility result for t-resilient asynchronous computations[END_REF]. In anonymous systems, a safe agreement object implementation can be obtained by slightly modifying an anonymous binary consensus protocol by Attiya, Gorbach and Moran [START_REF] Attiya | Computing in totally anonymous asynchronous shared memory systems[END_REF] designed for the asynchronous shared memory model with no failures. See appendix A for more details.

Algorithm 1 C-based binary consensus protocol.

1: init SA[1, . . .]
Array of safe agreement objects

2:
AC[1, . . .] Array of adopt-commit objects

3: D ← ⊥ Decision register, initially ⊥ 4: function propose(v) v ∈ {0, 1} 5:
est ← v; start tasks T1, T2; 6: task T1: end if 14:

(b, u) ← AC[r].propose(aux) b ∈ {adopt, commit}, u ∈ {0, 1, ⊥} 15: case b = commit ∧ u ∈ {0, 1} then D ← u; return 16: b = adopt ∧ u ∈ {0, 1} then est ← u 17: default then nop u = ⊥ 18:
end case

19:

end for 20: task T2:

21: repeat u ← D until u = ⊥ end repeat 22:
stop task T1; return u Description of the protocol Algorithm. 1 consists in two tasks denoted T1 and T2, launched in parallel at each process p (line 5). In task T2, process p keeps reading a shared register D, whose initial value is ⊥, until it sees some non-⊥ value u. u is then decided by p (line 22).

In task T1, processes proceed in asynchronous rounds aiming at writing a single non-⊥ value to D. An adopt-commit object and a safe agreement object denoted respectively AC[r] and SA[r] are associated with each round r. Following a standard design pattern, e.g., [START_REF] Aspnes | A modular approach to shared-memory consensus, with applications to the probabilistic-write model[END_REF][START_REF] Gafni | The extended bg-simulation and the characterization of t-resiliency[END_REF], the processes that enter round r first try to reach agreement by accessing the safe agreement object SA[r] (line 9) and then check whether agreement has been achieved using the adopt-commit object AC[r] (line 14).

In more details, each process p maintains an estimate est that contains the value it currently favors. In round r, process p proposes its estimate to SA[r] (line 9) and, if its operation is unsuccessful (line 10), enters a loop in which it repeatedly reads the object (line 11). If no processes that enter round r fail, at least one of the invocations of propose() on SA[r] is successful (non-triviality and termination properties of safe agreement) and thus by keeping reading the object, a process eventually obtains a non-⊥ value (consistent reads property of safe agreement). Hence, in the case in which no processes entering round r fail, every process that enters that round eventually obtains a non-⊥ value, either because its propose() operation is successful, or as a result of a read() operation. Note that this value is the same for every process (agreement property of safe agreement).

However, some of the processes that enter round r may fail. In this case, each propose() operation may be unsuccessful, and every read() operation may return ⊥. We rely on failure detector C to ensure progress as follows:

• A process is allowed to enter a round r only if its local failure detector module output is larger than or equal to r (line 8);

• A process exits the loop in which it is trying to obtain a non-⊥ value from SA[r] by performing read() operation whenever its local failure detector output is strictly larger than d c (line 12).

This simple mechanism prevents processes from getting stuck in any round r in which a failure occurs. Indeed, a process p failing in round r must have obtained from C a value d c ≥ r (line 7). Then, following the crash of p, due to the signaling property of C, C eventually outputs at every non-faulty processes values strictly larger than d C , allowing these processes to exit the loop in which the safe agreement object SA[r] is read (lines 11-12).

To reconcile processes that have obtained a non-⊥ value form SA[r] and those to which C has signaled a failure, we use the adopt-commit object AC[r] (line 14). Each process p keeps in its local variable aux the result of its operations (at lines 9 and 11) on SA[r], e.g., ⊥ or some value v ∈ {0, 1}. In the second part of round r, process p proposes the value stored in aux to AC[r] (line 14). If it gets back (adopt, u), where u = ⊥ it changes its estimate to u (line 16). A process that receives (commit, u) can thus safely write u to the decision register D, as it follows from the agreement of adopt-commit that every propose() operation returns (commit, u) or (adopt, u). Hence, every process either writes u to D or changes its estimate to u, thus preventing any value u = u to be written to D in subsequent rounds. Finally, if a process p receives ( * , ⊥), then no process writes to D in the current round r, and p leaves its estimate unchanged (line 17).

As for termination, a process decides as soon as it reads a non-⊥ value from D (task T2). Let us observe that this happens if there is a round r in which (1) enters only one process, and this process is correct or (2) enter only correct processes, and at each of these processes, the largest output of C is r. Clearly, if only one process p enters round r, its propose() operation on SA[r] returns a non-⊥ value u (non-triviality property of safe agreement). u is then the only value proposed to AC[r]. p thus receives (commit, u) from AC[r] (convergence property of adopt-commit) and then writes u to D. Condition (1) is satisfied in executions in which there is only one correct process.

For the second condition, if only correct process enters round r, at least one of the propose() operation on SA[r] is successful. Moreover, no process can exit the reading loop (lines 11-12) without having obtained a non-⊥ value from SA[r], as C never outputs a value larger than r to those processes. Since every non-⊥ value returned by operations on SA[r] are the same, only one value is proposed to AC[r], from which we conclude that only (commit, v), where v = ⊥, is returned by each propose() operation performed on AC[r] (convergence property of AC[r].). Hence a value is written to D in round r. Condition (2) is met in every execution in which there is at least two correct processes, since in that case the output of C eventually stabilizes at every correct process, and the stabilization value is larger than every value output at faulty processes.

Proof of the protocol We consider an arbitrary execution e of the protocol. We assume that every correct process invokes propose() at line 4. Let F be the failure pattern, and H ∈ C(F) the failure detector history in e. Consensus agreement and validity follow from the agreement and validity properties of the adopt-commit and the safe agreement objects (see the proof of Theorem 4.3). The proof of termination relies on the following Lemma, which stems from the signaling property of the underlying failure detector C. Lemma 4.1. Let τ c be the time at which the last crash occurs in e (i.e., F(τ ) = F(τ c ), for every τ c < τ ). There exists T ∈ N such that: (i) for every faulty process p, for every time τ ≤ τ c , H(p, τ c ) ≤ T and, (ii) there exists a time τ T such that for every correct p, for every time τ, τ T ≤ τ, T < H(p, τ ).

In other words, there is value T such that each query to C by a faulty processes returns a value smaller than T while the queries by the correct processes eventually return values strictly greater than T .

Proof. Let T = max{H(p, τ ) : p ∈ faulty(F) and τ < τ c }. Item (i) is an immediate consequence of the definition of T . By the definition of T , there exists a faulty process q and a time τ 1 < τ c at which the output of C at q is T , i.e., H(q, τ 1 ) = T . Let p be a correct process. As for every time τ, τ 1 < τ c ≤ τ , F(τ 1 ) < F(τ ), there exists a time τ p , τ 1 < τ p such that T = H(q, τ 1 ) < H(p, τ p ) (Signaling property of C). Let τ T = max{τ p : p is correct}. By the monotonicity property of C, for every time τ, τ T ≤ τ and every correct process p, T < H(p, τ p ) ≤ H(p, τ ), which proves item (ii).

We say that a process decides when it returns a value at line 22 in task T2. Lemma 4.2 (Termination). Every correct process decides.

Proof. Assume for contradiction that no correct processes decide. As a process decides as soon as it reads a non-⊥ value from the decision register D (task T2), no non-⊥ value is ever written to D. Hence no process exits task T1 by executing the return statement of line 15.

We say that a process enters round r is it exists the repeat loop (line 8) of round r. Note that this occurs when a query to C returns a value d, r ≤ d. A process is blocked in round r if it enters round r and never enters round r + 1.

Let p denote a correct process and let d be a value returned to p by a query to C. Observe that p enters round d. Indeed, for every round r < d, p is not blocked in round r. First, as the successive values returned by the queries to C form a non-decreasing sequence, the condition for entering round r is eventually satisfied at p (line 8). Second, in round r, as p does not fail, its calls to propose() on the safe agreement and adopt-commit objects SA[r] and AC[r] terminate. Finally, the repeat loop at lines 11-12 eventually ends since C eventually outputs a value greater than r at process p.

We consider two cases according to the number of correct processes in the execution.

• |correct(F)| = 1. Let p be the correct process of the execution. By Lemma 4.1 and the monotonicity property of C, there exists an integer T such that (1) after some time every query to C by p returns a value greater than T and (2) every query by a faulty process returns a value ≤ T . It follows that there exists a round r, T ≤ r such that no process but p enters round r (Faulty processes cannot enter round r since they do not obtain large enough values from C. On the contrary, p does enter round r as a query by p to C returns r.).

Therefore, p is the only process that calls propose() (on line 9) on the safe agreement object SA [r]. By the non-triviality property of safe agreement, it must get back a value v = ⊥ from that call, which it then proposes to the adopt-commit object AC[r] (line 14). This operation returns (commit, v) as p is the only process that accesses the object. It thus follows from the code that p writes v to D. This is a contradiction.

• |correct(F)| > 1. In this case, at each correct process p the output of C eventually stabilizes to a value denoted d p . Let R = max{d p : p ∈ correct(F)} and let P be the set of processes at which the failure detector output is eventually R. Therefore, every propose() operation on the adopt-commit object AC[R] has v as input.

Each such operation thus returns (commit, v), from which we conclude that v is written to the decision register D. This is a contradiction.

Theorem 4.3. Protocol 1 solves binary consensus using failure detector C.

Proof. Validity directly follows from the validity properties of safe agreement and adopt-commit object. Termination follows from Lemma 4.2. For agreement, we prove that all values written to the decision register D are the same. Let r be the first round in which a value is written to D. That is, a process writes to D after entering round r and before leaving that round. Let v be the value written by that process. By the code (line 15), p has previously called propose() on AC[r] and has received (commit, v) from that call. By adopt-commit agreement, every other propose() operation on AC[r] that terminates returns (adopt, v) or (commit, v). It thus follows that (1) every value written to D in round r is v and, (2) every process that does not return in round r (at line 15) sets its estimate est to v before leaving round r (line 16). Therefore, for any round r ≥ r, the estimate of any process entering round r is v, from which we conclude that no value = v can be written to D after round r.

C is necessary to solve consensus

Let X be an anonymity-preserving failure detector, and assume that there is a protocol A that solves consensus using X. We present (Algorithm 2) a protocol T X→C that emulates C using X in the wait-free environment.

Overview As in previous protocols that emulate weakest failure detectors [START_REF] Deepak | The weakest failure detector for solving consensus[END_REF][START_REF] Delporte-Gallet | Tight failure detection bounds on atomic object implementations[END_REF][START_REF] Gafni | On set consensus numbers[END_REF][START_REF] Zielinski | Anti-Omega: the weakest failure detector for set agreement[END_REF], in T X→C each process locally simulates many possible runs of algorithm A. According to the output of these runs, information on the failure pattern is inferred and the desired weakest failure detector emulated.

Let F denote the failure pattern underlying the execution of T X→C . In order to simulate valid runs of A, e.g., runs indistinguishable from reals runs of A, samples from the underlying failure detector X have to be collected. Those samples are then used in the simulation of each step in which a query to failure detector X occurs. Hence, each process p must collect samples from its failure detector module, but also from other processes. Precedence relationships between samples should also be maintained to order to simulate valid runs of A. For example, the simulation must avoid using a sample from some faulty process q if a sample taken after the failure of q has already been used. In systems with identities, this is usually achieved by maintaining a DAG, where each vertex v contains failure detector sample d and a process id, and for any successor v of v, the sample d associated with v has been taken after d. In the anonymous shared memory model, the lack of identifiers make tracking precedence relationships difficult and the standard technique [START_REF] Deepak | The weakest failure detector for solving consensus[END_REF] does not apply. However, in the case of anonymity-preserving failure detectors, the samples taken by each process p from its local failure detector module are sufficient to simulate runs of A, even with more than one participating process. This is because the sequence of samples obtained by p might have been also obtained by every other processes in some execution with the same failure pattern F.

In T X→C , each process p simulates executions of A in which at most two processes, denoted q 0 and q 1 , participate with input 0 and 1 respectively. On one hand, for such an execution e by adding clones of q 0 and q 1 one may construct an indistinguishable execution e in which the number of participating processes matches the number of correct processes in correct(F). It thus can be shown that execution e is indistinguishable from the point of view of q 0 and q 1 from some real execution of A with failure pattern F. On the other hand, there must exist an interleaving of the steps of q 0 and q 1 such that the corresponding emulated execution of A does not decide. Otherwise, algorithm A together with the sequence of failure detector samples collected by p can be used to solve binary consensus wait-free and without failure detector by two non-anonymous processes q 0 and q 1 , contradicting the impossibility of consensus.

Operationally, process p explores every possible two-processes schedules of A in a particular, corridor -based order, as in [START_REF] Gafni | On set consensus numbers[END_REF][START_REF] Zielinski | Anti-Omega: the weakest failure detector for set agreement[END_REF]. Whenever a decision occurs in the execution simulated by p, a shared counter is incremented, and the output of C at p is set to the new value of the counter. We prove (1) that following any (real) process failure, p eventually simulates an execution of A in which a decision occurs, and due to the order in which schedules are explored, (2) that eventually p keeps simulating one infinite execution in which no processes decide. The correctness of the emulation C then follows (1) and (2).

Algorithm A Let M EM denote the (not necessarily finite) array of registers used by A. Recall that in a step of A, a process performs a read() or write() operation on some register M EM [ ] or a query() operation, from which it gets back an output from the underlying failure detector X. It may then perform some local computation. Instead of simulating runs of A, we are going to simulate runs of a slightly modified version of A, called A , defined as follows. The purpose of the modification is to help tracking causality relations between steps of the algorithms.

In

v ← M EM [ ].read() in A is replaced in A by v, η ← M EM [ ].read(); η ← max(η, η + 1).
Finally, after each write(), read() or query() operation η is incremented (η ← η + 1). For each step s of the modified algorithm A , we define η(s) as the value of η immediately before it is incremented (e.g., immediately before η ← η + 1 is performed). Obviously, these modifications do not affect the correctness of A , i.e., A solves consensus using X.

Causality Let r be a run of A with two processes q 0 , q 1 , where the input of q i , i ∈ {0, 1} is i. Note that in these particular executions, although the processes are anonymous, we can assume that the values written are unique, as they can be tagged with the process input and a sequence number. For any two steps s, s in r, s causally precedes s , denoted s s if and only if :

1. s and s are performed by the same process in that order or, 2. in s a value v is written to some register M EM [ ], and in s v is read from M EM [ ] or, 3. there exists a steps s such that s s and s s .

The following Lemma follows from the management of the variables η in A .

Lemma 5.1. Let r be a run of A by two processes q 0 , q 1 with input 0 and 1 respectively. For every steps s, s of r, s s =⇒ η(s) < η(s ).

Proof. If s and s are two steps by the same process q i , occurring in that order, the lemma follows from the fact that η is incremented at the end of each step of q i . Suppose value v is written to some register in s and read in s . Then η(s ) = max(old, η(s) + 1) > η(s) where old is the value of η at the beginning of s and the lemma follows. Otherwise, there exists steps s 0 (= s), s 1 , . . . , s m (= s ) such that for every j, 0 ≤ j ≤ m -1, steps s j and s j+1 are performed by the same process in that order or a value written in s j is read in s j+1 . In that case, the lemma follows from an easy induction on m.

Collecting failure detector X samples In order to simulate a run r of A , each process p must be able to select appropriate outputs from the failure detector X for each query() steps in r.

Since failure detector X is anonymity-preserving, p does not need to know outputs of X at other processes p . Indeed, for any failure pattern F and any finite or infinite sequence x = x 1 , x 2 , . . . of outputs of X collected by p in a run with failure pattern F, there is a run with the same failure pattern in which every process see the same sequence x of outputs of X. Therefore, in order to provide failure detector values for the simulation of runs of A , p simply builds an ever growing sequence of failure detector outputs x[1], x [START_REF] Angluin | Local and global properties in networks of processors (extended abstract)[END_REF], . . . by repeatedly querying its local failure detector module.

Induced schedules of A Each process p simulates runs of A in which at most two processes, denoted q 0 and q 1 , take steps with initial values 0 and 1 respectively. We next describe how a binary sequence and a sequence of failure detector X outputs induce a schedule S of A , that is a sequence of steps of A . Let x denote a sequence of failure detector outputs, obtained from X at increasing times, and let λ denote a binary sequence. Intuitively, λ describes in which order processes take steps in S and x supplies failure detector outputs for simulating query(). A difficulty is to choose output in x for each query() step of S in such a way that there is a real execution of A indistinguishable to q 0 and q 1 from S.

Schedule S is defined inductively. Recall that a configuration c, in the context of a two processes schedule consists in a triplet (s 0 , s 1 , M EM ) where s i , i ∈ {0, 1} is the local state of q i and the array M EM contains the current value of each register used by A . In the initial configuration c 0 of S, c 0 .s i , i ∈ {0, 1} reflects the fact that the initial value of q i is i and c 0 .M EM is initialized as specified by A . The ith step of S is taken by process q λ[i] and is deduced from A applied to the local state of q λ[i] in configuration c i-1 . If this step is a read() or write() step, it is simulated by reading or writing a value to/from M EM . If the step is a query() operation, it is simulated by taking x[η λ [i] ] as its result, where η λ[i] is the value of the variable η at process q λ[i] in configuration c i-1 . Configuration c i is then derived from c i-1 in the obvious way.

The choice of output for each simulated query() preserves causality in the following sense: Let s and s be steps of S in which X is queried and assume that s s . Let j, j the indices in x of the values returned by these queries in the simulation. Then x[j] is obtained from X before x[j ], i.e., j < j , as one would expect. Indeed, let q i and q i be respectively the processes that perform s and s , and let η(s) and η(s ) be the value of η at process q i and q i in the configurations that immediately precede s and s , respectively. The results of the queries in s and s are x[η(s)] and x[η(s )]. By Lemma 5.1, as s s , η(s) < η(s ).

Indistinguishability of induced schedules from real runs Given a binary sequence λ and a sequence x of outputs of X, the schedule S λ,x induced by λ and x may not correspond to a real execution of A . More precisely, for the simulation of S to be meaningful, we need that there exists a real run r of A that is indistinguishable from S to q 0 and q 1 . The schedule in r may differ from S, but the successive states of q i must be the same in S and r, for each i ∈ {0, 1}. Next Lemma establishes the existence of r. Lemma 5.2. Let λ be a binary sequence. Let x denote a (finite or infinite) sequence of outputs of X and let S denote the schedule induced by λ and x. Assume that there exists a failure pattern F, a history H ∈ X(F) and an increasing sequence of times τ 1 < τ 2 < . . . such that for every i, x[i] = H(p, τ i ) for some process p. If for every i, |F(τ i )| ≤ n -2, there exists a run of A indistinguishable from S to q 0 and q 1 . Proof. Let r = (F, H, I, S , T ) where F and H as are in the Lemma statement, and I is the initial configuration in which process q i input is i, for each i ∈ {0, 1}. S is a schedule with exactly the same steps as S and T is a non-decreasing sequence of times, such that for every i, step S[i] occurs at time T [i]. To define S and T , we associate with each step s in S a time θ(s) as follows: Let prec(s) be the set of steps in S that causally precede s, i.e., prec(s) = {s ∈ S : s s}.

θ(s) = τ η(s) if s is a query() step max{θ(s ) : s ∈ prec(s)} + 1 otherwise.
S is the sequence of steps in S, order according to θ. If two steps s, s are such that θ(s) = θ(s ), they are performed by two distinct processes and we order the step performed by q 0 first. T is then the sequence θ(S [START_REF] Afek | The ksimultaneous consensus problem[END_REF]), θ(S [2]), . . . We next verify that r defines a run of A .

We check that for any two steps s 1 , s 2 , if s 1 s 2 , then θ(s 1 ) < θ(s 2 ). Suppose first that s 1 is a query step. If s 2 is also a query step, since s 1 s 2 , it follows from Lemma 5.1 that η(s 1 ) < η(s 2 ). Hence θ(s 1 ) = τ η(s 1 ) < τ η(s 2 ) = θ(s 2 ). If s 2 is a read or write step, since s 1 ∈ prec(s 2 ), θ(s 1 ) < θ(s 2 ). Suppose now that s 1 is read or write step. If s 2 is also read or write step, θ(s 1 ) < θ(s 2 ) since s 1 ∈ prec(s 2 ). Otherwise s 2 is a query. Observe that ≤ θ(s 1 ), where is the length of the longest causal chain of steps ending in s 1 . By the management of the η variables in A , = η(s 1 ). If = θ(s 1 ), as s 1 s 2 , η(s 1 ) < η(s 2 ) (Lemma 5.1) and thus, since η(s 2 ) ≤ τ η(s 2 ) , θ(s 1 ) < θ(s 2 ). Otherwise, there exists a query step s ∈ prec(s 1 ) such that θ(s 1 ) = τ η(s) + δ, where δ is the length of the causal chain from s to s 1 . Since s s 1 s 2 , η(s 2 ) = η(s) + δ where δ < δ . Hence, as 5) of a run is satisfied.

τ η(s) + δ ≤ τ η(s)+δ < τ η(s)+δ = θ(s 2 ), θ(s 1 ) < θ(s 2 ). Therefore, for any i, j, if S [i] causally precedes S [j] then T [i] < T [j]. Property (
Clearly S and T have the same length (property (1)). By assumption, at least two processes, say p and p do not fail in F. Algorithm A being anonymous, and failure detector X anonymity preserving, we can think of run r as a run in which p and p take the steps in lieu of q 0 and q 1 , respectively. Hence, no process takes a step in r after it has failed (property ( 2)). By definition, if s = S [i] is a query step, T [i] = τ η(s) and the value returned by the query is d = x[η(s)] = H(p, τ η(s) ) for some process p. Since X is an anonymity preserving, d is also a valid output at time τ η(s) for the process performing the query (property (3)). S and S contain the same set of steps. For each process q i , the steps of q i occur in the same order in S and S . Hence S and S are indistinguishable to q i . Finally, as the order of read/write operations on each register M EM [ ] is preserved in S , each read returns last value written. Hence property (4) of runs holds. Run r however may not be fair. A infinite run r = (F, H, I, S, T ) is fair if every process in correct(F) take infinitely many steps in r. Given an infinite binary sequence λ, let inf (λ) ⊆ {0, 1} the bits that appear infinitely many often in λ. Next Lemma expresses a sufficient condition for the existence of a fair run indistinguishable to q 0 and q 1 from the schedule induce by binary sequence and a sequence of failure detector outputs λ, x. Lemma 5.3. Let λ be an infinite binary sequence and x an infinite sequence of failure detector X outputs. Suppose that there exists a failure pattern F, a sequence of times τ 1 < τ 2 < . . . and an history H ∈ X(F) such that for every i ≥ 1, x[i] = H(p, τ ) for some process p.

If |correct(F)| ≥ 2 and inf(λ) = {0, 1} then the schedule S λ,x induced by λ, x is indistinguishable from the schedule in a fair run r of A.

In the induced schedule S λ,x , only two processes take step. However, more than two processes may be correct in the failure pattern F. We resolve this difficulty by adding clones of q 0 and q 1 . A clone [START_REF] Faith | On the space complexity of randomized synchronization[END_REF] of process q i is a process that has the same input and the same code as q i . p is scheduled in lock-step with q i : it reads and writes the same values as p, and each of its queries to X returns the same output as the queries by p. The latter is made possible by the fact that X is anonymity-preserving. The outputs of X at q i are also valid outputs at any other processes.

Proof. Let r = (F, H, I, S , T ) be the run indistinguishable to q 0 and q 1 , as defined in the proof of Lemma 5.2. If |correct(F)| > 2, we construct fair run r by adding |correct(F)| -2 clones of q 0 to r. Each clone p has the same input as q 0 , writes and reads the same value as q 0 . The queries by p occur at the same times as the queries by q 0 and return the same values. Since X is an anonymity-preserving failure detector, there exists and history H ∈ X(F) such that for any time τ and any clone p, H (p, τ ) = H (q 0 , τ ) = H(q 0 , τ ). Steps by clones are not seen by neither q 0 nor q 1 . Thus r is indistinguishable from r to q 0 and q 1 . Clearly r is a fair run of A .

C emulation Algorithm 2 emulates failure detector C from any anonymity preserving failure detector X that can be used to solve consensus. It closely follows the emulation technique of Zielinski [START_REF] Zielinski | Anti-Omega: the weakest failure detector for set agreement[END_REF]. At each process p, the emulation consists in two tasks T and T that run in parallel. In task T , p collects outputs of X by querying its local failure detector module. The outputs are stored in the array x. In task T , p recursively simulates every possible schedule of A (lines 9-19). An infinite array A of registers is used to implement a weak shared counter. Each register A[i] initial value is ⊥. The counter is incremented by changing to the value of the register with the smallest index containing ⊥. The value of the counter is thus the largest index i of A such that A[i] = . Each time a process decides in a simulated schedule, the counter is incremented and the output of C is set to the counter new value (line 17).

Algorithm 2 T X→C , where X can be used to solve consensus. c 0 ← initial configuration: q i , i ∈ {0, 1} input is i, M EM is initialized as prescribed by A

5:

P 0 ← {q 0 , q 1 }; λ 0 ← ; out-C ← 0 6:

start tasks T and T' where task T' is explore(λ 0 , c 0 , P 0 ); let U be the set of processes still undecided in c 9:

for each P ⊆ P ∩ U in an order consistent with ⊆ do 10:

for each q i ∈ P do 11:

let step be the next step of q i in configuration c according to A simulate next step of q i 12:

case step = read() from th register then read c.M EM [ ] if q i has decided in c then let m ← min{ :

A[ ] = ⊥}; A[m] ← ; C-out ← m 18:
end if update (emulated) failure detector C output for i = 1, 2, . . . do x[i] ← X-query() end for

In the following, we consider an arbitrary run of algorithm 2. Let F denote the failure pattern of this run and H ∈ X(F) the failure detector history. We denote by f the total number of failures, i.e., f = |faulty(F)|. We first show that each correct process p simulates at least one schedule in which a decision occurs after the time of the last crash in F. (Lemma 5.4). Consequently, the output of C at p is incremented at least once after the last time a process fails, as required by the signaling property. The second Lemma (Lemma 5.5) states that if the underlying failure pattern includes at least two correct processes, the exploration procedure is eventually stuck simulating a non-deciding schedule. As the output of C is modified each time a simulated schedule decides, it follows that eventually the emulation of C eventually stabilizes at each process.

Lemma 5.4. Let τ c be the time of the last crash and let m = max{ : A[ ] = at a time τ c }. There exist a time τ following the time of the last crash such that for every correct process p, C-out τ p > m. Proof. Let p be a correct process. There exists an index i such that for every j, i < j, x[j] is a value output by X after the last crash occurs. Let i c denote the smallest such i.

explore(λ 0 , c 0 , P 0 ) recursively simulates schedules of A . Recall that simulating a query step consists in selecting an output in x. For any time τ , let i τ e be the largest index of x such that x[i τ e ] has been used to simulate a query step.

Claim: For any time τ , if i τ e ≤ i c , explore(λ 0 , c 0 , P 0 ) has not terminated by time τ . Proof of the Claim. Assume for contradiction that explore(λ 0 , c 0 , P 0 ) has terminated by time τ . Essentially, this implies that A together with x[1, . . . , i τ e ] can be used to solve consensus wait-free using only registers.

Assume for contradiction that explore(λ 0 , c 0 , P 0 ) terminates. Then for each possible schedule S of A for two processes q 0 , q 1 , there is a finite prefix S at the end of which each participating process has decided. This schedule is induced by some finite binary sequence λ and the sequence of outputs of X x = x[1..i τ e ], i.e., S = S λ ,x . There exists times τ 1 < . . . < τ i τ e such that for every i, 1 ≤ i ≤ i τ e , x [i] = x[i] = H(p, τ i ). As i τ e ≤ i c , τ i < τ c where τ c is the time of the last crash. Therefore, |F(τ i )| < f ≤ n -1, for every i, 1 ≤ i ≤ i τ e . It thus follows from Lemma 5.2 that S λ ,x is indistinguishable for its participating processes from a real run of A . Therefore, the decisions in S λ,x satisfy the validity and agreement requirements of consensus. Moreover, in the simulation of S λ ,x , the simulation of query() steps for q i depends only on the local state of q i in the simulation (line 23).

Therefore algorithm A together with the finite array x can be used by two non-anonymous processes q 0 and q 1 to solve wait-free using only registers the following election task: Each non-faulty process is required to decide the id of one of the participating processes such that all decisions are the same. This task cannot be solved wait-free with registers [START_REF] Borowsky | Generalized FLP impossibility result for t-resilient asynchronous computations[END_REF], as it can then be used to solve consensus.

end of the proof of the Claim.

The recursion tree of explore(λ 0 , c 0 , P 0 ) has bounded degree. It thus follows from the claim that a schedule is simulated in which an output x[j] for some j > i c , is used to simulate a query step. That is, x[j] is a value output by X after the time of the last crash. Let explore(λ, c, P ) be the first call to explore in which a value output by X after the last crash is used to simulate a query step. Without loss of generality, let us assume that q 0 is the simulated process in this step. As the output of the query depends solely on λ and c, the next calls to explore following the simulation of this step are of the form explore( * , * , {q 0 }) (line 9). That is, x[j] is used for the first time while simulating the schedule induced by the sequence λ • 0 • 0 • 0 . . .. Let r the real run of A that is indistinguishable from S λ,x . By Lemma 5.2, r does exist since every failure detector output used in S λ,x is taken before the last crash, that is at times τ such that |F(τ )| ≤ n -2. Run r is obtained by extending and adding clones to r. In r , after r, only q 0 and his clones take steps. Those steps are the same as in the simulated schedule S λ•0•0•0...,x . The number of clones of q 0 is |correct(F)| -1. q 1 has no clones. r is a real execution of A, as we can identify q 0 and his clones to the set of correct processes in F and q 1 with one the faulty processes. Thus no process takes step after it has failed in r . Moreover, r is fair. Therefore, q 0 decides in S λ•0•0•0...,x . This happens at some time τ d > τ c . By the code (line 17), the value of a new register A[m ] with m > m is changed to and the emulated output of C is set to m > m. Proof. Let p be a correct process and x the array of samples of X at p. We assume that there is at least two correct processes in the underlying failure pattern F. Therefore, according to Lemma 5.2, every simulated schedule S λ,x is indistinguishable from a real execution of A . Hence, as seen in the proof of Lemma 5.4, explore(λ 0 , c 0 , P 0 ) does not terminate at each correct process p, as it would otherwise imply a wait-free protocol for two-processes election using only registers. The remaining of the proof is essentially the same as the proof of Theorem 3 in [START_REF] Zielinski | Anti-Omega: the weakest failure detector for set agreement[END_REF]. The key ingredient is the particular order in which schedules are simulated. Let λ 0 • λ 1 • . . ., c 0 • c 1 • . . . and P 0 • P 1 . . . be defined as having explore(λ 0

• λ 1 • • • λ k+1 , c k+1 , P k+1 ) be the first call in explore(λ 0 • λ 1 • • • λ k , c k , P k ) that does not terminate. Let λ = λ 0 • λ 1 • • • .
At least one process takes infinitely many steps but does not decide in S λ,x . As S λ,x is indistinguishable from a real run of A , it must be the case that inf (λ) {0, 1} (Lemma 5.3). Without loss of generality, let inf

(λ) = {0}, that is λ = λ • 0 • 0 • • • .
For every k, k , k ≤ k , P k ⊇ P k ⊇ {λ k } (lines 9-10). Moreover, the order in which set P are chosen (line 9) implies that for each k, P k = ∪ k geqk {λ k }. Therefore, we have P k = {q 0 } for each k ≥ k for some k > 0. Hence, eventually process p simulates solely schedule S λ,x , in which process q 0 never decides and takes infinitely many steps. It then follows that p eventually stops modifying the output of the emulated failure detector C. C 1 is identical to C, while in an n-processes system, C n provides no information on failures. Intuitively, failure detector C k behaves in a similar way as C, but has a coarser view on failures. In any time interval in which less than k failures occur, the output of C k may or may not change. However, as soon as the number of failures is at least k, and provided that the interval is large enough, it is guaranteed that the output of C k is incremented.

C k -based k-set agreement protocol

This section presents a protocol (Algorithm 3) that solves the k-simultaneous binary consensus task using failure detector C k . In the k-binary simultaneous consensus task [START_REF] Afek | The ksimultaneous consensus problem[END_REF] (k-BSC for short), each process is initially provided with a binary vector -→ v ∈ {0, 1} k and is required to decide a pair (i, b) where i, 1 ≤ i ≤ k is an integer and b a binary value subject to the following requirements:

1. Validity. If (i, b) is decided then b is the ith bit of some input vector. Intuitively, the k-BSC task might be seen as trying to solve k instance of binary consensus in parallel. Each process has initially a binary of proposal -→ v [i] for each instance i, and is required to decide in at least one instance. Decisions (if any) in each instance i must satisfy the validity and agreement of consensus. k-set agreement can be implemented wait-free from k-BSC objects and registers. The protocol presented in [START_REF] Afek | The ksimultaneous consensus problem[END_REF] does not use ids but relies on snapshot objects, which can be implemented with registers without using ids [START_REF] Guerraoui | Anonymous and fault-tolerant shared-memory computing[END_REF]. Therefore, k-set agreement can be solved using k-SBC in the anonymous shared memory model.

Description of the protocol Algorithm 3 shares a similar structure with the binary consensus protocol (Algorithm 1). It consist in two tasks T 1 and T 2 that run in parallel. A process decides at line 27 in task T 2 when it reads a pair (i, v) from the decision register D.

In task T 1, each i, 1 ≤ i ≤ k is associated with an infinite alternating sequence δ i = SA i [START_REF] Afek | The ksimultaneous consensus problem[END_REF], AC i [START_REF] Afek | The ksimultaneous consensus problem[END_REF], SA i [START_REF] Angluin | Local and global properties in networks of processors (extended abstract)[END_REF], AC i [2] of safe agreement and adopt-commit objects, in a way similar to the extended BG-simulation protocol [START_REF] Gafni | The extended bg-simulation and the characterization of t-resiliency[END_REF]. Indeed, tasks T 1 might be seen as a variant of the extended BG-simulation adapted to the anonymous settings. The purpose of each sequence δ i is to reach agreement on a common value, which is one the proposal -→ v [i] of some process. As in Algorithm 1, in each round r, processes first access safe agreement SA i [r] trying to pick a common non-⊥ value (lines 9-17). Then, again as in -→ est ← -→ v ; start tasks T1,T2

6: task T1: As k-set agreement can be implemented anonymously from registers and k-binary simultaneous consensus objects, we have: Corollary 6.4. There is an algorithm that solves k-set agreement using registers and failure detector C k .

Conclusion

The paper has defined the new failure detector C and has shown that, within the class of anonymitypreserving failure detectors, it is the weakest failure detector for consensus in the anonymous shared memory model in any environment. The paper has also shown that failure detector C k , a natural extension of C, can be used to solve k-set agreement tolerating any number of failures. Obvious questions for future work include (dis)proving that C k is the weakest anonymity preserving failure detector for k-set agreement and extending weakest failure detector results in anonymous systems outside the domain of anonymity preserving failure detectors.

7 :if aux = ⊥ then 11 :

 711 for r = 1, 2, . . . do 8: repeat d ← C-query() until d ≥ r end repeat 9: aux ← SA[r].propose(est) aux ∈ {0, 1, ⊥} 10: repeat aux ← SA[r].read(); d ← C-query() 12:until (d > r) ∨ (aux = ⊥)13:

  algorithm A , each process has an extra local counter η whose initial value is 1. Each register M EM [ ] is divided in two fields, data and ctr. M EM [ ].data is initialized as specified by A while the initial value of M EM [ ].ctr is 0. For each integer and value v, each operation M EM [ ].write(v) in A is replaced in A by M EM [ ].write( v, η ), i.e., v and the current value of the local variable η are written to the data and ctr components, respectively, of M EM [ ]. Similarly, each instruction of the form

1 :

 1 init A[1 . . .] ← [⊥, . . .] Array of registers with initial value ⊥ 2: procedure C-emulation 3: x[1 . . .] ← [⊥, . . .]Array for storing outputs of X 4:

7 :

 7 function explore(λ, c, P ) 8:

13 :

 13 step = write(v) to th register then write v to c.M EM [ ] 14:step = X-query() then take x[ ] as the output of X, where is the value of η in c.s i ;

19 :λ

 19 ← λ • i; explore(λ, c, P )

Lemma 5 . 5 .

 55 If |correct(F)| ≥ 2, there exist an integer D such that for every process p and every time τ , C-out τ p ≤ D.

Theorem 5 . 6 .

 56 Algorithm 2 emulates C.Proof. By the code, the values of the variable out-C never decrease (Monotonicity property). The convergence property directly follows from Lemma 5.5.Lemma 5.4 implies that the signaling property holds: Let τ, τ , τ < τ be two times such that F(τ ) F(τ ). Let p and p be two processes, p being a correct process. As a crash occurs after time τ , out-C τ p ≤ m. This follows from the facts that at the time τ c of the last crash, only the registers A[1], . . . , A[m] have their value equal to , and whenever out-C is set to d, the value of register A[d] has previously been changed to (line 17). Hence out-C τ p ≤ m. By lemma 5.4 and the monotonicity property, there exists a time τ , τ ≤ τ such that out-C τ p ≤ m < out-C τ p , as desired.6 The case of k-set agreementThis section defines the failure detector C k and presents a C k -base algorithm for k-set agreement.

6. 1

 1 The failure detector family C k , 1 ≤ k ≤ n For every k, 1 ≤ k ≤ n, failure detector C k generalizes C as follows. For every failure pattern F, history H : Π × N → N belongs to C k (F) if and only if 1. Monotonicity. For every process p i , for every times τ ≤ τ , H(p i , τ ) ≤ H(p i , τ ); 2. k-Signaling For every times τ ≤ τ , for every pair of processes p i , p j , if k ≤ |F(τ ) \ F(τ )|, there exists a time τ , τ ≤ τ such that H(p i , τ ) < H(p j , τ ); 3. k-Convergence. If k < |correct(F)|, there exists a time τ such that for every τ , τ ≤ τ , for every processes p i , p j , H(p i , τ ) = H(p j , τ ).

2 . 3 .

 23 Agreement. For every i, 1 ≤ i ≤ k, if pairs (i, b) and (i, b ) are decided then b = b . Termination. Every correct process eventually decides.

Algorithm 3 C 2 : 3 :

 323 k -based k-simultaneous binary consensus protocol. 1: init SA i,1≤i≤k [1, . . .] k infinite arrays of safe agreement objects AC i,1≤i≤k [1, . . .] k inifinite arrays of adopt-commit objects

7 : 8 : 9 :

 789 for r = 1, 2, . . . do repeat d ← C-query() until d ≥ r end repeat for i = 1, . . . , k do 10:--→ aux[i] ← SA i [r].propose( -→ est[i]) --→ aux ∈ {0, 1, ⊥} konly b can be proposed to SA i [r ] and thus the input of every propose() operation on AC i [r ] is b or ⊥. Therefore, if (i, b ) is written to D in round r , b = b.

  As seen above, each process p ∈ P eventually enters round R, and it follows from Lemma 4.1 that no faulty process enters rounds R. Hence every call to propose() on the safe agreement object SA[R] returns. By the non-triviality property, at least one of these calls is successful, i.e., returns a non-⊥ value. By the agreement property of safe agreement, all non-⊥ values returned by successful propose() operations are the same. Let v denote this value.

Let p ∈ P . Suppose that p propose() operation on SA[R] returns ⊥. p cannot exit the repeat loop on lines 11-12 by getting a value d > R from C, as by definition R is the largest value output by C at p. However, as there is a successful propose() operation on SA[R], one of p read() operations on SA[R] returns a non-⊥ value. By the agreement property of safe agreement objects, this value is v.

More generally, v may belong to any finite set. Restricting to binary inputs is sufficient for our purpose, namely using failure detector C to solve binary consensus.

Algorithm 1 object AC i [r] is used to reconcile the two possible outputs returned by the operations on SA i [r], namely ⊥ and some value v ∈ {0, 1} (lines [START_REF] Delporte-Gallet | Wait-freedom with advice[END_REF][START_REF] Delporte-Gallet | Tight failure detection bounds on atomic object implementations[END_REF][START_REF] Faith | On the space complexity of randomized synchronization[END_REF][START_REF] Michael | Impossibility of distributed consensus with one faulty process[END_REF][START_REF] Felix | The failure detector abstraction[END_REF][START_REF] Gafni | Round-by-round fault detectors: Unifying synchrony and asynchrony (extended abstract)[END_REF][START_REF] Gafni | The extended bg-simulation and the characterization of t-resiliency[END_REF], and ensure agreement and validity.

For termination, some care should be taken as:

• On one hand, when the number of failures f is small (f ≤ k -1) or there are few correct processes (|correct| ≤ k), the output of C k is arbitrary;

• On the other hand, when a large number f, f ≥ k of processes fail, every safe agreement objects SA 1 [r], . . . , SA k [r] of a given round r may be "blocked", in the sense that no propose() operations on each of the objects are successful. In that case, the output of C k should allow the processes to move to the next round.

To resolve this difficulty, each process accesses the safe agreement objects SA 1 [r], . . . , SA 2 [r] of round r in that order until it receives a non-⊥ response or reaches the end of the sequence (line [START_REF] Bonnet | Consensus in anonymous distributed systems: Is there a weakest failure detector[END_REF][START_REF] Bonnet | Anonymous asynchronous systems: the case of failure detectors[END_REF][START_REF] Borowsky | Generalized FLP impossibility result for t-resilient asynchronous computations[END_REF][START_REF] Borowsky | The BG distributed simulation algorithm[END_REF]. If at most k processes enter the round, each non-faulty process thus performs a successful propose() operation on one the safe agreement of the round object. Moreover, as in Algorithm 1, a process enters round r only after its local failure detector module has output a value d ≥ r (line 8). In the case where f ≥ k, there thus exists due to the k-signaling property of C k a round R such that no more than k -1 faulty processes enter any round r, r ≥ R. In any such round r, at most k -1 safe agreement objects are blocked (by processes failing while performing a propose() operation).

After having invoked propose() on each safe agreement SA 1 [r], . . . , SA k [r], a process waits until either (1) a read() operation returns a non-⊥ value or (2) the output of C k is larger than r (line 16). When |correct| > k, the k-convergence property ensures that eventually the output of C k is the same value D ≥ R at each process. Hence, in round D condition (1) cannot be satisfied, but as seen above, at least one the safe agreement of round R is not blocked. Eventually, every read() operations performed on that object returns a non-⊥ value. To summarize, the protocol ensures that every non-faulty process receives a non-⊥ value from one of the safe agreement object of round r if (i) at most k processes enter round r or (ii) C k output eventually stabilizes on D and r = D. Note that condition (i) or (ii) is satisfied in every execution, as if the failure detector output does not stabilize, |correct| ≤ k. Finally, when a process p has obtained a non-⊥ value v from safe agreement SA [r], it first accesses the corresponding object AC [r] to try to commit value v (line 18). If round r satisfies conditions (i) or (ii) above, this ensure that only v is proposed to AC [r], and thus p writes to the decision register D (line 20) and eventually decides.

Proof of the protocol We consider an arbitrary run of the protocol. Let F and H ∈ C k (F) be respectively the failure pattern and the failure detector history in the run. Lemma 6.1. Let p be a correct process. There is an integer D and at time τ such that the number of faulty processes at which C k outputs values larger than or equal to D is strictly smaller than k: |{q : q ∈ faulty(F) ∧ ∃τ q : H(q, τ q ) ≥ D}| < k.

Proof. Let f denote the number of failures in F and let τ 1 ≤ . . . ≤ τ f denote the times at which the failures occur. If f < k, the Lemma is trivially satisfied.

Let us assume that f ≥ k. Let p be a correct process. Let d f be the largest output of C k at faulty processes before τ f -k+1 . Formally, d f = max{H(q, τ ) : q ∈ faulty(F) ∧ τ ≤ τ f -k+1 }. As exactly k -1 crashes occur after τ f -k+1 , C k output may be strictly larger than d f for at most k -1 faulty processes.

end for 13:

end if 18:

end case

24:

end for

25:

end for 26: task T2: A process decides when a pair is returned at line 27. Lemma 6.2 (Termination). Every correct process decides.

Proof. Assume for contradiction that no correct processes decide. Therefore no processes write to the decision register D at line 20.

We distinguish two cases according to whether the outputs of C k is bounded or not.

• The output of C k is unbounded. As in the consensus protocol (Algorithm 1), a correct process cannot get stuck in round r if its local failure detector module eventually outputs a value > r. Indeed, the only blocking part of the code of round r is the repeat loop of lines 15-16. For each process p, the loop terminates as soon a value d > r is output by C k . It thus follows that there is a round R in which only correct processes enter.

Let p be a correct process that enters round R. In the second part of round R, observe that for every process q that accesses object AC [R], we have --→

aux[ ] = b q = ⊥. Note that by the agreement property of safe agreement, for every process q, q , if --→

aux[ ] = b q = ⊥ at q and --→ aux[ ] = b q = ⊥ at q then b q = b q . Hence, the input of every propose() operation on AC [R] is the same value b = ⊥. By the convergence property of adopt-commit object, each of the operation returns (commit, b ). Therefore, by the code (line 20) p writes b = ⊥ to D : a contradiction. Theorem 6.3. Algorithm 3 solves k-binary simultaneous consensus using failure detector C k .

Proof. Validity directly follows from the validity properties of adopt-commit and safe agreement objects. Termination follows from Lemma 6.2. For agreement, it is sufficient to prove that if (i, b) and (i, b ) are written to D we have b = b , for every i, 1 ≤ i ≤ k. The proof is similar to the proof of agreement of the consensus algorithm (Theorem 4.3).

Suppose that processes p and p write respectively (i, b) and (i, b ) to D in that order, where i, 1 ≤ i ≤ k. Without loss of generality, assume that p writes to D in round r. By the code (line 20), before writing to D, p invokes propose() on AC i [r] and receives (commit, b) as a response. It follows from the agreement property of adopt-commit object that every value written to D in round r is b.

Moreover, for every process q that does not return in round r at line 20, we have -→ est[i] = b (agreement property of adopt-commit) when q leaves round r. Hence in any subsequent round r ,

A Anonymous safe agreement

For completeness, this section presents an anonymous implementation of a safe agreement object using registers. The implementation is an almost verbatim copy of an anonymous binary consensus protocol [START_REF] Attiya | Computing in totally anonymous asynchronous shared memory systems[END_REF], designed for asynchronous, anonymous but failure-free shared-memory systems.

Attiya, Gorbach and Moran protocol (Algorithm 4 in [START_REF] Attiya | Computing in totally anonymous asynchronous shared memory systems[END_REF]) consists in two parts, a wait-free section and a final wait statement. The processes first execute the wait-free code. Agreement is eventually reached in the wait-free section by evicting slow processes and, in case of conflicting proposals, favoring value 0. That is, the number of processing willing to decide 1 progressively decreases. Processes dropped from the wait-free section simply wait until the remaining processes are able to agree. In the safe agreement implementation (Algorithm 4 below), the propose() operation is implemented by the wait-free code, while a read() operation consists in checking whether the exit condition of the wait statement is satisfied.

Algorithm 4 Safe agreement (Attiya et. al failure-free consensus protocol [START_REF] Attiya | Computing in totally anonymous asynchronous shared memory systems[END_REF]). end if

25

In more details, the protocol relies on a procedure reduceone() (lines 16-23) that aims at decreasing disagreement among the processes. Each process invokes reduceone() with input 0 or 1 and obtains a response in {⊥, 0, 1} with the following properties: Lemma A.1 ([6], Lemma 4.1). Non-triviality: The output of at least one process is not ⊥; Validity: If the output of p is v = ⊥, then the input of some process is v. Monotonicy: If some process outputs 0 and another process outputs 1, then the number of processes with output 1 is strictly smaller than the number of processes with input 1.

By the code, reduceone() is wait-free. Suppose that n processes invoke propose() and none of them fails. Essentially, in each iteration j of the for loop (lines 5-13) (1) at least one process receives a non-⊥ value from its invocation of reduceone(j, * ) and ( 2) the number of processes whose estimate est is 1 is strictly smaller than in the previous iteration. Hence, after sufficiently many operation, only the value of A j [0] is changed from false to true, which then allow some process to write 0 to D and return 0 as the result of its propose() operation. Indeed, we have Lemma A.2 ([6], Lemma 4.6). If n processes invoke propose() and none of them fail, some process write a non-⊥ value to D in iteration j ≤ n + 1 When a successful propose() returns, a value = ⊥ has been written to the shared register D. Hence, every read() operation that follows returns a non-⊥ value (consistent reads property). Validity and agreement of the safe agreement implementation follow from the same properties of the original consensus protocol. Indeed, as it is designed for asynchronous systems, failures may impair progress but do not cause violation of safety properties. For details about the underlying principle and the proof of Algorithm 4, we refer to [START_REF] Attiya | Computing in totally anonymous asynchronous shared memory systems[END_REF].