A Hierarchy of Unrestricted Deterministic Objects with Consensus Number 1

A process only updates $T[a]$ with a view of $R$ containing $a$ 1s. $R$ is an atomic snapshot object that initially has 0 in all its components and the only updates to it change a single component to 1. Thus, each distinct view of $R$ consists of a unique number of 1s. $◀$

Note that the doorway can be open when a process performs line 19. For example, suppose an srn$(i)$ call performs lines 1 and 2 and goes to sleep. Then, another srn$(i)$ call performs line 1 followed by lines 16 to 19.

Suppose no srn calls encounter an open doorway on line 3. Then, line 4 is never performed. Therefore, the doorway is closed on line 19. Let $c$ be the first srn call to perform line 19. Let $i$ and $p$ respectively be the input of $c$ and the process that invoked it. Since $c$ performs line 19, $c$ reads 1 from $R[i]$ on line 1. Thus, some other srn$(i)$ call $c^{\prime }$ updated $R[i]$ to 1 before $c$ performs line 1. Let $p^{\prime }$ be the process that invoked $c^{\prime }$.

The doorway is open before $c$ performs line 19. Therefore, by Lemma 6, no srn call returns before $c$ performs line 19. Thus, $p\ne p^{\prime }$. Note that both $p$ and $p^{\prime }$ start but do not return an srn$(i)$ call before $c$ performs line 19. As there are only $k$ processes, this implies that there exists a $j\in {\mathbb{Z}}_k$ such that no srn$(j)$ call has started before $c$ performs line 19. Therefore, if $r$ is the result of the scan performed during $c$, then $r[i]=1$ and $r[j]=0$. $T$ is updated with this view on line 18 of $c$. $◀$

First, suppose at least one srn call encounters an open doorway on line 3. Of these srn calls, in the first srn call to perform line 5, propose returns its input. Therefore, this srn call returns 0 on line 6.

So, suppose that no srn call encounters an open doorway on line 3. By Lemma 7, $T$ is updated with a view, $r$, of $R$, before the doorway closes. Furthermore, $r$ contains at least one 1 and one 0. As $r$ consists of only 1’s and 0’s, there exists $i\in {\mathbb{Z}}_k$ such that $r[i]=1$ and $r[i+1]=0$. As $r[i]=1$, at least one srn$(i)$ call $c$ has updated the value of $R[i]$ to 1 on line 2. As no srn call encounters an open doorway on line 3, $c$ performs line 3 after the doorway closes. This implies that when $c$ performs a scan of $T$ on line 10, $T$ is already updated with $r$. Thus, $c$ returns 0 on line 13. $◀$

Suppose $c$ returns 0 on line 13. Then, there exists an integer such that the result, $t$, of the scan of $T$ performed on line 10 satisfies $t[b][i]=1$ and $t[b][i+1]=0$. In other words, before $c$ performs line 10, $T$ was updated with some view, $r$, of $R$ such that $r[i]=1$ and $r[i+1]=0$.

So, suppose $c$ returns 0 on line 20. Then, $c$ reads $1$ from $R[i]$ on line 1. Thus, the result, $r$, of the scan of $R$ performed on line 16 satisfies $r[i]=1$. As $c$ returns 0, $r[i+1]=0$. $r$ is updated to a component of $T$ on line 18. $◀$

Let $Q$ be the set of inputs $i^{\prime }\in {\mathbb{Z}}_k$ such that some srn$(i^{\prime })$ call reads an open doorway on line 3.

First, suppose $|Q|=k$. Then, $Q={\mathbb{Z}}_k$. By Lemma 6, the doorway closes before any srn call returns. Thus, all srn calls that read an open doorway are concurrent. Since there are only $k$ processes and some srn$(i^{\prime })$ call reads an open doorway for each $i^{\prime }\in {\mathbb{Z}}_k$, each process first calls srn with a different input. All of these calls read an open doorway on line 3 before any of them close the doorway on line 4. Since these calls all update $R$ to 1 on line 2, the result of each scan of $R$ performed on line 7 and 16 during the run has 1 in every component. Thus, no srn call returns 0 on line 13 or 20. Some process does not get its identifier back from $S$ on line 5. Let $i$ be the input to the first srn call by this process. Since this srn$(i)$ call does not perform line 6 and all other srn$(i)$ calls read $R[i]=1$ on line 1, no srn$(i)$ call performs line 6. Thus, no srn$(i)$ call returns 0.

So, suppose $|Q|\le k-1$. For the sake of contradiction, assume that, for all $i^{\prime }\in {\mathbb{Z}}_k$, some srn$(i^{\prime })$ call returns 0. For each $i^{\prime }\in {\mathbb{Z}}_k$, the first srn$(i^{\prime })$ call that performs line 1 reads 0 from $R[i^{\prime }]$ and so performs line 2. For each $i^{\prime }\in {\mathbb{Z}}_k\setminus Q$, let $c_{i^{\prime }}$ be the first srn$(i^{\prime })$ call that performs line 2. Let $C=\{c_{i^{\prime }}:i^{\prime }\in {\mathbb{Z}}_k\setminus Q\}$. Thus, $|C|=k-|Q|$.

Let $c_j$ be the last call in $C$ to perform line 2. Since $j\notin Q$, no srn$(j)$ call reads an open doorway on line 3. Thus, no srn$(j)$ call returns 0 on line 6. By assumption, some srn$(j)$ call returns 0. By Lemma 9, this implies that a scan of $R$ such that its result, $r$, satisfies $r[j]=1$ and $r[j+1]=0$, is performed before the call returns. Thus, $R[j+1]$ is updated from 0 to 1 after $R[j]$ is. Since $R[j]$ is updated from 0 to 1 when $c_j$ performs line 2 and $c_j$ is the last call in $C$ to perform line 2, it follows that $(j+1)\in Q$. This implies some srn$(j+1)$ call reads an open doorway on line 3. Thus, the scan that resulted in $r$ is performed before the doorway closes.

Let $c^{\ast }$ be the srn call in which the scan that resulted in $r$ is performed. Let $D$ be the set of srn calls that read an open doorway on line 3. Then $|D|\ge |Q|$.

Since the doorway is closed before any srn call performs line 7, the scan that resulted in $r$ is performed on line 16. Thus, $c^{\ast }\notin C\cup D$. Since the scan that resulted in $r$ is performed before the doorway closes, $c^{\ast }$ starts before the doorway closes. By definition, all calls in $D$ perform line 3 before the doorway closes. Furthermore, the scan that resulted in $r$ is performed after $c_j$ performs line 2. Thus, all calls in $C\cup D\cup \{c^{\ast }\}$ start before the doorway closes. By Lemma 6, no calls return prior to the doorway closing. Therefore, at least $|C|+|D|+1\ge k+1$ srn calls execute concurrently, which cannot occur with just $k$ processes. Thus, by contradiction, there exists an $i\in {\mathbb{Z}}_k$ such that no srn$(i)$ call returns 0. $◀$

If $c$ returns on line 14, then $c$ performs a scan of $R$ with result $r$ on line 7. As $c$ has updated $R[i]$ to $1$ on line 2, $r[i]=1$. Since $c$ does not return on line 13, $r[i+1]=1$. Similarly, if $c$ returns 1 on line 20, $r[i+1]=1$. Thus, before $c$ returns, $R[i+1]$ is updated to 1. Let $c^{\prime }$ be an srn$(i)$ call that starts after $c$ returns. When $c^{\prime }$ performs line 1, $R[i]=1$. Thus, $c^{\prime }$ performs a scan of $R$ on line 16 with result $r^{\prime }$ and then returns $r^{\prime }[i+1]$ on line 20. Since $R[i+1]$ is updated to 1 before $c$ returns, $r^{\prime }[i+1]=1$. Therefore, $c^{\prime }$ returns $1$. $◀$

Suppose that some srn$(i+1)$ call returns before $c$ starts. This implies that before $c$ starts, $R[i+1]$ has been updated to 1 and the doorway is closed.

If $c$ reads $R[i]=1$ on line 1, then the result, $r$, of the scan of $R$ performed by $c$ on line 16 satisfies $r[i+1]=1$. Thus, if $c$ reads $R[i]=1$ on line 1, $c$ returns $1$ on line 20.

So, suppose $c$ reads $R[i]=0$ on line 1. Then, $R[i+1]$ was updated from 0 to 1 before $R[i]$ was. Thus, no scan of $R$ performed in any srn call results in a view, $r$, such that $r[i]=1$ and $r[i+1]=0$. As the doorway is closed before $c$ starts, $c$ does not return on line 6. $c$ also does not return on line 13. Therefore, $c$ returns 1 on line 14. $◀$

Suppose that $c$ performs a scan of $R$ on line 7 or 16 before $R[i+1]$ is updated to $1$. Then, the result of the scan, $r$, satisfies $r[i+1]=0$. Furthermore, since $c$ either reads $R[i]=1$ on line 1 or updates $R[i]$ to 1 on line 2, it follows that $r[i]=1$.

If $c$ reads $R[i]=1$ on line 1, it returns $r[i+1]$ on line 20, which is equal to $0$. So, suppose $c$ reads $R[i]=0$ on line 1. Then, it updates $T$ with $r$ on line 9 and performs a scan of $T$ on line 10. As $T$ has been updated with $r$ prior to the scan, $c$ returns 0 on line 13. $◀$

For each $i\in {\mathbb{Z}}_k$, let ${𝒟}_i$ be the set of srn$(i)$ calls that start before any srn$(i)$ call returns. Note that ${𝒟}_i$ is non-empty as long as there is at least one srn$(i)$ call in the execution. In this case, we distinguish exactly one srn$(i)$ call $d_i\in {𝒟}_i$ as follows.

• $\mathrm{■}$

  If there exists a call in ${𝒟}_i$ that returns 0, of these calls, let $d_i$ be the one that starts first.

• $\mathrm{■}$

  Otherwise, let $d_i$ be the srn$(i)$ call that performs line 2 first.

There are two very useful properties regarding these distinguished calls.

From the way that $d_i$ is chosen, if $d_i$ returns 1, then all calls in ${𝒟}_i$ return 1. Furthermore, as the first srn$(i)$ call to return is in ${𝒟}_i$ and thus returns 1, by Lemma 11, all srn$(i)$ calls that start after it returns also return 1. $◀$

If ${𝒟}_{i+1}=\mathrm{\varnothing }$, then no srn$(i+1)$ calls are performed. If ${𝒟}_{i+1}\ne \mathrm{\varnothing }$ and $d_{i+1}$ returns 1, then by definition, $d_{i+1}$ is the srn$(i+1)$ call that updates $R[i+1]$ from 0 to 1. In both cases, $c$ returns before $R[i+1]$ is updated to 1. Note that $c$ either returns on line 6 or performs line 7 or 16. By Lemma 13, $c$ also returns 0 in the latter case.

So, suppose ${𝒟}_{i+1}\ne \mathrm{\varnothing }$ and $d_{i+1}$ returns 0. For the sake of contradiction, assume $c$ returns 1. By the contrapositive of Lemma 13, some srn$(i+1)$ call $c^{\prime }$ updates $R[i+1]$ to 1 before $c$ returns. As $c$ returns before $d_{i+1}$ starts, $c^{\prime }$ starts before $d_{i+1}$ starts. By definition, out of all the srn$(i+1)$ calls that return 0, $d_{i+1}$ starts first. Thus, $c^{\prime }$ returns 1.

As $c$ returns 1 before $d_{i+1}$ starts, $R[i+1]$ is updated to 1 before $d_{i+1}$ starts. Therefore, $d_{i+1}$ reads $R[i+1]=1$ on line 1 and performs lines 16 to 20. As $d_{i+1}$ returns 0, $R[i+2]=0$ when $d_{i+1}$ performs line 16. As $c$ returns 1, $c$ updates $T$ with a view, $r$, of $R$, such that $r[i+1]=1$. As $c$ returns before $d_{i+1}$ starts, $r[i+2]=0$. Since $c^{\prime }$ executes line 2 and returns 1, $c^{\prime }$ returns 1 on line 14. As $c^{\prime }$ does not return on line 13, $c^{\prime }$ executes line 10 before $c$ updates $T$ with $r$. This implies a scan of $R$ is performed on line 7 of $c^{\prime }$ before $d_{i+1}$ starts. Let $r^{\prime }$ be the result of the scan. As $c^{\prime }$ updates $R[i+1]$ to 1 on line 2, $r^{\prime }[i+1]=1$. Since $c^{\prime }$ also returns 1, $r^{\prime }[i+2]=1$. Thus, before $d_{i+1}$ starts, $R[i+2]$ is updated to 1. Therefore, $d_{i+1}$ returns 1. This is a contradiction, so $c$ returns 0. $◀$

The execution graph (of the execution) is the directed graph $𝒢=(𝒱,ℰ)$, where $𝒱$ is the set of srn calls in the execution and $(u,v)\in ℰ$ if and only if one of the following properties are satisfied for some $i\in {\mathbb{Z}}_k$:

1. 1.

   $u$ is an srn$(i)$ call that returns 0 and $v$ is an srn$(i+1)$ call

2. 2.

   $u=d_{i+1}$ is a distinguished call and $v$ is an srn$(i)$ call that returns 1

As shown in Lemmas 16 and 19, $𝒢$ is acyclic and encodes nice temporal relationships between srn calls.

Note that consecutive nodes in $𝒢$ have input values that differ by 1 modulo $k$. Additionally, in any directed path consisting of strictly increasing input values, all srn calls, except possibly the last one, return 0. Similarly, in any directed path consisting of strictly decreasing input values, all srn calls, except possibly the last one, are distinguished and all srn calls, except possibly the first one, return 1. Furthermore, $𝒢$ does not contain any directed path $c_h\to c_{h-1}\to c_h^{\prime }$, where $c_h$ and $c_h^{\prime }$ are srn$(h)$ calls and let $c_{h-1}$ is an srn$(h-1)$ call. This is because $(c_h,c_{h-1})\in ℰ$ would imply that $c_{h-1}$ returns 1 but $(c_{h-1},c_h^{\prime })\in ℰ$ would imply that $c_{h-1}$ returns 0.

For the sake of contradiction, suppose that $𝒢$ contains a directed cycle.

First, suppose that at least one node in the cycle returns 1. By the definition of $𝒢$, all nodes that can be reached from this node also return 1. Furthermore, each edge of the cycle goes from an srn$(i+1)$ call to an srn$(i)$ call for some $i\in {\mathbb{Z}}_k$. As each node in a directed cycle has an outgoing edge, all nodes in the cycle are distinguished srn calls. Thus, the cycle contains distinguished calls of every possible input. Therefore, for all $i\in {\mathbb{Z}}_k$, $d_i$ returns 1. By Lemma 14, all srn calls return 1. This contradicts Lemma 8.

So, suppose that all nodes in the cycle return 0. Then, each edge in the cycle goes from an srn$(i)$ call to an srn$(i+1)$ call for some $i\in {\mathbb{Z}}_k$, so the cycle contains calls of every possible input. This means that for every input, at least one srn call returns 0. This contradicts Lemma 10.

Thus, by contradiction, $𝒢$ contains no directed cycles. $◀$

We will prove this lemma by induction.

Suppose $c_i$ reads $R[i]=1$ on line 1. Then, $c_i$ performs a scan of $R$ on line 16. As $c_i$ returns 0, the result of the scan, $r$, satisfies $r[i+1]=0$. Thus, $c_i$ performs the scan before $R[i+1]$ is updated to 1, so $c_i$ starts before $R[i+1]$ is updated to 1.

Now, suppose $c_i$ reads $R[i]=0$ on line 1. This implies $c_i$ starts before $R[i]$ is updated to 1. As $c_i$ does not read an open doorway, $c_i$ returns on line 13. By Lemma 9, before $c_i$ returns, $T$ is updated with a view, $r$, of $R$, such that $r[i]=1$ and $r[i+1]=0$. This implies $R[i]$ is updated to 1 before $R[i+1]$ is updated to 1. Thus, $c_i$ starts before $R[i+1]$ is updated to 1.

Let $c_h\in W$ where $h\ne i$ and $h\ne j$, and assume that $c_i$ starts before $R[h]$ is updated to 1. Hence, $c_i$ starts before $c_h$ reads $R[h]=1$ on line 1 or updates $R[h]$ to 1 on line 2. Since the doorway is closed before $c_i$ starts, $c_h$ returns 0 on line 13 or 20. By Lemma 9, before $c_h$ returns, $T$ is updated with a view, $r^{\prime }$, of $R$, such that $r^{\prime }[h]=1$ and $r^{\prime }[h+1]=0$. This implies $R[h]$ is updated to 1 before $R[h+1]$ is. As $c_i$ starts before $R[h]$ is updated to 1, $c_i$ starts before $R[h+1]$ is updated to 1. $◀$

Since $c_j$ returns 1, it performs a scan of $R$ before it updates $T$. Hence, if $R[i+1]$ is updated to 1 before $c_j$ performs a scan of $R$, then it is updated to 1 before $c_j$ updates $T$. So, suppose that $c_j$ performs a scan of $R$ before $R[i+1]$ is updated to 1. As $c_j$ returns 1, the contrapositive of Lemma 13 implies that $R[j+1]$ is updated to 1 before $c_j$ performs a scan of $R$. This implies the result of the scan, $r$, satisfies $r[i+1]=0$ and $r[j+1]=1$.

Let $c_i^{\prime }$ be the srn$(i)$ call that updates $R[i]$ from $0$ to $1$. Suppose that $c_i^{\prime }$ returns 1. Then it performs line 2 and returns on line 14. By the contrapositive of Lemma 13, $R[i+1]$ is updated to 1 before $c_i^{\prime }$ performs a scan of $R$ on line 7.

We prove that $R[i+1]$ is updated to 1 before $c_j$ updates $T$ by strong induction on the length of $W$. Suppose that the lemma is true for all directed paths of shorter length.

If $r[i]=1$, then $c_i^{\prime }$ performs a scan of $T$ on line 10 before $c_j$ updates $T$ with $r$ on line 9 or 18. This is because $r[i+1]=0$ and $c_i^{\prime }$ does not return on line 13. In this case, $R[i+1]$ is updated to 1 before $c_j$ updates $T$.

So, suppose that $r[i]=0$. If $W$ is a path of length 1, then $i=j+1$, so $r[i]=1$. Thus, $W$ has length greater than 1. Recall that $r[j+1]=r[j]=1$. Let $c_h$ be the last srn call in $W$ such that its input, $h$, satisfies $r[h]=0$. Then $r[h-1]=1$ and $h-1$ is not equal to $i$ and $j$. Let $c_{h-1}$ be the srn$(h-1)$ call following $c_h$ in $W$. Since $c_{h-1}$ is a distinguished srn call that returns 1, it performs line 2 and returns on line 14. Moreover, $r[h-1]=1$ and $r[h]=0$, so $c_{h-1}$ performs a scan of $T$ on line 10 before $c_j$ updates $T$ with $r$.

Let $W^{\prime }$ be the prefix of path $W$ that ends with $c_{h-1}$. By the induction hypothesis applied to $W^{\prime }$, $R[i+1]$ is updated to 1 before $c_{h-1}$ updates $T$ on line 9. This occurs before $c_{h-1}$ performs a scan of $T$ on line 10, which is before $c_j$ updates $T$. $◀$

By Lemma 6, if $c_i$ starts before the doorway is closed, $c_i$ starts before any srn call returns. So, assume that $c_i$ starts after the doorway is closed.

We need to consider three separate cases, as $W$ can consist of strictly increasing input values, strictly decreasing input values, or increasing input values followed by decreasing input values.

First, we consider the case where $W$ consists of strictly increasing input values. As there is some srn$(j-1)$ call in $W$, by Lemma 17, $c_i$ starts before $R[j]$ is updated to 1. Since $R[j]$ is updated to 1 before $c_j$ returns, this implies that $c_i$ starts before $c_j$ returns.

Now, we consider the case where $W$ consists of strictly decreasing input values. Suppose $c_i$ starts before $R[i]$ is updated to 1. If the length of $W$ is 1, then $j=i+1$ and $c_j$ returns 1. By the contrapositive of Lemma 13, $R[j+1]$ is updated to 1 on line 2 before $c_j$ performs a scan of $R$ on line 7 or 16. This implies $R[i]$ is updated to 1 before $c_j$ updates $T$. Thus, $c_i$ starts before $c_j$ returns. On the other hand, if the length of $W$ is greater than $1$, then $i-1\ne j$. Hence, the srn$(i-1)$ call immediately after $c_i$ in $W$ is $d_{i-1}$ and it returns 1. This implies $d_{i-1}$ is the srn$(i-1)$ call that updates $R[i-1]$ from 0 to 1. Thus, by applying Lemma 18 to the suffix of $W$ starting at $d_{i-1}$, we see that $R[i]$ is updated to 1 before $c_j$ updates $T$. Once again, $c_i$ starts before $c_j$ returns.

So, suppose $c_i$ starts after $R[i]$ is updated to 1. Thus, $c_i$ reads $R[i]=1$ on line 1 and performs lines 16 to 20. Note that $c_i=d_i$ and $c_i$ is not the srn$(i)$ call that updates $R[i]$ to 1. Thus, $c_i$ returns 0. This implies that the result, $r$, of the scan that $c_i$ performs on line 16 satisfies $r[i+1]=0$. Therefore, $c_i$ performs line 16 before $R[i+1]$ is updated to 1. Let $c$ be the srn$(i)$ call that updates $R[i]$ from 0 to 1. As $c$ is not distinguished and starts before $c_i$, $c$ returns 1. By Lemma 18, $R[i+1]$ is updated to 1 before $c_j$ returns. Thus, $c_i$ performs line 16 before $c_j$ returns.

Finally, we consider the case where $W$ consists of increasing input values followed by decreasing input values. In other words, $W$ contains some sub-path $c_h\to c_{h+1}\to c_h^{\prime }$, where $h\in {\mathbb{Z}}_k$, $c_h$ and $c_h^{\prime }$ are srn$(h)$ calls and $c_{h+1}$ is an srn$(h+1)$ call. Since $(c_h,c_{h+1})\in ℰ$, it follows that $c_h$ returns 0. Thus, by definition, $d_h$ also returns 0. Similarly, since $(c_{h+1},c_h^{\prime })\in ℰ$, $c_h^{\prime }$ returns 1. Therefore, $c_h^{\prime }\ne d_h$. By definition of $𝒢$, $c_h^{\prime }$ has no outgoing edges, so $c_h^{\prime }=c_j$.

First, suppose $c_i=c_h$. Since $c_i$ is an srn$(h)$ call that returns 0, it follows by Lemma 11 that $c_i$ starts before $c_j$ returns. Now, suppose $c_i\ne c_h$. Then, there exists an srn$(j-1)$ call in $W$. By Lemma 17, $c_i$ starts before $R[j]$ is updated to 1. Note that $R[h]$ is updated to 1 before $c_j$ returns. Thus, $c_i$ starts before $c_j$ returns. $◀$

Fix an execution $\mathscr{H}$. Let $𝒢=(𝒱,ℰ)$ be its execution graph. Let $f$ be the srn call in $𝒱$ that returns first, and let $F$ be the set of srn calls in $𝒱$ that start before $f$ returns. In particular, $f\in F$. By Lemma 16, $𝒢$ contains no directed cycles. Thus, either $f$ is a source, or there exists a source $q\ne f$ in $𝒢$ such that there is a directed path from $q$ to $f$. By Lemma 19, $q$ starts before $f$ returns, so $q\in F$.

Algorithm 5 returns a linearization of the execution. This algorithm topologically sorts $𝒢$, while guaranteeing that if an srn call $u$ returns before another srn call $v$ starts in $\mathscr{H}$, then $u$ is ordered before $v$. For $u,v\in 𝒱$, let $u\prec v$ denote that $u$ occurs before $v$ in the linearization.

Let us prove the contrapositive. Suppose $v\prec u$. Let $\widehat{G}$, $\widehat{f}$, and $\widehat{F}$ be the respective values of $G$, $f$, and $F$ when $v$ is added to $ℒ$. Then, $u$ is a vertex in $\widehat{G}$ and $v\in \widehat{F}$. By definition of $\widehat{F}$, $v$ starts before $\widehat{f}$ returns in $\mathscr{H}$. Furthermore, since $\widehat{f}$ is the first call in $\widehat{G}$ to return and $u$ is a vertex in $\widehat{G}$, $\widehat{f}$ returns at or before $u$ returns. Thus, $v$ starts before $u$ returns in $\mathscr{H}$. $◀$

First, suppose $v$ returns 1 in $\mathscr{H}$. By the contrapositive of Lemma 15, ${𝒟}_{i+1}\ne \mathrm{\varnothing }$ and $d_{i+1}$ starts before $v$ returns. By part 2 of the definition of execution graph, $(d_{i+1},v)\in ℰ$. In each iteration of the while loop of Algorithm 5, only sources are added to the end of $ℒ$. Therefore, $d_{i+1}$ is added to $ℒ$ before $v$, so $d_{i+1}\prec v$.

Now, suppose $v$ returns 0 in $\mathscr{H}$. Let $u$ in $𝒱$ be any srn$(i+1)$ call. By part 1 of the definition of execution graph, $(v,u)\in ℰ$. In each iteration of the while loop of Algorithm 5, only sources are added to the end of $ℒ$. Thus, $v\prec u$. Therefore, there do not exist any srn$(i+1)$ calls $u$ such that $u\prec v$. $◀$ By Lemmas 20 and 21, Algorithm 5 returns a linearization of the execution.

Now, consider an execution $\mathscr{H}$ of our implementation of ${\text{SRN}}_k$ that may be infinite and may contain invocations of srn that do not return. Let $s_1$ be a step in $\mathscr{H}$ after which no incomplete srn call takes another step.

Initially, $R[i]=0$ for all $i\in {\mathbb{Z}}_k$. Note that each process may read $R[i]=0$ on line 1 only during its first call of srn$(i)$. If a process reads $R[i]=1$ on line 1, it only performs lines 1 and 16 to 20. Let $s_2$ be a step in $\mathscr{H}$ after which no srn call performs any of lines 2 to 14.

Let $s$ be whichever of $s_1$ and $s_2$ occurs last. Let $H^{\prime }$ be the prefix of $\mathscr{H}$ up to and including $s$ and let $H^{\prime \prime }$ be the remainder of $\mathscr{H}$. Let $I$ be the subset of incomplete srn calls in $\mathscr{H}$ that update $R$ on line 2 or $T$ on line 18. Let ${\mathscr{H}}^{\ast }$ be the execution that starts with $H^{\prime }$, but with the removal of the incomplete srn calls not in $I$. This is followed by the continuation of each call in $I$ until it completes, which is then followed by the steps in $H^{\prime \prime }$.

The calls removed from $H^{\prime }$ do not modify any of the shared objects, so the behavior of the other calls is the same in $\mathscr{H}$ and in ${\mathscr{H}}^{\ast }$. Processes that take steps in $H^{\prime \prime }$ do not invoke any of the srn calls in $I$. Therefore, the state of the processes that take steps in $H^{\prime \prime }$ are the same in $\mathscr{H}$ and ${\mathscr{H}}^{\ast }$ immediately before any step in $H^{\prime \prime }$ is performed. During $H^{\prime \prime }$, only lines 1 and 16 to 20 are performed, so $R$ is the only shared object that is read. As $R$ is only updated on line 2, the calls in $I$ do not update $R$ after $s$ in ${\mathscr{H}}^{\ast }$. Thus, the behaviour of each call in $\mathscr{H}$ except for those in $I$ is the same as in ${\mathscr{H}}^{\ast }$, so ${\mathscr{H}}^{\ast }$ is a valid execution.

Let $J$ be the set of srn calls that start in $H^{\prime }$. Consider the shortest prefix of ${\mathscr{H}}^{\ast }$ in which every call in $J$ returns. Let $ℱ$ be the continuation of this execution in which each incomplete srn call takes steps until it completes. Since these incomplete srn calls start in $H^{\prime \prime }$, the only shared object they read from is $R$. Since $R$ is only updated prior to $H^{\prime \prime }$, the value returned by each of these calls is the same in $ℱ$ and in ${\mathscr{H}}^{\ast }$. Notice $ℱ$ is a finite execution in which every srn call returns. Then, Algorithm 5 produces a linearization ${ℒ}^{\prime }$ of $ℱ$. Let $ℒ$ be the sequential execution obtained from ${ℒ}^{\prime }$ by appending the remaining calls in ${\mathscr{H}}^{\ast }$ in the order in which they start.

In ${ℒ}^{\prime }$, each srn call returns the same value as in $ℱ$, which is the value returned in ${\mathscr{H}}^{\ast }$. Consider any srn$(i)$ call, $c$, that is in $ℒ$, but not ${ℒ}^{\prime }$. This implies that, in ${\mathscr{H}}^{\ast }$, $c$ starts in $H^{\prime \prime }$. First, suppose $c$ returns 1 in $ℒ$. Then, some srn$(i+1)$ call occurred before $c$ in $ℒ$. This srn$(i+1)$ call also occurs in ${\mathscr{H}}^{\ast }$. Hence, $R[i+1]$ is updated to 1 (on line 2) during ${\mathscr{H}}^{\ast }$. As line 2 is not performed during $H^{\prime \prime }$, $R[i+1]=1$ immediately prior to $H^{\prime \prime }$. Thus, $c$ returns 1 in ${\mathscr{H}}^{\ast }$. Now, suppose $c$ returns 0 in $ℒ$. Then no srn$(i+1)$ call has occurred in ${ℒ}^{\prime }$, which implies no srn$(i+1)$ call occurs during $ℱ$. As line 2 is not performed during $H^{\prime \prime }$, it follows that $R[i+1]=0$ throughout $H^{\prime \prime }$. Thus, $c$ returns 0 in ${\mathscr{H}}^{\ast }$. Therefore, each srn call in $ℒ$ returns the same value as in ${\mathscr{H}}^{\ast }$.

Let $c$ be an srn call in ${\mathscr{H}}^{\ast }$ that returns before another srn call $c^{\prime }$ begins. First, suppose that $c^{\prime }\in {ℒ}^{\prime }$. Then $c^{\prime }\in ℱ$. As $c$ returns before $c^{\prime }$ starts in ${\mathscr{H}}^{\ast }$, $c$ returns before $c^{\prime }$ starts in $ℱ$. Therefore, $c$ occurs before $c^{\prime }$ in ${ℒ}^{\prime }$ and, hence, in $ℒ$ as well. Now suppose that $c^{\prime }\notin {ℒ}^{\prime }$. If $c\in {ℒ}^{\prime }$, then $c$ occurs before $c^{\prime }$ in $ℒ$, since ${ℒ}^{\prime }$ is a prefix of $ℒ$. If $c\notin {ℒ}^{\prime }$, then $c$ occurs before $c^{\prime }$ in $ℒ$, because $c$ starts before $c^{\prime }$ in ${\mathscr{H}}^{\ast }$. Thus, $ℒ$ is a linearization of ${\mathscr{H}}^{\ast }$.

$ℒ$ contains every completed call in ${\mathscr{H}}^{\ast }$, so it contains every completed call in $\mathscr{H}$. Furthermore, each completed call in $\mathscr{H}$ returns the same value as in ${\mathscr{H}}^{\ast }$ and, hence, as in $ℒ$. If an srn call $c$ returns before another srn call $c^{\prime }$ begins in $\mathscr{H}$, then $c$ returns before $c^{\prime }$ in ${\mathscr{H}}^{\ast }$. Therefore, $c$ occurs before $c^{\prime }$ in $ℒ$. Thus, $ℒ$ is a linearization of $\mathscr{H}$.

An important consequence of this lemma is that ${\text{SRN}}_k$ objects have consensus number 1.

For the sake of contradiction, suppose that ${\text{SRN}}_k$ objects have a consensus number of at least 2. This would imply that the consensus task for 2 processes can be solved using ${\text{SRN}}_k$ objects and registers. Thus, by Lemma 22, the consensus task for 2 processes can be solved using any solution to the $(k-1)$-set agreement task for $k$ processes and registers. This contradicts Theorem 1. $◀$