Carole Delporte-Gallet

Hugues Fauconnier

Sam Toueg

A separation of (n -1)-consensus and n-consensus in read-write shared-memory systems

A fundamental research theme in distributed computing is the comparison of systems in terms of their ability to solve basic problems such as consensus that cannot be solved in completely asynchronous systems. In particular, in a seminal work [?], Herlihy compares shared-memory systems in terms of the shared objects that they have: he proved that there are shared objects that are powerful enough to solve consensus among n processes, but are too weak to solve consensus among n + 1 processes; such objects are placed at level n of a wait-free hierarchy. The importance of this hierarchy comes from Herlihy's universality result: intuitively, every object at level n of this hierarchy can be used to implement any object shared by n processes in a wait-free manner.

As in [?], we compare shared-memory systems with respect to their ability to solve consensus among n processes. But instead of comparing systems defined by the shared objects that they have, we compare readwrite systems defined by the process schedules that they allow. These systems capture a large set of systems, e.g., systems whose synchrony ranges from fully synchronous to completely asynchronous, several systems with failure detectors, and "obstruction-free" systems. In this paper, we consider read-write systems defined in terms of process schedules, and investigate the following natural question: For every n, is there a system of n processes that is strong enough to solve consensus among every subset of n -1 processes in the system, but not enough to solve consensus among all the n processes of the system? We show that the answer to the above question is "yes", and so these systems can be classified into hierarchy akin to Herlihy's hierarchy.

Motivation and related work

A fundamental research theme in distributed computing is the comparison of systems in terms of their ability to solve basic problems such as consensus or k-set agreement that cannot be solved in completely asynchronous systems [?, ?, ?, ?, ?, ?, ?, ?, ?, ?, ?]. In particular, in a seminal work [?], Herlihy compares shared-memory systems in terms of the shared objects that they have: he proved that there are shared objects that are powerful enough to solve consensus among n processes, but are too weak to solve consensus among n + 1 processes; such objects are placed at level n of a wait-free hierarchy. The importance of this hierarchy comes from Herlihy's universality result: intuitively, every object at level n of this hierarchy can be used to implement any object shared by n processes in a wait-free manner.

As in [?], in this paper we compare shared-memory systems with respect to their ability to solve consensus among n processes. But instead of comparing systems defined by the shared objects that they have, we compare systems (with shared registers) defined by the process schedules that they allow, as we explain below.

First, note that several types of read-write shared-memory systems, e.g, asynchronous, partially synchronous and synchronous systems, can be defined by the set of process schedules that they allow. [START_REF]σ is an infinite sequence of the form ∞ i=1 [{1, 2} ℓ {1, 3} ℓ[END_REF] For example, a completely asynchronous system is one where every process schedule can occur. Similarly, a partially synchronous system is one where the process schedules satisfy some timeliness or "fairness" conditions [?, ?, ?] which effectively define the set of process schedules that are allowed. Perfectly synchronous systems can also be defined by the set of process schedules that are allowed. Furthermore, several systems with failure detectors [?] are equivalent to systems defined in terms of process schedules: for several well-known failure detectors D (including P, ✸P, S and ✸S) an asynchronous system augmented with D is equivalent to a system where schedules satisfy some fairness conditions [?]. [START_REF]σ = σ ′ for some finite schedule σ ′ . Since σ is finite it is trivially ℓ-solo[END_REF] Finally, obstruction-free algorithms work in systems with a specific set of process schedules, namely, schedules where some process eventually executes solo [?].

Thus, shared-memory systems defined in terms of process schedules capture a large set of systems, e.g., systems whose synchrony ranges from fully synchronous to completely asynchronous, several systems with failure detectors, and "obstruction-free" systems. In this paper, we consider such systems and investigate the following natural question: For every n, is there a system of n processes that is strong enough to solve consensus among every subset of n -1 processes in the system, but not enough to solve consensus among all the n processes of the system? If this is true, it would imply that these systems can be classified into hierarchy akin to Herlihy's hierarchy.

The answer to the above question is not obvious. In [?] it is shown that if a failure detector D is powerful enough to solve consensus among every subset of n -1 processes in a system of n processes, then it is powerful enough to solve consensus among all the n processes in the system. Since [?] shows that several systems with failure detectors are equivalent to systems with sets of schedules, it is tempting to conjecture that the answer is "no":

In this paper we show that the answer to the above question is "yes". More precisely, we prove that for every n ≥ 2, there is a read-write shared-memory system S of n processes such that: (a) consensus can be solved for every subset of n -1 processes of S, and (b) consensus cannot be solved for the n processes of S. It is worth noting that the positive result (a) holds even if S has only a bounded number of bounded-size registers, while the impossibility result (b) holds even if S has an unbounded number of unbounded-size registers.

Model

We consider shared-memory systems of processes with SWMR multivalued atomic registers. Processes proceed by executing atomic events: in each event, a single process can read or write a single register. In the following, P denotes a set of processes, formally P ⊆ N = {1, 2, . . .}.

Process schedules

A schedule σ of a set of processes P is a finite or infinite sequence where each element of the sequence is a process in P , e.g., σ = 243125434253335 . . . is a schedule of P = {1, 2, 3, 4, 5}. Each occurrence of a process p in a schedule σ is called a step of p (in σ). A process is correct in a schedule σ if it occurs infinitely often in σ, otherwise it is faulty (or crashes) in σ.

Roughly speaking, a schedule σ is k-solo, if σ has a process that runs solo for at least k consecutive steps infinitely often. More precisely, a schedule σ of a set of processes P is k-solo if σ is finite or there is a process p ∈ P such that σ contains an infinite number of subsequences consisting of k or more consecutive steps of p (and only of p). Note that if a schedule is k-solo then it is also (k -1)-solo, and every schedule is trivially 1-solo.

Systems and subsystems

Intuitively, a system S is described by the set P of processes in the system and the set Σ of schedules of P that can occur in this system. More precisely, a system S is a tuple [P, Σ], where P is a non-empty set of processes and Σ is a non-empty set of schedules of P . We say that σ is a schedule of system S = [P, Σ] if σ ∈ Σ. Moreover,

S ′ = [P ′ , Σ ′ ] is a subsystem of S = [P, Σ] (denoted S ′ ⊆ S) if P ′ ⊆ P and Σ ′ ⊆ Σ. Finally, S ′ = [P ′ , Σ ′ ] is a proper subsystem of S = [P, Σ] (denoted S ′ ⊂ S) if S ′
is a subsystem of S and P ′ ⊂ P or Σ ′ ⊂ Σ.

In the following definitions, P is a set of processes and Q is a subset of P . If σ is a schedule of P , we denote by σ(Q) the subsequence of σ obtained by keeping only the steps of the processes that are in Q; e.g., if σ = 243125434253335 and Q = {2, 5} then σ(Q) = 225255. Note that σ(Q) is a schedule of Q. If Σ is a set of schedules of P , we denote by Σ(Q) the set of schedules obtained by keeping only the steps of the processes that are in Q in the schedules of Σ; more precisely:

Σ(Q) = {σ ′ | ∃σ ∈ Σ such that σ ′ = σ(Q)}.
Note that all the schedules of Σ(Q) are schedules of Q.

Let S = [P, Σ] be a system and Q be a subset of P . We denote by S(Q) the subsystem of S obtained by keeping only the steps of the processes that are in Q from S; more precisely,

S(Q) = [Q, Σ(Q)]. Note that if Q is a proper subset of P , then S(Q) is a proper subsystem of S.

Systems A n and S k n

We now define some systems that are central to our results. Henceforth, P n is the set of n processes {1, 2, . . . , n} and Σ n is the set of all the schedules of P n .

• A n = [P n , Σ n ] is the asynchronous system of the processes in P n .

• For k ≥ 1, S k n = [P n , Σ k n ] where Σ k n = {σ | σ ∈ Σ n and for all the proper subsets Q of P n : σ(Q) is k-solo}.
Observation 1 Let Q be any proper subset of P n . All the schedules of the subsystem S k n (Q) of S k n are k-solo schedules of Q.

To see this, consider any schedule σ

′ of S k n (Q) = [Q, Σ k n (Q)], i.e., σ ′ ∈ Σ k n (Q). So σ ′ = σ(Q) for some σ ∈ Σ k n . By the definition of Σ k n , σ(Q) (and therefore σ ′ ) is a k-solo schedule of Q.
Note that:

1. For all k ≥ 1, S 1 n = A n , the asynchronous system of the processes in P n = {1, 2, . . . , n}. This is because for every schedule σ of P n and every proper subset Q of P n , the schedule σ(Q) is trivially 1-solo.

2. For all k ≥ 1, S k 2 = A 2 , the asynchronous system of the processes in P 2 = {1, 2}. This is because for every schedule σ of P 2 = {1, 2} and every proper subset

Q of {1, 2} (namely, Q = {1}, Q = {2} or Q = ∅) the schedule σ(Q) is trivially k-solo for all k ≥ 1.
3. For all n ≥ 3, and all k ≥ 2, S k n ⊂ A n . To see this, let k ≥ 2 and consider the infinite schedule σ = 123123123123 . . . etc. of P n = {1, 2, . . . , n}. This is a schedule of A n , but it is not a schedule of S k n . This because for the proper subset

Q = {1, 2} of P n = {1, 2, . . . , n}, the schedule σ(Q) = 12121212 . . . etc. is not k-solo for k ≥ 2, so σ is not a schedule of S k n .
4. For all n ≥ 3, A 2 ⊆ S 2 n . To see this, consider the infinite schedule σ = 1212121212 . . . etc. This is a schedule of A 2 , but it is not a schedule of S 2 n . This is because, for all n ≥ 3, Q = {1, 2} is a proper subset of P n = {1, 2, . . . ., n} but σ(Q) = 1212121212 . . . etc. is not 2-solo.

For all n ≥ 3, and all

k ≥ 1, S k+1 n ⊂ S k n . To see this, let σ ∈ S k+1 n . For every Q ⊂ P n , σ(Q) is (k + 1)-solo, and so σ(Q) is also k-solo; thus σ ∈ S k n . Furthermore, consider the schedule σ = ∞ i=1 (1 k 2 k . . . n k ). It is clear that for every Q ⊂ P n , σ(Q) is k-solo, and so σ ∈ S k n ; but for Q = {1, 2}, σ(Q) = 1 k 2 k 1 k 2 k . . . 1 k 2 k . . . is not (k + 1)-solo, and so σ ∈ S k+1 n .
To provide some intuition about the systems S k n that we defined, we now give a few simple examples of schedules that are in S k n and are not in S k n . 3 To describe these schedules we use the following notation. For two processes p and q in P n = {1, 2, . . . , n}, (pq) i denotes the sequence of steps pq repeated i times; for example (pq)3 is pqpqpq. Similarly, {p, q} i denotes any finite sequence of steps of processes p and q that contains at least i steps of p and at least i steps of q, in any order. For example, {p, q} 3 includes the sequences pqpqpq, pppqqqq and ppqqpq, but it does not include the sequence ppprqqq (because it contains a step of process r) or ppppqq (because it contains fewer than 3 steps of q). We start with some examples of schedules of system S k n (i.e., of schedules σ ∈ Σ k n ) for n ≥ 3:

(a) σ = ∞ i=1 [(12) k (13) k (14) k . . . (1n) k ]. Schedule σ ∈ Σ k n because it is a schedule of P n and for every proper subset Q of P n , the schedule σ(Q) is k-solo. To see this, assume Q is not empty (if Q = ∅, σ(Q) is trivially k-solo
because it is the empty schedule). There are two possible cases. If Q does not contains process 1, then, since Q is not empty, Q contains at least one process j ∈ {2, 3, . . . n}; since the sequence (1j) k appears infinitely often in σ and 1 ∈ Q, the sequence j k (i.e., k consecutive steps of process j) appears infinitely often in schedule σ(Q); thus σ(Q) is k-solo. If Q contains process 1, then, since Q is a proper subset of P n , some process j ∈ {2, 3, . . . n} is not in Q; since the sequence (1j) k appears infinitely often in σ and j ∈ Q, the sequence

1 k appears infinitely often in schedule σ(Q); thus σ(Q) is k-solo. Thus, in both cases σ(Q) is k-solo. (b) σ is any schedule of the form ∞ i=1 [{1, 2} k {1, 3} k {1, 4} k . . . {1, n} k ]. The proof that σ ∈ Σ k n is similar to the one given above. (c) σ = ∞ i=1 [(12) k (23) k (34) k . . . (n -2 n -1) k (n -1 n) k (n 1) k ].
It is easy to see that for every

Q ⊂ P n , the schedule σ(Q) is k-solo, so σ ∈ Σ k n .
The following schedule is not in system S k n , i.e., σ ∈ Σ k n , for any k ≥ 2 and n even, n ≥ 4 :

(a) σ = ∞ i=1 [(12) k (34) k . . . (n -3 n -2) k (n -1 n) k ].
To see that σ ∈ Σ k n , note that for the proper subset Q = {1, 2} of P n , the schedule σ(Q) = 121212121212 . . . is not k-solo for any k ≥ 2.

Consensus problem

Consider an algorithm A defined for some set of processes P . A schedule determines exactly the sequence of steps of the processes executing the algorithm. Then the set of runs of algorithm A for a system S = [P, Σ] is the set of all runs of A obtained when the processes of P execute A for Σ.

In the consensus problem each process has an initial value and must decide a value. We say that algorithm A solves the consensus in system S = [P, Σ] if and only if every run of A for S satisfies the following properties:

• (Agreement) If a correct process p decides v and a correct process q decides v ′ then v = v ′ ;

• (Integrity) If some correct process decides v then v is the initial value of some process.

• (Termination) Every correct process eventually decides some value.

By a slight extension we say that A solves the consensus for a subset Q of P in S = [P, Σ] if A solves the consensus in the subsystem S(Q).

We sometimes consider the uniform variant of the consensus. In the uniform consensus, each run has to ensure (i) (uniform agreement) if a process p decides v and a process q decides v ′ then v = v ′ , (ii) (uniform integrity) if some process decides v then v is the initial value of some process, and (iii) termination as before.

Main result statement and proof outline

Our main result is that for all n ≥ 2 there is a shared-memory system S of n processes that separates the problems of (1) solving consensus for n processes and (2) solving consensus for every proper subset of these processes.

More precisely, we show the following:

Theorem 2 For every n ≥ 2, there is a system S of processes P n such that:

(a) for every proper subset Q of P n , consensus can be solved in the subsystem S(Q) of S, and (b) consensus cannot be solved in S.

Proof outline. For n = 2, the proof is obvious. S is simply the asynchronous system of P 2 = {1, 2}, i.e., S = A 2 . By the well-known impossibility of result of [?, ?], consensus cannot be solved in S. Furthermore, for every proper subset Q of P 2 = {1, 2}, consensus can be trivially solved in the subsystem S(Q) of S since this system contains at most one process.

For n ≥ 3, the system S is defined as follows. Consider the algorithm B n for processes P n given in Section ??, this algorithm using snapshots may be rewritten into an algorithm B ′ n using only SWMR registers. Let ℓ be the number of steps that any process p ∈ P n takes to execute the main loop of this algorithm (i.e., Figure ??, lines ??-??) 2n + 1 times. From the code of this loop, it is clear that ℓ is well-defined: this is because (a) the code does not contain any "wait" statement, and (b) multi-writer snapshot used in the algorithm can be wait-free implemented with a bounded number of SWMR registers such that each scan or update of a process p terminates if p takes more than k steps alone for some k.

Definition 3 Let S = S ℓ n .
Recall that S ℓ n = [P n , Σ ℓ n ] where Σ ℓ n = {σ | σ ∈ Σ n and for all Q ⊂ P n : σ(Q) is ℓ-solo} (see Section ??). We show that S satisfies the two parts of Theorem ??, as follows.

Proof of Part (a): Let Q be any proper subset of P n . We claim that the algorithm B ′ n shown in Section ?? solves consensus in the subsystem S(Q) of S. To prove this, we show that the algorithm B ′ n satisfies the properties of consensus in every run of the processes in Q where either (a) all processes in Q crash (the corresponding schedule of Q is finite), or (b) there is a process in Q that executes at least ℓ consecutive steps solo infinitely often. In other words, the algorithm B ′ n solves consensus in every run of the processes in Q whose schedule is ℓ-solo. By Observation ??, every schedule of subsystem S(Q) of system S = S ℓ n is an ℓ-solo schedule of Q, thus the algorithm B ′ n solves consensus in S(Q). The detailed explanation and proof of algorithm B ′ n is given in Section ??. Proof of Part (b): We claim that consensus cannot be solved in system S. Suppose, for contradiction, that there is an algorithm C n that solves consensus in system S. Then we can show that consensus can be solved in the asynchronous system A 2 -contradicting the well-known impossibility result in [?, ?]. To solve consensus in A 2 , the two processes of A 2 can simulate the execution of the consensus algorithm C n by the n processes of P n in a system S ′ such that:

(1) S ′ is a subsystem of S = S ℓ n = [P n , Σ ℓ n ]. In particular, every schedule of S ′ is in also a schedule of S.

(2) If at least one of the two processes of system A 2 does not crash during their simulation of algorithm C n in system S ′ , then at least one of the n simulated processes in P n does not crash in the simulated run of C n in system S ′ .

Property (1), together with the assumption that C n solves consensus in S, ensures that every simulated run of C n in the subsystem S ′ of S also satisfies the properties of consensus. In particular, in each simulated run of C n in S ′ , all the simulated processes that are correct in this run reach a common decision.

Property (2) ensures that if at least one of the two processes in A 2 is correct, then at least one of the n processes in P n that they simulate, say process p, is also correct; by the above, p reaches a decision in the simulated run of C n in S ′ . So, every correct process in A 2 can wait until one of the simulated processes decides some value, and then adopt this common decision value.

Thus, by simulating the execution of C n in system S ′ ⊆ S, the two processes of A 2 can solve consensus in A 2 . This violation of the impossibility result of [?, ?] concludes the proof that consensus cannot be solved in S.

In Section ?? we show how the two processes of system A 2 simulate the execution of the consensus algorithm C n by the processes P n in system S ′ such that conditions (1) and ( 2) above hold.

Consensus algorithm

In this section we present an algorithm B ′ n in a system S = [P, Σ] where P is a set of n processes. We show that for some ℓ it achieves uniform consensus in any ℓ-solo schedules. Moreover for any Q ⊂ P , B ′ n solves the consensus in the subsystem S ℓ n (Q). For convenience, we first give B n an algorithm using multi-writer wait-free snapshot then we deduce from B n the existence of an algorithm B ′ n using only SWMR registers solving consensus in any ℓ-solo schedules. Algorithm B n (Figure ??) is an adaptation of obstruction-free consensus algorithm in [?]. It uses a 2n multiwriter snapshot array and terminates if at least one process runs alone during 2n + 1 iterations of the main loop. In algorithm B n we say that process decides value x if it executes Line ?? with variable v equal to x.

Describe informally the algorithm. Each process maintains a proposed value (variable propose) and tries to write its proposed value in a cyclic order in every cell of the snapshot array R. The proposed value is modified V iew := scan(R) following the following rules: initially it is the initial value of the process, then just after the process writes its proposed value in some cell of the snapshot array R, it scans R and if some value v is the value in a majority of cells of the returned array, the process adopts that value as proposed value. When all values in the snapshot array are the same, then the process decides this value.

8 if ∃v : ∀j(1 ≤ j ≤ 2n)V iew[j] = v 9 then /* one value in R */ 10 let v such that ∀j(1 ≤ j ≤ 2n) : v = V iew[j] 11 if decide == ⊥ 12 then 13 decide := v 14 else /* more than one value in R */ 15 if (∃v(v = ⊥) :| {j | (1 ≤ j ≤ 2n) ∧ v = V iew[j]} |> n 16 then / * a majority of cells of R contain v */ 17 let v (v = ⊥) such that (| {j | ∧(1 ≤ j ≤ 2n)) ∧ v = V iew[j]} |> n 18 prop := v 19 i := (i mod 2n) + 1
If some process decides value v, in the last scan made by this process all the 2n cells of the snapshot array are equal to v and then it can be proved that all the next scans of R will have a strict majority of cells with value v.

Hence the proposed value of any process that makes a scan after that will be v and then v is the only value that can be decided. Moreover if some process is running alone enough time it will be able to update all the cells of R with its proposed value and then it decides. Consider the body of the main loop of algorithm B n (Lines ?? to ??), if a process runs alone at least 2n + 1 successive iterations of the body of the main loop, after the scan of its first iteration its proposed value does not change and it updates during the next 2n iterations all cells of the snapshot array with this value. Then by the end of these 2n + 1 iterations it decides. As soon as some process decides, it is easy to verify that all correct processes decide.

Theorem 4 If some process runs alone during 2n + 1 successive complete iterations of the main loop, algorithm B n is a consensus algorithm.

PROOF. Due to the lack of space, we give the formal proof of this Theorem in Appendix (Section ??).

Algorithm B n uses a multi-writer snapshot array. Using the implementation of multi-writer snapshot with MWMR registers described in [?] and the implementation of MWMR registers with SWMR registers from [?], we can derive from B n an algorithm B ′ n using only SWMR registers. From Theorem ??, algorithm B ′ n is a consensus algorithm in which all correct processes terminate in any schedule such that some process takes enough atomic steps solo to run alone during 2n + 1 successive iterations of the main loop.

The algorithm in [?] gives a wait-free implementation of a multi-writer snapshot array from MWMR registers. For this algorithm there exists a constant C 1 such that each update or scan operation requires less than C 1 n 2 reads and writes to MWMR registers. Moreover, if the values written in the snapshot are bounded by some K there exists a function D 1 such that the values written in the MWMR registers are bounded by D 1 (K). they do so by simulating the execution of C n by the n processes of P n in a subsystem S ′ of S, such that if one of the processes in A 2 does not crash then at least one of simulated processes in P n does not crash. Henceforth, we denote by x and y the two processes of A 2 (this is to distinguish them from the n processes of P n = {1, 2, . . . , n} that they simulate).

In the following: (a) we first define the system S ′ and show that it is indeed a subset of system S, (b) we then show how the algorithm in Figure ?? executed by the two processes x and y of A 2 simulates runs of C n in system S ′ , i.e., the schedules of these runs are schedules of S ′ , and (c) finally we show that x and y solve consensus among themselves using this simulation algorithm.

Intuitively, the schedules of system S ′ are: (1) all the infinite schedules of the form ∞ i=1 [{1, 2} ℓ {1, 3} ℓ . . . {1, n} ℓ ],4 (2) all the finite prefixes of such schedules, and (3) all the finite prefixes of such schedules followed by p ∞ for some process p ∈ P n (i.e, an infinite sequence of steps of p). More precisely, let

Σ = {σ | σ is of the form ∞ i=1 [{1, 2} ℓ {1, 3} ℓ . . . {1, n} ℓ ]. Definition 7 S ′ = [P n , Σ ℓ n ]
where Σ ℓ n = {σ|σ ∈ Σ or there is a finite prefix σ ′ of a schedule in Σ such that σ = σ ′ or such that σ = σ ′ p ∞ for some p ∈ P n }.

Lemma 8 S ′ is a subsystem of system S.

PROOF. Since S

′ = [P n , Σ ℓ n ] and S = [P n , Σ ℓ n ], we must show that Σ ℓ n ⊆ Σ ℓ n . Recall that Σ ℓ n = {σ | σ ∈ Σ n and for all Q ⊂ P n : σ(Q) is ℓ-solo}. Let σ ∈ Σ ℓ n . Since σ is a schedule of P n , σ ∈ Σ n . To show that σ ∈ Σ ℓ n it suffices to prove that for all Q ⊂ P n , σ(Q) is ℓ-solo. Let Q any proper subset of P n . If Q is empty then σ(Q) is trivially ℓ-solo,
so assume that Q is not empty. There are three possible cases:

show that the schedules of these simulated runs are schedules of the system S ′ = [P n , Σ ℓ n ], i.e., they are either (1) infinite schedules of the form ∞ i=1 [{1, 2} ℓ {1, 3} ℓ . . . {1, n} ℓ ], or (2) finite prefixes of such schedules, or (3) finite prefixes of such schedules followed by p ∞ for some process p ∈ P n .

From the above and the termination condition of processs y's while loop of line ??, it is clear that y completes each execution of the while loop that it starts, unless it crashes or process x crashes (and stops incrementing P C [1]). Thus, unless x or y crash, process y executes an infinite number of iterations of the for-loop of line ??. Note that during its i-th iteration of this for-loop, process y simulates the steps of process p = 2 + (i -1)mod(n -1). So in the successive iterations of this for-loop, process y simulates the steps of the processes 2, 3, ...., n in round-robin order. Let t i be the time when process y starts its i-th iteration of the for-loop of line ??; t i is undefined if y never starts this iteration. From the above, we have the following:

Observation 10 If, for some k ≥ 1, t k is undefined then process x or y (or both) crash.

To show that x and y simulate schedules of S ′ , we consider the steps of the processes in P n that x and y simulate from time 0 (when x or y start executing the simulation algorithm) to time t 1 , from time t 1 to time t 2 , ..., from time t j to time t j+1 , ... until we reach a time t k that is undefined if such a time exists.

Note first that if t 1 is not defined, then y crashes before executing its first for-loop of line ??, so y never simulates any step. Since process x simulates only the steps of process 1, the resulting simulated schedule of P n is simply 1 ∞ or some finite prefix of 1 ∞ (if x crashes). It is easy to see that this is a schedule of S ′ .

Henceforth assume that t 1 is defined. During the interval [0, t 1 ] process y does not simulate any step, and process x simulates only steps of process 1. So during interval [0, t 1 ] the simulated schedule is some finite prefix of 1 ∞ . Now suppose that, for some i ≥ 1, t i is defined. Let p = 2 + (i -1)mod(n -1). As we noted before, this is the (only) process of P n that y simulates during its i-th iteration of the for-loop of line ?? that starts at time t i .

There are two possible cases:

(1) t i+1 is defined. In this case, we show that during the interval of time [t i , t i+1 ], processes x and y simulate a sequence of steps of the form {1, p} ℓ .

CLAIM 1: During the interval [t i , t i+1 ] processes x and y simulate only the steps of processes 1 and p, and they simulate at least ℓ steps of 1 and at least ℓ steps of p.

Proof of Claim 1: First note that during interval [t i , t i+1 ], process y simulates only steps of process p, and process x simulates only steps of process 1.

Process y stores the value of P C [1] in pc [1] at some time τ 1 , and y stores the value of P C[p] in pc[p] at some time τ 2 , such that t i ≤ τ 1 ≤ τ 2 < t i+1 . Furthermore, the while loop that y executes during the interval [t i , t i+1 ] ends at some time τ 3 ≤ t i+1 , when y finds that (P C (2) t i+1 is undefined.

CLAIM 2: After time t i , only the steps of processes 1 and p are simulated. Furthermore, there is a time τ ≥ t i after which only steps of process 1 are simulated, or only steps of process p are simulated, or no steps are simulated.

Proof of Claim 2: Since t i+1 is undefined, process y never starts its (i + 1)-th iteration of the for-loop of line ??. Thus, after time t i process y can simulate only the steps of process p. Since x simulates only the steps Let α be the prefix of the schedule σ that includes all steps of σ up to and including the step where p decides. Consider the infinite schedule σ ′ = αp ∞ . It is clear that p is correct in schedule σ ′ and σ ′ ∈ Σ ℓ n . Now consider the run R ′ of C n with the schedule σ ′ ∈ Σ ℓ n (so R ′ is a run in system S) and with the same processes inputs as in run R. Since the schedule σ and σ ′ of R and R ′ have the same initial prefix of steps α, process p behaves in same way in R and R ′ up to and including its decision step: so p decides v in R ′ even though v is not the input value of a process in R ′ . This contradicts the assumption that C n solve consensus in S.

2 V

 2 Shared variables: R[1..2n]: array of multi-writer snapshot, initialized to [⊥..⊥] CODE FOR PROCESS p: 1 prop := vp /*p input value*/ iew[1..2n] : array, initialized to [⊥..⊥]

Figure 1 :

 1 Figure 1: B n consensus algorithm with 2n multi-writer snapshot array.

[ 1 ]

 1 > pc[1] + ℓ) and (P C[p] ≥ pc[p] + ℓ) holds. Since P C(1) = pc(1) at time τ 1 and P C[1] > pc[1] + ℓ at time τ 3 , then at least ℓ steps of process 1 are simulated during the interval [τ 1 , τ 3 ]. Similarly, since P C(p) = pc(p) at time τ 2 and P C[p] ≥ pc[p] + ℓ at time τ 3 , then at least ℓ steps of process p are simulated during the interval [τ 2 , τ 3 ]. We conclude that during interval [t i , t i+1 ], only steps of processes 1 and p are simulated, and at least ℓ steps of 1 and at least ℓ steps of p are simulated.

Intuitively, a process schedule specifies the order in which processes take steps.

The results in [?] were for message-passing systems, but similar results hold for read-write shared-memory systems.

The examples of schedules that we give here are very simple (they have a simple repetitive pattern). It should be clear, however, that the set of schedules of S k n is very "rich": it contains schedules that are much more varied and complex than the few simplistic ones that we give for illustration here.

Recall that {p, q} i is any sequence of steps of p and q that contains at least i steps of p and at least i steps of q, in any order.

The algorithm given in [?] implements MWMR registers from SWMR registers. For this algorithm there exists a constant C 2 such that each write requires less than C 2 n reads and writes to the SWMR registers and each read requires less than C 2 n log n reads and writes to the SWMR registers. Moreover, if the values written in the MWMR registers are bounded by K there exists a function D 2 the value written in the SWMR registers are bounded by D 2 (K) Let m = (2n + 2)(2C 1 n 2 C 2 n log n), if some process runs solo for at least m steps it runs alone during 2n + 1 iteration of the main loop of B n , then by Theorem ?? all correct processes decide.

In algorithm B n the processes update the snapshot array with only initial values. Let M be the max of the initial values of processes, in B ′ n all SWMR are bounded by a constant namely by D 2 (D 1 (M )). Then we get:

Theorem 5 There is a constant ℓ such that algorithm B ′ n solves consensus with a bounded number of boundedsize SWMR registers in any ℓ-solo schedules.

Consider system S ℓ n for the bound ℓ given in the previous theorem, then for any

Theorem 6 For any proper subset Q of P n , consensus can be solved in S ℓ n (Q) by an algorithm with a bounded number of bounded-size SWMR registers. We now prove that consensus cannot be solved in system S = S ℓ n . Suppose, for contradiction, that there is an algorithm C n that solves consensus in system S. We show that the two processes of the asynchronous system A 2 can use C n to solve consensus among themselves (contradicting the impossibility result in [?, ?]); intuitively, of process 1, after time t i only the steps of 1 and p can be simulated. Furthermore, since t i+1 is undefined, by Observation ?? process x or process y (or both) crash. If y crashes then after this crash occurs no steps of p are simulated. If x crashes then after this crash occurs no steps of 1 are simulated. So there is a time τ ≥ t i after which only steps of process 1 are simulated, or only steps of process p are simulated, or no steps are simulated.

Consensus cannot be solved in system S

From the above, it is clear that when x and y execute the algorithm in Figure ?? in system A 2 , they simulate a schedule of

or a finite prefix of such a schedule, or a finite prefix of such a schedule followed by p ∞ for some process p ∈ P n . In other words, they simulate schedules of the system

We now show that the algorithm Figure ?? solves consensus in the asynchronous system A 2 . This algorithm simulates the execution of an algorithm C n that is assumed to solve consensus in system S. We first show that C n satisfies the uniform version of the agreement and integrity properties, namely: (a) all the processes that decide (whether correct or faulty) decide the same value, and (b) any process that decides (whether correct or faulty) decides a process input value. That is:

, the consensus algorithm C n satisfies the uniform agreement and uniform integrity properties.

PROOF. Due to the lack of space, we give the proof of this Lemma in Appendix (Sec ??).

To prove that the algorithm in Figure ?? solves consensus in A 2 , consider an execution of this algorithm where x and y have input value i x and i y , respectively. In this execution, process x simulates the steps of process 1 executing algorithm C n with input i x (see line ??); if process 1 decides a value v in C n , then x also decides v. Similarly, process y simulates the steps of processes 2, 3, . . . , n executing algorithm C n with input i y (see line ??). If any process in {2, 3, . . . , n} decides a value in C n , then y also decides this value. By Lemma ??, this execution simulates a run of the consensus algorithm C n among the n processes of P n in the subsystem S ′ of S. We now show that x and y reach consensus.

• (Uniform) Agreement: If x and y decide, then x decides the value that process 1 decides and y decides the value that some process p ∈ {2, 3, . . . , n} decides in the simulated execution of C n in system S ′ ⊆ S. By Lemma ??, C n satisfies the uniform agreement property in system S. Thus, x and y decide the same value.

• Termination: If process x is correct, then process 1 is correct (i.e., it takes an infinite number of steps) in the simulated execution of C n in system S ′ ⊆ S. Since C n satisfies the termination property in system S, correct process 1 decides a value in this execution of C n . So x also decides a value.

If process y is correct, then at least one process p ∈ {2, 3, . . . , n} that y simulates is correct in the simulated execution of C n in system S ′ ⊆ S. Since C n satisfies the termination property in system S, correct process p decides a value in this execution of C n . So y also decides a value.

• (Uniform) Integrity: If x or y decides a value v, then some process p ∈ P n decides v in the simulated execution of C n in system S ′ ⊆ S. By Lemma ??, C n satisfies the uniform integrity property in system S. Thus v must be the input value of some process q ∈ P n in this execution of C n . Note that the input value of q in A n is the input value of x or y (algorithm lines ?? and ??). So v is the input value of x or y.

We proved that if an algorithm C n solves consensus in system S, then the algorithm in Figure ?? solves (uniform) consensus in the asynchronous system of two processes A 2 -contradicting the results in [?, ?]. Thus, consensus cannot be solved in S.

Appendix

A Consensus (Section ??)

More formally, let V τ (v) be the number of cells of snapshot array R equal to v at time τ . Given any value v, assume that p has already made its scan in Line ??, the next update of a process p in Line ?? will be with a value different from v if (i) at least n cells of the array returned by the last scan of p contain the same value w and w = v and (ii) not all the values of the array returned by the last scan of p are the same. Let C τ (v) be the number of processes that have already made the scan (Line ??) and have not yet made the next update (Line ??) for which conditions (i) and (ii) are true. Let Inv τ (v) ≡ V τ (v) -C τ (v) > n, we have:

PROOF. Prove that for all v Inv τ (v) is an inductive invariant. Assume that Inv τ (v) is true and consider the next step of any process and let τ ′ be the linearization time of the this next step and p be the process making this step. We have the following cases:

• at time τ ′ process p updates cell i with a value w. As p has performed its update and has not preformed yet its scan,

• at time τ ′ process p performs a scan, the snapshot returned is the value of R at time τ , hence the number of cells equal to v is V τ (v), and we have

ensures that the number of cells equal to v in the scan is strictly greater than n then the proposed value after Line ??

Hence Inv τ (v) is an invariant and by induction we deduce the lemma.

Lemma 13 If some process p decides v, if τ is the linearization time of the last scan of the process p before its decision, then Inv τ (v) is true. Moreover for every time

PROOF. As p decides value v at time τ we have V τ (v) = 2n and as C τ (v) < n, Inv τ is true. By Lemma ??

We deduce the uniform agreement property:

Lemma 14 (Uniform agreement) If process p decides v and process q decides v ′ at time

PROOF. Assume p decides v at time τ 1 and q decides w at time τ 2 Without loss of generality assume that τ 1 < τ 2 . By Lemma ?? at any time τ ≥ τ 2 , V τ (v) > n and V τ (w) > n. As the snapshot array has 2n cells, if value v and value w are each in more than n cells then v = w.

Only initial values are written in the snapshot array then we have the uniform integrity property:

Lemma 15 (Uniform integrity) If some process decides v then v is the initial value of some process.

Concerning termination:

Lemma 16 If some process decides v at time τ then all correct processes decide.

PROOF. By Lemma ??, after time τ forever more than n cells of the snapshot array contains value v, then there is a time τ ′ after which any update of the snapshot array is with value v. Moreover any cell containing value v after time τ ′ contains value v forever. If some correct process q does not decide, it will perform an infinite number of updates of the snapshot array after time τ ′ with value v and as update of cells are made in a cyclic order eventually all cells of the snapshot array will be forever equal to v, and q decides -a contradiction.

Lemma 17 If some process runs alone during 2n + 1 successive iterations of the main loop, it decides.

PROOF. Consider the body of the main loop of algorithm B n (Lines ?? to ??), if a process runs alone at least 2n + 1 successive iterations of the body of the main loop, after the scan of its first iteration its proposed value does not change and it updates during the next 2n iterations every cell of the snapshot array with this value. Then by the end of these 2n + 1 iterations it decides.

By Lemma ?? and ??, if some process runs alone during 2n+1 successive iterations of the main loop, termination are ensured by algorithm B n . Then with agreement (Lemma ??) and integrity (Lemma ??) we get:

Theorem 18 (Theorem ??) If some process runs alone during 2n + 1 successive iterations of the main loop, algorithm B n is a consensus algorithm.

In fact outr algorithm ensures uniform consensus.

B Consensus cannot be solved in system S (Section ??)

Lemma 19 ( Lemma ??) In system S = [P n , Σ ℓ n ], the consensus algorithm C n satisfies the uniform agreement and uniform integrity properties.

PROOF. Suppose, for contradiction that the lemma does not hold. There are two cases:

• C n violates the uniform agreement property in system S. So there is a run R of C n in system S, i.e., a run R with some schedule σ ∈ Σ ℓ n , such that some process p decides a value v p , another process q decides a value v p = v p , and at least one of these two processes crashes (i.e., stops taking steps) after deciding. Recall that Σ ℓ n = {σ | σ ∈ Σ n and for all Q ⊂ P n : σ(Q) is ℓ-solo}. Let α be the prefix of the schedule σ that includes all steps of σ up to and including the steps where p and q decide. Consider the infinite schedule σ ′ = αp ℓ q ℓ p ℓ q ℓ p ℓ q ℓ . . .. Note that both p and q are correct in schedule σ ′ . We claim that σ ′ ∈ Σ ℓ n . This holds because for each proper subset Q of P n , σ ′ (Q) is ℓ-solo: in fact, if Q contains p or q, then σ ′ (Q) contains infinite instances of p ℓ or q ℓ , so it is ℓ-solo; and if Q contains neither p nor q, then σ ′ (Q) is finite and so it is also ℓ-solo. Now consider the run R ′ of C n with the schedule σ ′ ∈ Σ ℓ n (so R ′ is a run in system S) and with the same processes inputs as in run R. Since the schedule σ and σ ′ of R and R ′ have the same initial prefix of steps α, processes p and q behave in same way in R and R ′ up to and including their decision steps: so they decide different values v p and v q in R ′ even though they are both correct processes in R ′ . This contradicts the assumption that C n solve consensus in S.

• C n violates the uniform integrity property in system S. So there is a run R of C n in system S, i.e., a run R with some schedule σ ∈ Σ ℓ n , such that some process p decides a value v that is not the input value of a process, and and p crashes after deciding.