Zohir Bouzid

Pierre Sutra

Corentin Travers

Anonymous Agreement: The Janus Algorithm

Keywords: Anonymity, asynchronous shared memory, consensus, failure detectors, homonym processes, indulgent algorithms

We consider the consensus problem in an n-process shared-memory distributed system when processes are anonymous, i.e., they have no identities and are programmed identically.

We present Janus, a new anonymous consensus algorithm that reaches decision after O( √ n)

writes in every solo execution. The set of values that can be proposed is unbounded and the algorithm tolerates an arbitrary number of crash failures. The algorithm relies on an anonymous eventual leader election mechanism. Furthermore, during solo executions in which a non-faulty process is elected since the beginning, the individual step complexity of Janus is O(n), matching a recent lower bound by Aspnes and Ellen (SPAA 2011).

The algorithm is then extended to the case of homonymous system in which c, 1 ≤ c ≤ n, identities are available. In every solo execution, the modified algorithm achieves O( √ nc + 1+ log c log log c ) individual write complexity and O(nc + log c log log c ) individual step complexity.

Introduction

In a typical distributed system, processes are eponymous, i.e., they have unique identities. On the other hand, in anonymous systems, processes have no identity and are programmed identically. When provided with the same input, processes in such systems are indistinguishable. Anonymity adds a new, challenging, difficulty to distributed computing.

From a practical point of view, anonymity is sometimes unavoidable. For example, consider a system composed of many tiny nodes, e.g., sensors networks. Sensors nodes might have limited storage and computational capability, and might not have been provided with unique identifiers [START_REF] Angluin | Computation in networks of passively mobile finite-state sensors[END_REF]. Some other systems, like peer-to-peer file sharing applications [START_REF] Chothia | A survey of anonymous peer-to-peer filesharing[END_REF], might require users to remain anonymous as a prerequisite to ensure privacy. See [START_REF] Federrath | Proceedings Designing Privacy Enhancing Technologies[END_REF] for more details regarding anonymous computing and privacy.

Recently, several papers [START_REF] Aspnes | Tight bounds for anonymous adopt-commit objects[END_REF][START_REF] Attiya | Computing in totally anonymous asynchronous shared memory systems[END_REF][START_REF] Delporte | Two consensus algorithms with atomic registers and failure detector Ω[END_REF][START_REF] Guerraoui | What can be implemented anonymously? Distributed Computing[END_REF][START_REF] Guerraoui | Anonymous and fault-tolerant shared-memory computing[END_REF][START_REF] Ruppert | The anonymous consensus hierarchy and naming problems[END_REF] have addressed the question of the computational power of anonymous systems, with an emphasis on the consensus problem. In particular, Aspnes and Ellen [START_REF] Aspnes | Tight bounds for anonymous adopt-commit objects[END_REF] have shown that, when the number of proposed values is unbounded, the solo step complexity of consensus is Θ(n) in an n-process system. This paper presents a new, efficient, consensus algorithm for anonymous system.

The consensus problem. Consensus is a fundamental problem in fault-tolerant distributed computing. Informally, n processes, each starting with a private value, are required to agree on one value chosen among their initial values. For shared memory systems, it is well known that asynchronous fault tolerant consensus is impossible as soon as at least one process may fail by crashing [START_REF] Mc Loui | Memory requirements for agreement among unreliable asynchronous processes[END_REF]. Trivially, consensus is thus impossible in anonymous, asynchronous and failure-prone shared memory. The same impossibility holds for non-anonymous message passing asynchronous systems [START_REF] Michael | Impossibility of distributed consensus with one faulty process[END_REF].

Since the publication of this result, several approaches have been identified to overcome this impossibility, including randomization (e.g., [START_REF] Ben-Or | Another advantage of free choice: Completely asynchronous agreement protocols (extended abstract)[END_REF]), strengthening the model with timing assumptions (e.g., [START_REF] Dwork | Consensus in the presence of partial synchrony[END_REF]) or failure detectors (e.g., [START_REF] Deepak | Unreliable failure detectors for reliable distributed systems[END_REF]) and strong synchronization primitives [START_REF] Herlihy | Wait-free synchronization[END_REF]. Similarly, in anonymous systems, randomization [START_REF] Buhrman | On the importance of having an identity or, is consensus really universal?[END_REF], failure detectors [START_REF] Bonnet | The price of anonymity: Optimal consensus despite asynchrony, crash and anonymity[END_REF][START_REF] Delporte | Two consensus algorithms with atomic registers and failure detector Ω[END_REF], as well as additional synchrony assumptions [START_REF] Delporte-Gallet | Fault-tolerant consensus in unknown and anonymous networks[END_REF] have been investigated to solve consensus.

A failure detector is a distributed device which provides processes with possibly unreliable information about failures. Unreliable failure detectors, and more generally system assumptions which are not guaranteed to always hold, have motivated the study of indulgent algorithms [START_REF] Guerraoui | A general characterization of indulgence[END_REF]. Informally, an algorithm is indulgent if it is always safe, i.e., it never violates the safety part of the problem it is supposed to solve, and converges to a decision when the failure detector matches its eventual property. In this line of research, the key question is determining how fast indulgent algorithms converge when the eventual property of the failure detector is satisfied [START_REF] Dutta | The inherent price of indulgence[END_REF].

Contributions of the paper. This paper investigates the consensus problems in an anonymous, crash prone and asynchronous shared memory systems. In particular, we are interested in the individual write step complexity of anonymous consensus. Typically, shared memory systems use caching techniques to improve performances. When a write is performed, the system has to ensure that every cached copy is updated, which is costly. Differently, repeatedly reading a shared location may be a local operation. The paper presents the following two main results:

• The first result is a consensus algorithm. The set of input values that processes might propose is unbounded. The algorithm relies on a failure detector of the class AΩ [START_REF] Bonnet | Anonymous asynchronous systems: The case of failure detectors[END_REF] and tolerates up to n -1 process crashes. The "anonymous leader" class AΩ is the anonymous counterpart of the class Ω, which is the weakest failure detector for solving consensus [START_REF] Deepak | The weakest failure detector for solving consensus[END_REF] in the eponymous settings. Informally, when queried, a failure detector of the class AΩ returns a boolean. Eventually, each query, except the queries issued by some non-faulty process, returns false. If no failure detector is available, we note that our algorithm can easily be made obstruction-free [START_REF] Herlihy | Obstruction-free synchronization: Double-ended queues as an example[END_REF] by simply removing failure detector invocations. The algorithm is write-efficient in the following sense : a process executing solo decides after performing O( √ n) write operations and O(n) shared memory operations in total.

• The second result is a generalization of our consensus algorithm to the case of homonymous systems recently introduced by Delporte-Gallet et al [START_REF] Delporte-Gallet | Byzantine agreement with homonyms[END_REF], in which a small number c, 1 ≤ c ≤ n of identities is available. The system is no longer totally anonymous since processes have identities. However, when the number of ids is smaller than n, several processes may share the same id. The generalized algorithm achieves O( √ nc + 1 + log c/ log log c) individual write complexity and O(nc + log c/ log log c) step complexity in solo execution. As in the case of anonymous systems, the algorithm relies on a failure detector of the class AΩ and the set of values that can be proposed is unbounded.

Roadmap. The paper is composed of 6 sections. Section 2 describes the anonymous shared memory model and the failure detector class AΩ. An anonymous consensus is presented in Section 3. Its generalization to the case of systems with homonym processes follows (Section 4). Section 5 surveys related work and Section 6 concludes the paper.

System model

Anonymous shared memory model. We consider a system Π of n ≥ 2 deterministic processes. Processes are anonymous: they do not have identifiers, and they execute identical algorithms. The total number of processes n is however known by the processes. The system is asynchronous, in the sense that each process runs at its own speed, independently of the other processes.

Processes communicate with each other by reading and writing atomic shared registers (they are linearizable [START_REF] Herlihy | Linearizability: a correcteness condition for concurrent objects[END_REF]). Registers are multi-writer and multi-reader: every register can be written in, or read from, by every process. In the pseudo-code we use to describe our algorithm, shared objects are denoted by upper-case letters, while lower-case identifiers are reserved for processes' local variables.

Failures and failure detectors. Processes may crash. A process is correct in an execution if it never crashes in this execution; otherwise it is faulty. We make no assumption on the number of crashes that may occur during a run.

As noted in the Introduction, a failure detector is a distributed oracle that provides processes with possibly unreliable information about failures [START_REF] Deepak | Unreliable failure detectors for reliable distributed systems[END_REF]. Several classes of failure detectors suited to anonymous systems have been defined [START_REF] Bonnet | Anonymous asynchronous systems: The case of failure detectors[END_REF]. The failure detector we consider is anonymous Ω, denoted hereafter AΩ. Each process is provided with a primitive AΩ.query(), which returns true or false. The following property, termed eventual leadership is ensured: there exists some correct process p 0 such that eventually every AΩ.query() always returns true at p 0 , and false at every other process.

Consensus. Consensus is a distributed task which consists in a single operation propose (v) that takes as input a value v in some (possibly unbounded) set V, and returns a value v ′ in V. When a process p invokes propose (v), we say that p proposes v. Similarly, when propose (v) returns a value v, we say that p decides v. Consensus requires that in every run: (Agreement) two processes cannot decide different values; (Validity) if a process decides some value v, then v was proposed before; and (Termination) every correct process eventually decides. Time complexity. Consider an algorithm A that solves consensus in an asynchronous system equipped with an eventual failure detector such as AΩ. In every execution, a correct leader process eventually emerges, but there is no bound on the time at which a correct process is elected. Obviously, the worst-case number of reads, or writes, performed by a process is unbounded. Thus, we measure the time complexity of asynchronous consensus algorithms in solo executions. Specifically, the individual write complexity is the worst-case number of write operations that occur in solo executions in which only one process participates. Similarly, the individual step complexity is the worst case total number of read and write operations performed in solo executions.

3 The Janus1 Algorithm

Description of Janus

The Janus algorithm solves consensus among n asynchronous and anonymous processes. Its pseudocode is depicted in Figure 1. Janus relies on a failure detector of the class AΩ and tolerates up to n -1 process failures. No knowledge of the set of values that can be proposed is required. In particular, this set might be unbounded.

A process p initiates its algorithm by invoking propose(v), where v is the input value of p. Process p then launches two tasks T1 and T2 that run in parallel (line 1). In task T2, p monitors a shared register decision D, which is initialized to ⊥2 . If p reads a non-⊥ value d in D, p decides that value (line 21) and terminates.

In task T1, the execution proceeds in asynchronous rounds. Process p maintains an estimate (stored in the local variable est), which is the value it currently favors. During each round to which it participates, p tries to commit its estimate by writing it in the decision register D (line 17). The algorithm ensures that [START_REF] Abrahamson | On achieving consensus using a shared memory[END_REF] no two distinct values are committed and (2) at least one process eventually commits its estimate. To that end, each round r is associated with two multi-writer/multi-reader shared registers: the value register T [r] and the conflict register C[r]. Intuitively, T [r] stores a value that some process is willing to commit in round r, while C[r], when set to true, indicates that two or more processes try to commit distinct values in round r.

A process p entering round r first checks whether a value has already been written in T [r] (line 5). If this happens, p immediately enters round r ′ ≥ r, where r ′ is the greatest round for which a value has been written to the associated register T [r ′ ], thus possibly skipping rounds r, . . . , r ′ -1. In addition, p adopts the value currently stored in T [r ′ ] as its new estimate. Otherwise, i.e., when T [r] equals ⊥, p writes its estimate in T [r].

Writing/reading value v to/from the value register T [r] is however not sufficient to allow this value to be committed. Several processes may be performing write operations concurrently on T [r] and thus, assuming that v is committed, a process entering round r later might adopt a value v ′ = v and commits this value. Therefore, before committing its estimate v (that is, writing v in D, line 17), process p first checks that no conflicts have been detected in the last K rounds and that the registers T [r], T [r -1], . . . , T [r -K + 1] still store v (lines 14-16). For large enough values of K, these two conditions prevent any other value different from v from being written in T [r]. We show in the proof (Lemma 6) that for K ≥ ⌈2 √ n⌉ + 1 this property is ensured.

Conflicts are detected at lines 9-11. A process p with estimate v executing round r performs a read operation in every register

T [r ′ ], r -K + 1 ≤ r ′ ≤ r. Whenever a value different from v is returned, the corresponding conflict register C[r ′ ] is updated to true.
Finally, the progress of Janus relies on the underlying failure detector AΩ. A process is allowed to enter round r only if it considers itself as a leader. In more details, before entering round r, each process queries its local failure detector module (line 3). Only if this query returns true, the process starts round r. Eventually, a unique non-faulty process is elected by the failure detector. This process eventually executes rounds alone, and eventually decides (See Lemma 3). rnd ← rnd + 1 % Look for an estimate with higher priority % ( 5)

if (T [rnd] = ⊥) then let r ← min{r ′ > rnd | T [r ′ ] = ⊥} ; (6) est ← T [r -1]; rnd ← r -1 (7) else T [rnd] ← est (8)
end if % Look for conflicting estimates in the last K rounds % [START_REF] Buhrman | On the importance of having an identity or, is consensus really universal?[END_REF] for each i : 0

≤ i < min(rnd, K) do (10) if (T [rnd -i] = est) then C[rnd -i] ← true end if (11)
end for % Check if no conflict occurs in the last K rounds % [START_REF] Chothia | A survey of anonymous peer-to-peer filesharing[END_REF] can decide ← true; [START_REF] Delporte | Two consensus algorithms with atomic registers and failure detector Ω[END_REF] if (rnd ≥ K) then [START_REF] Delporte-Gallet | Byzantine agreement with homonyms[END_REF] for each i : 0

≤ i < K do (15) if (C[rnd -i] = true) ∨ (T [rnd -i] = est) then can decide ← false endif (16)
end for end if [START_REF] Dwork | Consensus in the presence of partial synchrony[END_REF] if

(can decide) then D ← est endif (18) end if (19) end while task T2 : (20) repeat d ← D until d = ⊥ (21) stop T1; decide(d) Figure 1: The Janus algorithm, K = 2 √ n + 1
When a failure detector is not available, we note that Janus is easily made obstruction-free by removing the query to the failure detector at line 3.

Proof of the Janus algorithm

Fix some execution of the algorithm. Since the shared objects (i.e. the registers) are atomic the execution (as an interleaved sequence of reads and writes operation of the processes) is linearizable [START_REF] Herlihy | Linearizability: a correcteness condition for concurrent objects[END_REF]. As a consequence, we may consider σ a linearization of the reads and writes operations. We shall say that an operation in σ on some register occurs at time τ if τ is the linearization point of that operation. As usual, we shall note var p the local variable var of process p. The execution of the (asynchronous) round r by p is the interval during which rnd p = r. More precisely, it is the sequence of steps applied by p when rnd p = r.

A process, executing round r, writes its estimate v in T [r], provided it observes that no value has been previously written in T [r] (line 7). The following Lemma implies that if this occurs, v has been previously written to

T [1], . . . , T [r -1]. Lemma 1. Let r > 1.
Suppose that a write operation op with parameter v is performed on T

[r].
Then a write operation op ′ of value v to T [r -1] occurs before op.

Proof. Suppose that op is performed by process p. Observe that when this occurs (line 7), rnd p = r and v = est p , i.e., v is the estimate of p at the beginning of round r, and the previous value of rnd p is r -1 (lines 4-7).

We consider two cases according to the line at which p sets rnd p to r -1.

• p sets rnd p to r -1 at line 6. Let v ′ denote the value read by p from T [r -1]. Process p then adopts v ′ as its new estimate (line 6). As p does not modify again est p in round r -1, v ′ is the value of est p when it starts executing round r. Therefore, v ′ = v and thus v has been written in T [r -1].

• p sets rnd p to r -1 at line 4. As p does not change the values of rnd p at line 6, p reads ⊥ from T [r -1] and thus writes its current estimate v ′ in T [r -1] (line 7). By the code, v ′ is the estimate of p when p starts executing round r. Therefore, v ′ = v and v is written in T [r -1] (by p).

It then follows from the previous Lemma that algorithm 1 satisfies the validity requirement of consensus.

Lemma 2 (Validity). Every decided value is a proposed value.

Proof. Let v be a decided value (line 21). Note that v has been written in the shared register D by some process p. Let r the round in which this occurs. That is, when p writes v in D, we have rnd p = r and also est p = v. At the beginning of round r, the estimate of p is written in T [r] by p (line 7), or the estimate of p is the value returned by the read operation performed on that register (line 6). In both cases, v has been written in T [r]. It thus follows from Lemma 1 that v has been written in each register T [i], 1 ≤ i ≤ r. In particular, v is written in T [START_REF] Abrahamson | On achieving consensus using a shared memory[END_REF]. Validity follows then from the fact that values written in T [START_REF] Abrahamson | On achieving consensus using a shared memory[END_REF] are the processes' proposals.

We next show that termination is ensured. Lemma 3 (Termination). Every correct process eventually decides.

Proof. Assume for contradiction that some correct process q never decides. As, (1) only non-⊥ values can be written in D, and (2) q reads D infinitely many times and never decides, no value v = ⊥ is written in D. As a process may decide only if it reads a value different from ⊥ in D, this implies that no process decides.

By the eventual leadership property of the failure detector class AΩ, there is a correct process p and a time τ such that each AΩ-query() performed after τ returns true if and only if the invoking process is p. At time τ , let R be the largest round such that T [R -1] = ⊥. Clearly, p is the only process that can execute rounds R + 1, R + 2, . . . (line 3). Moreover by Lemma 1, for all i > 0, we have that

T [R + i] = ⊥.
As p is correct, it never decides, and for all i > 0 we have that T [R + i] = ⊥, p eventually executes rounds R + 1, R + 2, . . . As p is the only process that executes those rounds, it follows from the code (lines 5-7) that p writes in each register T [R + i] for all i > 0. Besides, it is not difficult to observe that the same value, say v, is written by p in each register T

[R + i].
As no process except p executes rounds R+i, i > 0, no process except p performs write operations on registers T

[R + i], i > 0. Therefore it holds forever that C[R + i] = false and T [R + i] = v, once p has written v in T [R + i]. Consider the execution of round R + K by p. Process p first writes v in T [R + K] (line 7). After this occurs, we have C[R + i] = false and T [R + i] = v for each i, 0 < i ≤ K.
Hence, can decide p = true after the execution of the for each loop at lines 14-16. We conclude that p writes v in D (line 17), and decides by the code of task T2: contradiction.

Proof of agreement. We divide the execution in epochs as follows. Epoch e i is an interval that starts with the first write (according to the linearization σ) to register T [i] and ends immediately before the first write (if any) performed to register T [i + 1]. Given a read, or write, operation op, we say that op occurs in epoch e i , or equivalently, that op is performed in e i , if op is linearized in the interval e i . Clearly, if a write to T [j] occurs in e i , then j ≤ i. The next lemma directly follows from the code of Janus (lines 5 and 7). Suppose that process p performs a write operation on register T [j] in epoch e i . When this operation terminates, a value has already been written in T [i] by definition of e i . Lemma 4 then implies that the next write operation by p (if any) is performed on some register T [j ′ ] such that j ′ > i. Lemma 5 bellow captures precisely this observation. Lemma 5. Denote by op, op ′ two write operations performed by the same process p. Suppose that:

(1) op occurs in e i , (2) op ′ is a write on register T [j] with j = i, and (3) op precedes op ′ . Then, j > i.

Proof. By Lemma 4, p reads from T [j] immediately before executing op ′ , and this read operation returns ⊥. Let op ′′ denote that operation. It follows from the third condition of the Lemma that op ′′ occurs after op, which in turn occurs after some non-⊥ value has been written in T [i ′ ] for each i ′ ≤ i (By definition of e i , and the fact op occurs in e i .). Since the read operation op ′′ performed on T [j] returns ⊥, we conclude that j > i.

Consider a round number r, and a value v. We say that value v is committed at round r if there exists a process p that writes v in D (line 17) while it is executing round r. Observe that in such a case, v is the estimate of p, and v has been written in T [r] (by p itself or some other process). Note moreover that for each decided value v, there exists a round during which v is committed.

The following lemma is central to the proof of the agreement property. Informally, this lemma says that if some process writes a value v in the decision register D while executing round r, no other value than v can be written to T [r]. Lemma 6. Let v be a value, and R be a round number such that v is committed at round R. For every value v ′ written in

T [R], it holds that v ′ = v.
The agreement property then follows by combining Lemma 1 and Lemma 6, and observing that every decided value has been committed.

Lemma 7 (Agreement).

No two process decide different values.

Proof. Let v and v ′ be two decided values (at line 21). By the code of Algorithm 1, v and v ′ have been previously written in D (at line 17). Hence, v and v ′ are committed at some round, say, r and r ′ respectively. Without loss of generality, assume that r ≤ r ′ . Let p ′ be a process that writes v ′ in D in round r ′ . Observe that v ′ is the estimate of p ′ in round r ′ . Therefore, v ′ has been written in T [r ′ ], either by p ′ (at line 7) or by some other process (in the latter case, v ′ was read by p ′ at line 6). As r ≤ r ′ , it follows from Lemma 1 that v ′ is written in T [r] as well. Since v is committed at round r, we conclude by Lemma 6 that v = v ′ . The rest of this section is devoted to the proof of Lemma 6. We proceed by contradiction. We name H the following assumption:

There exists a round R such that two write operations with parameters u = v are performed on T [R + K] and v is committed in round R + K.

In the following, we show that to satisfy assumption H the system must consist of at least n + 1 processes.

Denote by R the round number appearing in assumption H. For each i, j, 1 ≤ i, j ≤ K, note W i j the set of processes that perform a write operation to register T [R + j] during epoch e i . More precisely, a process p belongs to W i j if and only if there exists a write operation to T [R + j] by p which occurs in e i . By the definition of epochs, we know that if j > i, then W i j = ∅. The three lemmata below further precise how the sizes of the W i j 's and the round numbers are related.

Lemma 8.

If assumption H holds, then: ∀i, Clearly, this operation occurs in epoch e R+i ′ , for some i ′ ≥ i. Suppose for the sake of contradiction that i ′ > i. Hence, the first time v is written in T [R + i], a value has already been written in T [R + i + 1]. Let p be the process that performs this first write of v in T [R + i + 1]. As v is written to T [R + K], p must exist by Lemma 1. Denote w p (R + i+ 1) the write operation of p. According to the code of Janus we know that: (1) p performs that operation while it is executing round R + i + 1 (line 7), (2) w p (R + i + 1) is preceded by a read operation of T [R + i + 1] (denoted r p (R + i + 1)) by p that returns ⊥ , and (3) in round R + i, there is a read operation from T [R + i] that returns v or a write of v by p to T [R + i]. Denote by op p (R + i) this last operation, and op p (R + i), r p (R + i + 1), w p (R + i + 1) the operations that occur in this order. Moreover, op p (R + i), which reads or writes v in T [R + i] occurs in epoch e R+i ′′ for some i ′′ ≥ i ′ , since the write of v in T [R + i] occurs in e R+i ′ . Therefore, operation r p (R + i + 1) occurs after a write in T [R + i + 1], from which we conclude that r p (R + i + 1) returns a non-⊥ value. It thus follows by Lemma 4 that p does not write in T [R + i + 1] : a contradiction.

1 ≤ i < K, |W i i | ≥ 2.
We have shown that a write of v in T [R + i] occurs in epoch e i . A similar argument applied to value u yields that a write of u in T [R + i] occurs in e i . Since each process does not write twice in the same register, |W i i | ≥ 2.

Lemma 9.

If assumption H holds, then : ∀i, j :

1 ≤ i < K and 1 ≤ j < i, |W i j | ≥ 1.
Proof. We start by establishing that two read operations that return v and u respectively occur in e i .

As v is written in T [R + K], v is also written in T [R + i + 1] (Lemma 1). Let p the process that performs the first write of v in T [R + i + 1]. By the code, p executes round R + i before performing that write operation, and v is the estimate of p in that round. At the beginning of round R + i, p either reads v in T [R + i] or writes v in T [R + i]. Moreover, the read operation on T [R + i + 1] performed by p at the beginning of round R + i + 1 returns ⊥ (Otherwise p does not perform a write operation on T [R + i + 1]). Therefore, every operation performed by p while it is executing round R + i occurs in epoch e R+i .

In particular, the read of T [R + j] performed by p at line 10 occurs in e R+i . This read must return v. Otherwise, p writes true in C[R + i], and this operation occurs in e R+i . As no process ever writes false in C[R + i], every read operation performed on C[R + i] that occurs in later epochs return true. Consider a process p ′ executing round R + K. p ′ reads C[R + i] at line 15. This read operation occurs after a write operation has been performed on T [R + K], so it occurs after the end of epoch e R+i . Hence, that operation returns true and thus p ′ cannot write in D in that round. Therefore, no value is committed in round R + K, contradicting assumption H.

Similarly, by considering the process that performs the first write of u in T [R + i + 1], we get that a read operation of T [R + j] that returns u occurs in e R+i .

Finally, as there are two read operations of T [R + j] returning two different values occur in e i , there must exist a write operation on T [R+ j] that occurs in e i . We thus conclude that W i j = ∅.

Lemma 10. Suppose that assumption H holds. Let i, i ′ , j, j ′ such that

1 ≤ i ≤ i ′ < K and 1 ≤ j < i, 1 ≤ j ′ < i ′ . W i j ∩ W i ′ j ′ = ∅ ⇒ (i = i ′ ∧ j = j ′ ) ∨ (i < j ′ ) Proof. Let p ∈ W i j ∩ W i ′ j ′ .
By definition, a write operation by p occurs in e i and e i ′ . Either i = i ′ and j = j ′ or, by Lemma 5, i < j ′ .

We are now ready to prove Lemma 6.

Proof of Lemma 6. Assume for the sake of contradiction that assumption H is satisfied, and consider the following set:

S = (i, j) : K -1 2 ≤ i ≤ K -1, 1 ≤ j ≤ K -1 2
In what follows, we count the total number of processes that appear in the union of the sets W i j , where (i, j) ∈ S, then we show that this union includes at least n + 1 distinct processes.

Let (i, j) = (i ′ , j ′ ) ∈ S such that i ≤ i ′ . By definition of S, i ≥ j ′ and thus it follows from Lemma 10 that W i j ∩ W i ′ j ′ = ∅. Hence,

(i,j)∈S W i j = (i,j)∈S |W i j |
Moreover, It follows from Lemmas 8 and 9 that |W i j | ≥ 1 for each (i, j) ∈ S and

|W i i | ≥ 2 for each (i, i) ∈ S. Therefore, (i,j)∈S W i j ≥ K -1 2 • K -1 2 + 1 shared objects ∀r > 0 : J[r][1.
.c] is an array of c copies of Janus ∀r > 0 : AC[r] is an adopt-commit object ∀r > 0 : Overview of the algorithm. The algorithm, described in Figure 2, proceeds in asynchronous rounds. Each round is divided in two phases, an agreement phase in which each group of homonym processes agree on a common value, and a conciliation phase in which processes check whether every group agrees on the same value.

V [r][1..c]
The agreement phase of round r is implemented by c instances of the Janus algorithm that we note J[r][1], . . . , J[r][c]. As in the Janus algorithm, each process maintains an estimate stored in the local variable est. Processes with identity id propose their estimate to the same instance of Janus J[r][id] (line 4). The array V [r][1..c] is then used to store the decisions that occur (if any) in each of the c instances J[r][1..c] (line 5). This completes the agreement phase of round r.

Note that each instance of Janus is implemented with its own collection of registers. Processes however share a single failure detector AΩ. This means that a given instance of Janus might not progress if no process participating in this instance is elected by the failure detector. Nevertheless, if every correct process participates in at least one of the Janus instances of round r, termination is ensured in at least one instance, namely the instance J[r][id], where id is the identity of the eventual leader. The conciliation phase of round r is implemented by a single adopt-commit object denoted AC[r]. A process p with identity id that has previously obtained a decision d from the instance of Janus J[r][id] and has written this value to the register V [r][id] checks whether it is safe to decide this value. To do so, it proposes its identity to the adopt-commit object AC[r] (line 6). Let (b, id ′ ) denote the response of the object obtained by p. p first adopts the value it reads from V [r][id ′ ] as its new estimate (line 7). Note that the read operation of V [r][id ′ ] returns a non-⊥ value. This is because by the validity property of adopt-commit, a process p ′ with identity id ′ must have proposed its identity to AC[r] before p obtains the response (b, id ′ ). In addition, before accessing AC[r], p ′ must have written a value to V

[r][id ′ ].
Second, if b = commit , p then writes its estimate in the shared register DD, indicating that this value can be safely decided. Indeed, by the agreement property of adopt-commit, every propose() operation to AC[r] returns (adopt , id ′ ) or (commit , id ′ ). Hence, as a unique value v is written in V [r][id ′ ], the estimate of each process that completes round r is equal to v. It thus follows that v is the only value that may be written to DD in round r and any subsequent round.

Termination relies on the underlying failure detector AΩ. The eventual leadership property ensures that after some time τ , a single correct process considers itself as a leader. Let id denote the identity of this eventual leader. Observe that, by the code of Janus, a process participating in the execution of an instance of Janus does not take write steps unless it considers itself as a leader (Figure 1, line 3). Therefore, no decisions occur in every instance J[r][id ′ ] that starts after τ if id ′ = id. On the other hand, every instance J[r ′ ][id], r ′ ≥ 1 eventually produces a decision because the set of processes that participate in these instances includes the eventual leader. Consequently, if each round r instance of Janus starts after τ , only process with identity id may access the object AC [r]. Since they all propose the same value, namely id, it follows from the convergence property of adopt-commit that they get back (adopt, id). This implies that a value is eventually written to the decision register DD, and termination follows.

Complexity. Since at most nc + 1 processes participate in each instance of Janus (nc + 1 is the maximal size of a group of homonym processes), the parameter K is set to 2 √ nc + 1 + 1 in each instance. Values proposed to objects AC[r] are always taken from the set of available identities {1, . . . , c}. Each adopt-commit object is thus implemented by the optimal algorithm by Aspnes and Ellen [START_REF] Aspnes | Tight bounds for anonymous adopt-commit objects[END_REF]. A process executing solo, and elected leader by the failure detector from the beginning of the execution, decides after participating in one instance of Janus, and performing one propose() operation on an adopt-commit object. In addition, it performs two write operation (at lines 5 and 8). Therefore, in solo executions, the individual write complexity equals to O( √ nc + 1 + log c log log c ) and the individual step complexity equals to O(nc + 1 + log c log log c ).

Proof. The correctness of the algorithm described in Figure 2 is presented in this section. In the following, we say that value v is the estimate of process p at the end of round r if process p updates its local variable est with value v at line 7 while executing round r.

Lemma 13. Suppose that process p executes round r. Let v denote its estimate at the end of round r. v is the estimate of some process p ′ at the end of round r -1.

Proof. Consider the array of registers V [r][1..c]. By the code, every value v ′ written in this array is a value decided in one of the instances of Janus J[r][1], . . . , J[r][c] (lines 4-5). As each value proposed in any of these instances is some process' estimate at the end of round r -1, it follows from the validity property of consensus that every value written in V [r] is the estimate of some process at the end of round r -1. Before updating its estimate to value v, process p obtains a response, say (b, id ′ ), from the adopt-commit object AC[r]. v is then the value read by p from the register V [r][id ′ ]. By the validity property of adopt-commit, a process p ′ with identity id ′ must have previously invoked a propose() operation on object AC[r]. Note that, by the code (line 5), process p ′ writes a value in V [r][id ′ ] before accessing the adopt-commit object AC[r]. Therefore, v = ⊥ and v is thus the estimate of some process at the end of round r -1.

Lemma 14 (Validity and agreement). Every decided value is a proposed value, and no two processes decide different values.

Proof.

• Validity. Let v denote a decided value. By the code (lines 10-11), v is written to the register DD in some round r by some process p. The value written by p is its estimate at the end of round r. It thus follows from Lemma 13 that v is the estimate of some process at the end of round r -1. As the estimate value of each process p is initially its proposal, we conclude by induction that v is a proposed value.

• Agreement. As observed above, every decided value is written to the register DD. We show that no two distinct values are written to DD. We say that a value v is written to DD in round r if there exists a process p that writes v in DD while it is executing round r.

Denote by R the first round in which a value is written to DD. We show that no two distinct values can be written to DD in round R.

v = v ′ .
Consider some process q that updates its estimate with value v ′′ at line 7 in round R. Denote by (b, id ′′ ) the response it gets back from the adopt-commit object AC[R]. v ′′ is therefore the value read by q from the register

V [R][id ′′ ].
As a propose() operation performed on AC[R] returns (commit , id), it follows from the agreement property of adopt-commit that id ′′ = id. Moreover, as we have seen above, no two distinct values are written to J[R][id]. We thus have that v ′′ = v. This establishes that, for each process p that completes round R, the estimate of p at the end of that round is v. We thus conclude from Lemma 13 that no value = v is written to DD in any round > R, and agreement follows.

Lemma 15 (Termination). Every non-faulty process eventually decides.

Proof. Assume for contradiction that some non-faulty process does not decide. This means that no value v = ⊥ is written to DD and that no process decides. By the eventual leadership property of the failure detector class AΩ, there is a correct process p and a time τ such that each AΩ-query() performed after τ returns true if and only if the invoking process is p. Let id denote the identity of p. Fix some round R that starts later than τ . Notice that process p completes every round r ≤ R. As p is a correct process and does not decide, only a propose() operation that does not terminate may prevent p from completing round r. Adopt-commit objects are wait-free, therefore the propose() operation performed by p on AC[r] terminates. Moreover, an instance of Janus J[r][id ′ ] is guaranteed to terminate if among the processes that participate in that instance, one process is the eventual leader designated by the underlying failure detector AΩ. As process p is the eventual leader, every instance of Janus in which it participates eventually terminates.

Consider now round R. We show that no instance of Janus J[R][id ′ ], with id ′ = id terminates. Suppose that some process invokes J[R][id ′ ].propose(). As (1) only processes with identity id ′ = id participate in this instance, and (2) this instance starts after time τ , every query to AΩ performed in this instance returns false. It thus follows from the code of Janus (Figure 1, line 3) that the instance [R][id ′ ] never terminates, e.g., no invocation of J

[R][id ′ ].propose() terminates.
Hence, in round R, only the consensus instance J[R][id] terminates. Consequently, every

propose() operation performed on the object AC[r] has input id. By the convergence property of adopt-commit, every such operation that terminates returns (commit , id). In particular, the propose() operation by process p terminates. It thus follows from the code (line 8) that process p write a value in DD. This is a contradiction.

Next theorem captures the correctness of the algorithm described in Figure 2. Its proof directly follows from Lemmas 14 and 15.

Theorem 16. The algorithm described in Figure 2, when instantiated with a failure detector of the class AΩ solves consensus in an n-processes, homonymous shared memory system with identifiers {1, . . . , c}.

Related work

Attiya et al. [START_REF] Attiya | Computing in totally anonymous asynchronous shared memory systems[END_REF] characterized failure-free tasks that are solvable using registers when the number of processes n is unknown. In particular, the authors show, using bivalence and covering arguments, that consensus in such an environment requires more than Ω(log n) atomic registers, and at least Ω(log n) total work. Recently, Aspnes and Ellen [START_REF] Aspnes | Tight bounds for anonymous adopt-commit objects[END_REF] proved that the individual step complexity of adopt-commit object in anonymous shared-memory is Θ(min ( log m log log m , n)), where m is the number of different values that might be proposed to the object. Because consensus satisfies the specification of an adopt-commit object [START_REF] Gafni | Round-by-round fault detectors: unifying synchrony and asynchrony[END_REF], this lower bound also holds for the consensus object.

Guerraoui and Ruppert [START_REF] Guerraoui | Anonymous and fault-tolerant shared-memory computing[END_REF] studied the computational power of shared memory distributed systems in the presence of both anonymity and failures. They propose constructions for several fundamental abstractions: wait-free timestamping and snapshots, and obstruction-free consensus. In particular, the authors depict an anonymous binary consensus algorithm having a step complexity of O(1). When m is known, this algorithm solves anonymous consensus in O(log m) write operations and O(log m) individual work. Delporte-Gallet and Fauconnier [START_REF] Delporte | Two consensus algorithms with atomic registers and failure detector Ω[END_REF] proposed an anonymous consensus which relies on failure detector AΩ and a weak set abstraction. If m is known, this algorithm solves consensus in O(log m) individual work and O(1) writes.

Abrahamson [START_REF] Abrahamson | On achieving consensus using a shared memory[END_REF] studied binary consensus in the probabilistic-write model with eponymous processes, when identities are only used to label registers. Recently, Aspnes [START_REF] Aspnes | A modular approach to shared-memory consensus, with applications to the probabilistic-write model[END_REF] proposed a consensus algorithm for the probabilistic-write anonymous model which solves consensus in O(log m) individual work. The algorithm is based on the decomposition of consensus into two distinct components: an adopt-commit object which detects agreement, and a conciliator, which ensure agreement with some probability. Aside from their lower bound result, the authors of [START_REF] Aspnes | Tight bounds for anonymous adopt-commit objects[END_REF] proposed two asymptotically optimal implementations of adopt-commit objects: a O( log m log log m ) solution which requires that m is known, and a O(n) solution which solves the problem without any assumptions over m. During a solo execution, the latter algorithm writes O(n) different registers.

The Janus algorithm we depicted in Section 3 solves anonymous consensus in O(n) individual work, and O( √ n) write operations, a result which matches the lower bound of [START_REF] Aspnes | A modular approach to shared-memory consensus, with applications to the probabilistic-write model[END_REF] and further improves the write complexity of anonymous consensus.

The notion of partial anonymity in which some processes may share the same identifier was first introduced by Yamashita et al. [START_REF] Yamashita | Leader election problem on networks in which processor identity numbers are not distinct[END_REF] in the context of the leader election problem. The term homonyms was coined recently by Delporte et al. [START_REF] Delporte-Gallet | Byzantine agreement with homonyms[END_REF]. In this work, the authors study the Byzantine consensus problem in message passing systems when a limited number of identities is available. They prove several tight bounds on the number of Byzantine processes that can be tolerated depending on the asynchrony of the system and the number of available identifiers c.

Conclusion

This paper has presented two efficient consensus algorithms for anonymous and partially anonymous asynchronous shared memory systems. Both algorithms do not impose restrictions on the set V from which proposed values are taken. The complexity depends solely on the number of processes n and the number of available identifiers c in the partially anonymous case. To the best of our knowledge, the generalized algorithm presented in Section 4 is the first non-trivial consensus implementation for shared memory homonymous systems.

Of note, by limiting the Janus algorithm to its first K rounds and removing the queries to the failure detector, we obtain an anonymous adopt-commit implementation whose individual write complexity is O( √ n), while retaining an optimal O(n) individual work. With respect to the write complexity, this is an improvement over existing implementations. The paper has focused on consensus algorithms for which the set of input values V is not restricted. An interesting avenue for future research is to investigate the interplay between the size of the input set m, the number of available identifiers c, the number of processes n, and the number of distinct values k that can be decided, as well as to understand their impacts on the complexity of shared-memory agreement algorithms.

  shared variables ∀r > 0 : T [r] is a multivalued MWMR atomic register, initially ⊥ ∀r > 0 : C[r] is a binary MWMR atomic register, initially false D is a multivalued MWMR atomic register, initially ⊥ propose(v) (1) est ← v; rnd ← 0; start T1; start T2; task T1 : (2) while (true) do (3) if (AΩ-query()) then (4)

Lemma 4 .

 4 Suppose that p performs a write operation op on T [i]. The last operation preceding op performed by p is a read on T [i], and the value returned by that operation is ⊥.

Proof.

  By assumption H, at least two values v and u are written in T [R + K]. It follows from Lemma 1 that v and u must have been written in T [R + i] for each i such that 1 ≤ i < K. It remains to show that such a write operation with parameter v (resp. u) occurs in e i . Let us consider the first write of v in T [R + i].

Figure 2 :

 2 Figure 2: Consensus with homonyms, code for processes with identity id

  is an array of c MRMW registers, initially ⊥ DD is a multivalued MWMR atomic register, initially ⊥

	propose(v)
	(1) est ← v; rnd ← 0; start T1; start T2;
	task T1 :
	(2) while (true) do
	(3)	rnd ← rnd + 1;
	(4)	est ← J[rnd][id].propose(est);
	(5)	V [rnd][id] ← est;
	(6)	(b, id ′ ) ← AC[rnd].propose(id);
	(7)	est ← V [rnd][id ′ ];
	(8)	if b = commit then DD ← est endif
	(9) end while
	task T2 :
	(10) repeat d ← DD until d = ⊥
	(11) stop T1; decide(d)

  Suppose that two values v, v ′ are written to DD in round R by processes p and p ′ respectively. By the code, processes p and p ′ obtain responses (commit , id) and (commit , id ′ ) respectively from the adopt-commit object AC[R]. Moreover, we have id = id ′ by the agreement property of adopt-commit. Hence, values v and v ′ are both read from the same register V [R][id]. Since each value written to V [R][id] is the decision of the same consensus instance, namely J[R][id], we conclude that

In Roman religion and mythology, Janus is the god of gates. Most often he is depicted as having two heads, facing opposite directions (Wikipedia). The choice of the name is explained by the fact that each process in our algorithm has to look in two directions: forward to check if another process has already started a new round, and back to check if another process concurrently executed the K past rounds.

⊥ is a special value that is never proposed by the processes.

Finally, as K = 2 • ⌈ √ n⌉ + 1, we get

Therefore, assuming that H is satisfied, we have exhibited a set of n + 1 distinct processes : a contradiction. Consequently, H cannot be satisfied, from which we conclude that no value different from v is written in T [R], as desired.

Theorem 11. The Janus algorithm described in Figure 1, when instantiated with a failure detector of the class AΩ solves consensus in an n-processes, anonymous shared memory system.

Proof. Immediately follows from Lemmas 2, 3 and 7.

The following theorem proves that the step complexity of Janus is O(n), which is optimal [START_REF] Aspnes | Tight bounds for anonymous adopt-commit objects[END_REF], and that its write complexity equals to O( √ n).

Theorem 12. The Janus algorithm has a step complexity of O(n), and a write complexity of

Proof. Consider a solo execution of some process p. During this execution, p executes K = 2⌈ √ n⌉+1

rounds, then decides. Name {1, . . . , K} the rounds executed by p, and consider some round i.

According to the code of Algorithm 1, during round i process p executes a single write (line 7), and reads 3i + 1 shared registers (lines 5, 9 to 11, and 14 to 16). As a consequence, the step complexity of Janus is O(n), and its write complexity equals O( √ n).

The case of homonymous systems

In an homonymous system, c, 1 ≤ c ≤ n identities are available [START_REF] Delporte-Gallet | Byzantine agreement with homonyms[END_REF][START_REF] Yamashita | Leader election problem on networks in which processor identity numbers are not distinct[END_REF]. Each process has an identifier in the range {1, . . . , c}. Processes that share the same identifier are said to be homonym, and for each i ∈ {1, . . . , c}, the number of processes with id i is at least 1 (and thus at most nc + 1).

In this section we present a consensus algorithm for homonymous shared-memory systems that tolerates up to n -1 process failures. As in the case of anonymous systems, the algorithm relies on a failure detector of the class AΩ and the set of values that can be proposed is unbounded. The algorithm is built in a modular way from several copies of the Janus algorithm and an efficient implementation of m-valued adopt-commit objects due to Aspnes and Ellen [START_REF] Aspnes | Tight bounds for anonymous adopt-commit objects[END_REF].

Adopt-commit. An adopt-commit object [START_REF] Gafni | Round-by-round fault detectors: unifying synchrony and asynchrony[END_REF] is a shared object that supports a single operation denoted propose (v) where v is a value taken from some set V. Every invocation of propose (•) returns a response of the form (b, v ′ ) where b ∈ {commit , adopt } and v ′ ∈ V such that the following properties hold: (Termination) Every invocation of propose (•) by a correct process terminates; (Validity) If (b, v) is returned, then some process previously invoked propose (v); (Agreement) If (commit , v) is returned, then every decision has the form ( * , v); (Convergence) If every process proposes the same value v, then (commit , v) is the only possible decision.

An efficient crash-tolerant asynchronous implementation of m-valued adopt-commit objects from multi-reader multi-writer registers in anonymous system is presented by Aspnes and Ellen in