Solving Tasks with Fewer Registers Than Processes

Gafni, Eli; Losa, Giuliano; Raynal, Michel; Taubenfeld, Gadi

doi:10.4230/LIPIcs.OPODIS.2025.21

Solving Tasks with Fewer Registers Than Processes

Eli Gafni

UCLA, Los Angeles, CA, USA Giuliano Losa

Stellar Development Foundation, San Francisco, CA, USA Michel Raynal

Univ. Rennes, Inria, CNRS, IRISA, Rennes, France Gadi Taubenfeld

Reichman University, Herzliya, Israel

Abstract

This paper studies distributed-computing tasks through the lens of space complexity in the read/write wait-free model, defined as the number of multi-reader-multi-writer atomic read/write registers needed to solve a task using a wait-free algorithm. Surprisingly, even though the read/write wait-free model is at the foundation of distributed computing, previous work on space complexity has focused on synchronization primitives stronger than read/write registers or on weaker progress conditions.

The paper reveals that the read/write wait-free model offers a rich space-complexity landscape: (1) assuming non-anonymous processes, it shows that there is an infinite hierarchy of tasks of increasing space complexity; (2) it shows that space complexity separates anonymous from non-anonymous memory; (3) regardless of process or register anonymity, it exhibits a task of space complexity two, which is the minimal non-trivial space complexity; (4) finally, it shows that subcases of the adopt-commit task have different space complexity in non-anonymous memory under bounded wait-freedom.

Keywords and phrases:

Asynchrony, Read/write registers, Wait-freedom, Tasks, Covering argument, Lower bound, Space complexity, Anonymous Processes, Anonymous Memory

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Distributed algorithms

DOI:

10.4230/LIPIcs.OPODIS.2025.21

Event:

29th International Conference on Principles of Distributed Systems (OPODIS 2025)

Editors:

Andrei Arusoaie, Emanuel Onica, Michael Spear, and Sara Tucci-Piergiovanni

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Parallel Computing is the science of breaking down data-processing problems into independent parts that can be performed simultaneously by multiple processors to maximize performance. The nature of Distributed Computing is different: it is the science of (formalized) cooperation among independent computing entities [34]. At its core, it consists of designing and classifying distributed abstractions, each of which captures a specific form of cooperation. For example, Herlihy’s famous wait-free hierarchy [23] classifies distributed abstractions called objects according to the maximum number of wait-free processes that can solve consensus when they have access to instances of the object and read/write registers.

There are a large number of distributed abstractions and computing models in which to study them. However, one of the simplest possible settings is to consider distributed abstractions called tasks in the read/write wait-free model. Tasks are cooperation abstractions in which a number of processes each receive a single input and must produce a single output. The task’s specification relates assignments of inputs to processes to allowed assignments of outputs to processes. To solve a task in the read/write wait-free model, processes must communicate through atomic read/write registers only, and each process that takes sufficiently many steps must eventually output, regardless of what other processes do.

Surprisingly, there is no systematic classification of tasks in this simple setting. Here, Herlihy’s hierarchy is not informative, since consensus is not wait-free solvable with only read/write registers, and therefore such tasks are at level 1 of the consensus hierarchy.

This paper studies the classification of read/write wait-free solvable tasks according to the minimum number of atomic read/write registers needed (without a limit on register size) to solve the task wait-free. We call this number the read/write space complexity of a task (abbreviated space complexity in the rest of the paper). The space complexity of a task may vary depending on whether processes and registers are anonymous or not, and we consider all four possible anonymity combinations. Many previous works study other notions of space complexity (see Section 7), often based on primitives stronger than read/write registers or under progress conditions weaker than wait-freedom, but little is known about the space complexity of tasks in the read/write wait-free model.

Delporte-Gallet et al. [12] show that, for non-anonymous wait-free processes in non-anonymous memory, $n$ registers (where $n$ is the number of processes) are sufficient to solve any read/write wait-free solvable task even if registers are not pre-allocated to processes¹¹1Nevertheless, they make the wrong claim that $n$ registers are also necessary to implement any wait-free solvable task. Thus, at least in the non-anonymous case, space complexity is only interesting when there are fewer registers than processes. Some tasks are known to be implementable wait-free with fewer registers than processes. For example, the splitter [29] and the binary conflict-detector task [4] are solvable wait-free with just $2$ non-anonymous registers; other tasks, such as lattice agreement [5], require $n$ registers [12]. However, beyond these few examples, the space complexity of read/write wait-free solvable tasks has so far not been systematically explored.

The paper shows that the read/write wait-free model offers a rich space-complexity landscape by presenting novel space-complexity separation results:

Section 3 shows that for non-anonymous processes, whether registers are anonymous or not, there is a task of space complexity $k$ for every integer $k>1$ . Thus, assuming non-anonymous processes, every level of the space complexity hierarchy is populated. The lower bound needed for this result is obtained using a classic covering argument in the spirit of Burns and Lynch [7].

Section 4 shows that space complexity separates non-anonymous registers from anonymous registers by showing that, regardless of process anonymity, binary adopt-commit has space complexity 3 if the registers are non-anonymous and space complexity $n$ if the registers are anonymous. This is an interesting result because recent work [26] conjectures that read/write wait-free solvability of tasks, when the number of registers is not constrained, does not depend on register anonymity.

Section 5 presents the contention-detection task, and it shows that it achieves the weakest non-trivial space complexity – i.e., two – regardless of process or register anonymity.

Section 6 shows that space complexity separates sub-cases of the adopt-commit task: assuming each process receives as input one of two values drawn from a set of three values, adopt-commit is solvable bounded wait-free with three non-anonymous registers, but if the two values are drawn from a set of four values, then four registers are needed. Finally, Section 7 surveys related work and Section 8 concludes with open questions.

2 Computation Model

The computing model is the standard asynchronous wait-free model for deterministic, unbounded-state processes communicating using shared atomic, multi-reader-multi-writer (MRMW) read/write registers of unbounded size. The set of processes may be countably infinite or limited to $n$ processes.

A run in the model is a (possibly infinite) sequence of atomic steps. Each step is taken by a single process, which applies either a read or a write operation to a shared register and then updates its private state. A read operation returns the current value of the register, and a write operation takes a value parameter and replaces the current contents of the register with the provided value. Processes run an algorithm, and the operation applied by a process in a step is determined by the algorithm as a function of the local state of the process before the step. Since we focus exclusively on solving tasks, we assume that, in each run, each process initially receives a single input and produces at most one output. When a process outputs, it stops taking steps.

The system is asynchronous, meaning there are no restrictions on the process schedule. In particular, any process may stop taking steps at any point in a run, which may be interpreted as crashing. An algorithm is wait-free when every process that takes sufficiently many steps produces an output, and it is bounded wait-free when there is a fixed constant $c$ such that no process takes more than $c$ steps before producing an output.

A process participates in a run when it takes at least one step, and a run is complete when all participating processes produce an output. An input assignment is a map from a subset of the processes to inputs, and, similarly, an output assignment is a map from a subset of the processes to outputs. A complete run determines an input assignment and an output assignment in the obvious way.

A task is a relation between input assignments and output assignments that have the same domain. An algorithm solves a task when, for each complete run, if the input assignment is in the domain of the task, then the output assignment is in the image of that input assignment. (Note that, since we only consider solving tasks and wait-free algorithms, and since a process can never tell whether another process that has not produced an output will take further steps, it suffices to place requirements on complete runs.)

Each process has a unique natural number called its process identifier. When processes are not anonymous, the algorithm may use this identifier. When processes are anonymous, we forbid the algorithm from using the process identifier.

As recently introduced by Taubenfeld [37], the shared registers may also be anonymous. In this case, each process $p$ is assigned an arbitrary permutation $\sigma_{p}$ of the registers, which is unknown to the processes. When $p$ executes a read or write of a register $r$ , the register that is accessed is not $r$ but $\sigma_{p}(r)$ . If processes are anonymous, we preclude from consideration tasks that assign each process a unique input, as, in this case, each process can use its input as a unique identifier. When both processes and registers are anonymous, we say that the model is fully anonymous [36].

Note that solvability of a task for anonymous processes implies solvability for non-anonymous processes, and that solvability with anonymous registers implies solvability with non-anonymous registers.

Finally, the space complexity of a task in a given variant of the model (anonymous/non-anonymous processes, anonymous/non-anonymous memory, $n$ processes or an infinite number of processes) is the minimum number of registers needed to solve the task in the model variant.

3 For Every $k>1$ , There is a Task of Space Complexity $𝒌$

This section shows that, assuming either finitely or infinitely many non-anonymous processes, for every $k>1$ , there is a task of space complexity $k$ . This holds regardless of register anonymity. To show this, we define the $k$ -bounded lattice agreement task, for $k>0$ , and we show that:

$\blacksquare$

$k$ -bounded lattice agreement is not wait-free solvable with fewer than $k+1$ registers, and
$\blacksquare$

There is a wait-free algorithm (Algorithm 1) that solves $k$ -bounded lattice agreement using $k+1$ anonymous registers in a system of infinitely many non-anonymous processes.

Definition 1.

For every $k\geq 1$ , the $k$ -bounded lattice-agreement task for $n\geq 1$ processes is defined as follows. Processes receive no input, and each participating process outputs a set of process identifiers (possibly of cardinality greater than $k$ ), such that:

$\blacksquare$

Validity. Each participating process outputs a set of participating processes.
$\blacksquare$

Self-inclusion. Each process appears in its own output.
$\blacksquare$

Containment. Every two outputs of cardinality at most $k$ are related by containment.

Note that, for $k>1$ , any algorithm that solves $k$ -bounded lattice agreement also solves $(k-1)$ -bounded lattice agreement, but not necessarily vice versa. Also note that, if there are $n$ processes, then $(n-1)$ -bounded lattice agreement is the same as the classic lattice-agreement task [5] on the lattice of sets of process identifiers.

3.1 Lower Bound: $k+1$ Registers Are Necessary

Theorem 2 (Space Complexity Lower Bound for k-Bounded Lattice Agreement).

For every integer $k\geq 1$ , no read/write wait-free algorithm solves $k$ -bounded lattice agreement for $k+1$ processes using $k$ registers or fewer.

In a nutshell, to prove this theorem, we build a finite run at the end of which each register $i$ , $1\leq i\leq k$ , is about to be overwritten by a distinct process $p_{i}$ , process $p_{1}$ has not written thus far, and process $p_{k+1}\notin\{p_{i}\mid 1\leq i\leq k\}$ has not taken any steps. Then, we schedule $p_{k+1}$ until it outputs. Next, we obliterate any trace that $p_{k+1}$ participated by scheduling the writes of $p_{1},\dots,p_{k}$ . Finally, we let $p_{1}$ run until it outputs. To $p_{1}$ and $p_{k+1}$ , this run is indistinguishable from a run where the other did not participate. Thus $p_{1}$ must output a set not containing $p_{k+1}$ and $p_{k+1}$ must output a set not containing $p_{1}$ ; this violates the containment condition. A full proof appears in [19] and in the full version of this paper.

3.2 Upper Bound: $k+1$ Registers Are Sufficient

This section presents, for every $k>1$ , a wait-free algorithm that solves $k$ -bounded lattice agreement for infinitely many non-anonymous processes using $k+1$ anonymous registers. Pseudocode appears in Algorithm 1.

Algorithm 1

k

-bounded lattice agreement algorithm for finitely or infinitely many non-anonymous processes and anonymous shared registers.

At a high level, the algorithm works as follows. Every process keeps track of the set of processes it has seen so far (local variable seen), and it eventually outputs this set. Until it determines it can output, each process $p$ executes the following loop in which it accesses a shared register array of $k+1$ registers:

1.

First, at line 10, $p$ writes to a shared register (indicated by the cyclic counter $i$ ) a triple consisting of its identifier, a locally unique sequence number (equal to the number of writes it has done so far), and the set of processes it has seen so far.
2.

Second, between lines 13 and 20, $p$ tries to take an atomic snapshot of the shared register array. If successful, as indicated by variable snapshot, the atomic snapshot appears in the variable collect.
3.
Finally, lines 20 to 23:
1. (a)
  
  If $p$ has seen more than $k$ processes (including itself), $p$ outputs.
2. (b)
  
  If $p$ ’s atomic snapshot did not succeed, $p$ goes back to line 13 to try again to obtain an atomic snapshot.
3. (c)
  
  If $p$ ’s atomic snapshot succeeded and, in the snapshot, every shared register contains exactly the set of processes that $p$ has seen so far, then $p$ outputs.
4. (d)
  
  Else, $p$ goes to the next iteration of its main loop (i.e. it jumps back to line 10).

To try to take an atomic snapshot, each process $p$ reads the whole shared array twice in a row, storing the first array read in the local array collect. A process determines that it obtained an atomic snapshot of the array if each register has the same value in both the first and second read. Because processes write their identifier and a sequence number that each process uses only once, no triple is written more than once; this guarantees that no write happened in between the last read at line 14 and the first read at line 17, and thus the collect array is an instantaneous copy of the shared array as it was between those two points in time. This well-known snapshot technique was first presented by Afek et al. [1].

The safety of the algorithm relies on the fact that, once a process $p$ obtains a snapshot in which every register in the shared array contains some process $q$ , because there are $k+1$ registers, as long as only $k$ other processes participate, the registers cannot all be overwritten and $q$ will forever remain in at least one register. Similar reasoning is used by Delporte-Gallet et al. [10] in their SWMR-emulation algorithm. See Appendix A for a rigorous proof.

Wait-freedom intuitively relies on the following facts: (1) the seen set of each process must eventually remain constant (as it can only grow and the process outputs when it reaches a size greater than $k$ ); (2) if a set of processes keep taking steps forever, the one with the smallest seen set must always eventually grow its seen set, or it would output, which contradicts (1). For lack of space, we provide a rigorous proof in the full version of this paper.

4 Space-Complexity Separates Anonymous From Non-Anonymous Memory

This section shows that, whether processes are anonymous or not, the binary adopt-commit task (Binary AC for short) has space complexity 3 when registers are non-anonymous, but it has space complexity $n$ when registers are anonymous. These results establish that there is a space-complexity separation between non-anonymous and anonymous registers.

Definition 3.

In the binary adopt-commit task, each process $p$ receives a bit (0 or 1) as input and must output a pair of the form $(\text{``commit''},b_{p})$ or $(\text{``adopt''},b_{p})$ for some bit $b_{p}$ . When a process $p$ outputs $(\text{``commit''},b_{p})$ , we say that $p$ commits $b_{p}$ , and when $p$ outputs $(\text{``adopt''},b_{p})$ , we say that $p$ adopts $b_{p}$ . Outputs must satisfy the following properties:

1.

Validity. If all participating processes have the same input $v$ , then they all commit $v$ , and
2.

Agreement. If a participating process commits a value $v$ , then every participating process either commits or adopts $v$ .

4.1 Binary AC Has Space Complexity 3 if Registers Are Non-anonymous

In this section, we present an algorithm that solves binary AC using 3 non-anonymous registers for infinitely many anonymous processes, and we show that this is optimal.

Algorithm 2 Binary adopt-commit algorithm for infinitely-many anonymous processes using non-anonymous registers.

Pseudocode appears in Algorithm 2. Processes communicate using three shared registers $A[0]$ , $A[1]$ , and $C$ , all initially containing the value $\bot$ . Each process has two local variables: input, containing the input of the process, and output, eventually containing the output of the process. The algorithm unfolds as follows. Each process $p$ first announces its input by writing to register $A[0]$ if it has input $0$ and to register $A[1]$ if it has input $1$ (line 3). Then, $p$ checks if a different input has been announced (line 4). There are two cases.

First, if $p$ sees no different input, $p$ announces its intent to commit by writing its input to $C$ (line 11), and then checks again (line 12) whether a different input has been announced; if not, $p$ commits its input (line 13), and otherwise, $p$ adopts its input (line 15).

Second, if $p$ notices at line 4 a different input, then $p$ will not try to commit, and instead checks whether a process has declared its intent to commit in register $C$ (line 5); if so, then $p$ adopts the contents of register $C$ (line 6), and otherwise, $p$ adopts its input (line 8).

Theorem 4.

Algorithm 2 is a correct solution to adopt-commit.

The correctness of the algorithm rests on the following basic shared-memory property:

Property 1.

If $R_{1}$ and $R_{2}$ are two different shared registers, if a set of processes $P_{1}$ each write to $R_{1}$ then read from $R_{2}$ , if a disjoint set of processes $P_{2}$ each write to $R_{2}$ then read from $R_{1}$ , and if no other processes write to $R_{1}$ or $R_{2}$ , then either every member of $P_{1}$ reads a write by a member of $P_{2}$ , or vice versa.

The algorithm relies on Property 1 to ensure the following properties of adopt-commit:

1.

At most one value is committed. To see this, instantiate Property 1 with $R_{1}=A[0]$ , $P_{1}$ being the set of processes with input $0$ , $R_{2}=A[1]$ , and $P_{2}$ being the set of processes with input $1$ . By Property 1 and the algorithm, this implies that one of the two sets of processes will never write $C$ , and thus that at most one value is committed.
2.

If a process commits a value $v$ , then every process that adopts a value adopts $v$ . To see this, first note that, by the previous point, only the processes having input $\overline{v}$ are at risk of not adopting $v$ . Next, instantiate Property 1 with $R_{1}=C$ , $P_{1}$ being the set of processes that write $v$ to $C$ , $R_{2}=A[\overline{v}]$ , and $P_{2}$ being the set of processes with input $\overline{v}$ . By the algorithm, all processes that commit belong to $P_{1}$ and never read from $P_{2}$ , and, thus, by Property 1, every member of $P_{2}$ must read $v$ from $C$ .

Finally, it is easy to see that processes adopt or commit inputs of participating processes. ∎

Theorem 5 (Lower bound for solving adopt-commit using non-anonymous registers).

Solving binary adopt-commit wait-free for three or more processes requires at least three registers.

Proof.

Simple covering arguments. Assume, to the contrary, that binary $A C$ can be solved for three processes with two registers. Let $v\in\{0,1\}$ .

$\blacktriangleright$ Claim 1.

A process must write before it terminates when it runs alone.

Proof of Claim 1.

If a process runs solo, it must commit; if it did not write, other processes would have no way to avoid adopting or committing a different value. $\hfill\vartriangleleft$

$\blacktriangleright$ Claim 2.

The first write of processes with the same input must be to the same register, when each runs alone.

Proof of Claim 2.

Assume this is not the case. Let $p_{0}$ , $p_{1}$ , and $p_{2}$ have inputs $v,v,1-v$ , respectively, and suppose $p_{0}$ and $p_{1}$ make their first write to different registers. Run $p_{0}$ and $p_{1}$ until they are about to write. Before they write, run $p_{2}$ until it terminates; $p_{2}$ only sees itself, so it must commit $1-v$ . Let $p_{0}$ and $p_{1}$ each take one step so that the two registers are overwritten, and there is no trace left of $p_{2}$ . $p_{0}$ and $p_{1}$ must then commit $v$ . Contradiction. $\hfill\vartriangleleft$

$\blacktriangleright$ Claim 3.

The first write of processes with different inputs must be to the same register, when each runs alone.

Proof of Claim 3.

Assume this is not the case. Let $p_{0}$ and $p_{1}$ have inputs $v$ and $1-v$ , respectively, and assume that $p_{0}$ and $p_{1}$ make their first write to different registers. After they write, let $p_{0}$ run to completion. For some value $u\in\{0,1\}$ , $p_{0}$ either adopts or commits $u$ . Let $p_{2}$ have input $1-u$ . Now consider a new run, and let $p_{0}$ and $p_{1}$ run until they are about to write for the first time. At that point, run $p_{2}$ until it terminates; $p_{2}$ only sees itself, so it must commit $1-u$ . Let $p_{0}$ and $p_{1}$ each take one step so that the two registers are overwritten, and there is no trace left of $p_{2}$ . Now $p_{0}$ will either adopt or commit $u$ . Contradiction. $\hfill\vartriangleleft$

$\blacktriangleright$ Claim 4.

When a process runs alone, it will not write to both registers.

Proof of Claim 4.

Assume this is not the case. Let $p_{0}$ , $p_{1}$ , and $p_{2}$ have inputs $v,v,1-v$ , respectively. First, run these three processes until they are ready to write for the first time. By Claim 1 and Claim 2, they are ready to write to the same register. Run $p_{0}$ until it is ready to write to the second register. Let $p_{2}$ take one step so that the register written by $p_{0}$ is overwritten, and there is no trace that $p_{0}$ or $p_{1}$ ever participated. Then run $p_{2}$ until it terminates; $p_{2}$ only sees itself, so it must commit $1-v$ . Next, let $p_{0}$ and $p_{1}$ each take one step so that the two registers are overwritten, and there is no trace of $p_{2}$ . Now let $p_{0}$ and $p_{1}$ run to completion; they both must commit $v$ . Contradiction. $\hfill\vartriangleleft$

We are now ready to complete the proof of the theorem. Assume $p_{0}$ and $p_{1}$ have inputs $v$ and $1-v$ , respectively. First, run both processes until they are about to write. By Claim 2, they are about to write to the same register. Next, run $p_{0}$ until it terminates; $p_{0}$ only sees itself, so it must commit $v$ . By Claim 3, $p_{0}$ writes to only one register. Next, let $p_{1}$ take one step so that the register written by $p_{0}$ is overwritten, and there is no trace of $p_{0}$ . Finally, run $p_{1}$ until it terminates; $p_{1}$ only sees itself, so it must commit $1-v$ . Contradiction. $\hfill\blacktriangleleft$

Algorithm 3 Algorithm solving binary adopt-commit for

n

anonymous processes using an implementation of lattice-agreement. Overlines mean binary complement.

4.2 Binary AC Has Space Complexity $n$ if Registers Are Anonymous

In this section, we show that binary AC has space complexity $n$ if registers are anonymous: First, we present a wait-free adopt-commit algorithm for $n$ processes using $n$ registers in the fully-anonymous model. Second, we show that a space complexity of $n$ is optimal if registers are anonymous (even if processes are non-anonymous).

The solution to binary AC using $n$ anonymous registers appears in Algorithm 3. The idea is to emulate the non-memory-anonymous algorithm of the previous section (Algorithm 2) in the fully-anonymous model by announcing inputs and intents to commit, not by directly writing to registers, but by using the lattice-agreement task.

In the lattice-agreement task, each participating process receives a set of values as input and must output a set of values such that:

1.

Every output is a union of input sets of participating processes,
2.

Each process outputs a set that contains its input set, and
3.

Every two output sets are related by containment.

To emulate Algorithm 2 using lattice agreement, each process announces its input by calling lattice agreement with a singleton set containing its input. It then uses the set returned by lattice agreement to check whether another input was announced. To announce its intent to commit, a process calls lattice agreement a second time as a fresh process, this time providing as input the set consisting of the previous lattice-agreement output and a tuple indicating its intent to commit its input. Again, it checks whether a conflicting input was announced by checking whether a conflicting input appears in the set returned by its second lattice-agreement invocation.

Theorem 6.

Algorithm 3 is a correct fully-anonymous implementation of adopt-commit.

Proof.

The algorithm works for the same reason as Algorithm 2, because lattice agreement gives us a property analogous to Property 1:

Property 2.

If $e_{1}$ and $e_{2}$ are two different elements, if each process in a set $P_{1}$ calls lattice agreement with a set containing $e_{1}$ , and if each process in a disjoint set $P_{2}$ calls lattice agreement with a set containing $e_{2}$ , then either every member of $P_{1}$ receives, in return, a set containing $e_{2}$ or every member of $P_{2}$ receives, in return, a set containing $e_{1}$ .

Using Property 2 instead of Property 1, we can repeat the correctness proof of Algorithm 2. $\hfill\blacktriangleleft$

It now remains to implement lattice agreement for $n$ processes in the fully-anonymous model, including the ability for processes to call the algorithm twice as two different virtual processes. The algorithm appears in Algorithm 4. In order to use only $n$ registers, it assumes that a second call by a process provides an input that is a superset of the previous output of the process. Note that Algorithm 3 guarantees this is the case.

Algorithm 4 is similar to Algorithm 1: we have an array of $n$ registers (instead of $k+1$ in Algorithm 1) and each process $p$ repeatedly (a) writes the set of all inputs it has seen so far to one register selected round-robin (line 10) and then (b) attempts to obtain an atomic snapshot of the array (lines 13 to 21, as described below); $p$ stops and outputs the set of inputs it has seen so far when $p$ is able to obtain an atomic snapshot of the array such that each register contains exactly the set of inputs that $p$ has seen so far (line 25). Since $p$ ’s second invocation contains its previous output, there are only $n-1$ processes left that can obliterate $p$ ’s output. Since there are $n$ registers and processes have to read the whole array again after they write, $p$ ’s output will remain in at least one register, and the containment property of lattice agreement holds. It is easy to see that wait-freedom holds, as, contrary to the setting of Algorithm 1, there are only a fixed number of invocations.

Algorithm 4 Lattice-agreement algorithm for

n

anonymous processes using

n

anonymous registers. The algorithm allows processes to run the algorithm multiple times as new virtual processes, as long as each process provides as input a superset of its last output.

Finally, we now explain how Algorithm 4 obtains atomic snapshots of the array. In Algorithm 1, each process attempts to obtain an atomic snapshot of the array using two successive reads of the whole array, which, if identical, indicate a successful atomic snapshot. This works because each write is unique, as each process includes its identifier and a unique sequence number. With anonymous processes, processes obviously cannot include a unique process identifier in their write, and two successive identical reads of the whole array no longer guarantee an atomic snapshot because the same value may be written by multiple processes (we have the famous “ABA problem”, as described e.g. in [28]). Luckily, a small change suffices to obtain atomic snapshots in the fully-anonymous model: as first observed by Ruppert and Guerraoui [21], obtaining $n(n-1)+2$ identical reads of the whole register array guarantees an atomic snapshot, because, thanks to the sequence numbers, each value may be written at most $n-1$ times while the process reads. Thus, instead of reading the array twice and declaring that we have a snapshot if the reads are identical, we read the array $n(n-1)+2$ times and declare that we have a snapshot if all the reads are identical.

Theorem 7 (Lower bound for anonymous registers).

When registers are anonymous, solving wait-free binary adopt-commit for $n$ processes requires at least $n$ registers.

Proof.

We use a simple covering argument. Assume, to the contrary, that it can be solved with fewer than $n$ anonymous registers. Let the input of $p_{0}$ be 0, and the input of all the other $n-1$ processes be 1. Run all $n-1$ processes with input 1 until each is ready to write for the first time, and arrange the assignment of the anonymous registers to the processes so that all of the registers are ready to be written by at least one of these $n-1$ processes. Run $p_{0}$ solo until it terminates; $p_{0}$ only sees itself, so it must output the pair $\langle commit,0\rangle$ . Let each of the other processes take one step so that all the registers are overwritten, and there is no trace that $p_{0}$ ever participated. Now, let all the $n-1$ processes run to completion, and, by definition, they all must output $\langle commit,1\rangle$ . Contradiction. $\hfill\blacktriangleleft$

5 A Task Achieving Minimal Space Complexity in All Models

This section shows that there is a task that has space complexity 2 in all the models of the paper. This is the minimal non-trivial space complexity achievable. Indeed, no meaningful synchronization is possible with only one register, as we can always create a run in which each process obliterates any trace of other participating processes and then terminates.

Definition 8.

We define the contention detection task (abbreviated CD) as follows. Each participating process $p$ receives an input value (which may or may not be unique). Each participating process must produce an output that is the input of some participating process. Moreover, at most one participating process $p$ is such that (a) $p$ outputs its own input, and (b) no other participating process $q\neq p$ has the same input as $p$ .

For example, if participating processes receive unique inputs, then at most one process outputs its input. However, if, e.g., three processes $p_{1}$ , $p_{2}$ , and $p_{3}$ participate and $p_{1}$ and $p_{2}$ receive the same input $v$ , then all three processes may output their own input.

Theorem 9.

Contention detection has space complexity 2 in all four models of the paper.

Proof.

For the lower bound, it is easy to see that CD cannot be solved with just one register: schedule two processes until they are poised to write, then let one go and terminate, and finally let the other go and terminate. The processes do not learn about each other’s existence, and thus each must return its own input, which violates the specification of CD if their inputs are different.

For the upper bound, the algorithm of Algorithm 5 solves contention detection for arbitrarily many anonymous processes using two anonymous registers. To prove the correctness of the algorithm, assume, toward a contradiction, that there are two processes $p$ and $q$ such that $p$ outputs its own input $v_{p}$ , no other process has input $v_{p}$ , process $q$ outputs its own input $v_{q}\neq v_{p}$ , and no other process has input $v_{q}$ .

Remember that registers are anonymous: each access by a process $p$ to a register $r_{i}$ in fact accesses register $\sigma_{p}(i)$ , where $\sigma_{p}$ is an unknown permutation of the registers.

First, note that neither $p$ nor $q$ outputs at line 6, and thus they both output at line 8. To see this, suppose toward a contradiction that $p$ outputs at line 6. Then $p$ outputs the contents of register $\sigma_{p}(r_{2})$ . But $p$ has not written to $\sigma_{p}(r_{2})$ , and thus it must output the input of another process. Since no other process has the same input as $p$ , we conclude that $p$ does not output its own input. This is a contradiction. The situation is similar for $q$ .

Next, suppose, without loss of generality, that $p$ executes line 8 after $q$ executes that same line. There are two cases: either $\sigma_{p}=\sigma_{q}$ or $\sigma_{p}\neq\sigma_{q}$ .

Suppose that $\sigma_{p}=\sigma_{q}$ . Then $q$ must execute line 8 before $p$ ’s first write at line 3, otherwise either $p$ or $q$ would not read its own input at line 8. But then $p$ must read a non- $\bot$ value at line 4 and thus output at line 6. This is a contradiction.

Suppose that $\sigma_{p}\neq\sigma_{q}$ . Then $q$ must execute its write at line 7 before $p$ writes at line 3 (otherwise $p$ cannot overwrite it and would read it). But then $q$ must have written at line 3 before $p$ reads at line 4, and thus $p$ must read a non- $\bot$ value at line 4. Thus $p$ outputs at line 6, which is a contradiction. $\hfill\blacktriangleleft$

Algorithm 5 Algorithm solving contention-detection for an infinite number of anonymous processes using two anonymous registers.

6 A Space-Complexity Separation Among Sub-Cases of Adopt-Commit

Section 4 presented tight space lower bounds for binary adopt-commit that reveal a space-complexity separation between anonymous and non-anonymous registers. This section continues our study of adopt-commit, this time finding a space-complexity separation (whether processes are anonymous or not) in non-anonymous memory between two variants of adopt-commit, $(3,2)$ -adopt-commit and $(4,2)$ -adopt-commit, which differ only in the range of values from which inputs may be drawn.

Definition 10.

For every integer $k\geq 2$ and integer $\ell$ with $2\leq\ell\leq k$ , we consider the task of $k$ -valued adopt-commit with at most $\ell$ inputs, denoted $(k,\ell)$ -adopt-commit (in short $(k,\ell)$ -AC). This task is the adopt-commit task with an additional restriction on the possible combinations of inputs that may be received: Each process receives as input one of $\ell$ values drawn from the range $\{0,1,\dots,k-1\}$ . In other words, we restrict ourselves to input assignments that contain at most $\ell$ different values, each in the range $\{0,1,\dots,k-1\}$ .

Note that traditional adopt-commit, in which inputs come from an arbitrary set and processes may all receive different inputs, solves all $(k,\ell)$ -AC tasks.

Next, we show that $(3,2)$ -adopt-commit has strictly lower space complexity than $(4,2)$ -adopt-commit. We start by presenting Algorithm 6, which solves $(3,2)$ -adopt-commit.

Algorithm 6 is similar in principle to Algorithm 2: we have 3 shared registers, and processes use two of them to announce their input and the third to announce their intent to commit. However, since there are 3 possible input values instead of 2, it is no longer possible to statically reserve a unique register per input and an additional register for the commit value (we would need 4 registers in total). Nevertheless, we know that only 2 of the 3 values will be in play. The idea is thus to associate each register with a unique input value, knowing that after detecting which two input values $v_{1}$ and $v_{2}$ are present, we can use the remaining register, denoted $\texttt{CReg}(v_{1},v_{2})$ , as the commit register to play a role analogous to register $C$ in Algorithm 2.

But where does a process that does not detect any other value, and thus cannot compute which register is the commit register, announce its intent to commit? The solution is to write its input value in all the registers. This, however, risks overwriting the announcement of a potential competing value. To avoid this problem, we organize the registers in a ring and instruct processes to write in the ring order, starting from the register assigned to their input value. This ensures that only the value that comes directly after the other value in the ring may be overwritten. In the case of adopt, giving priority to the non-overwritable value (see lines 28 to 31) ensures that, should that value commit, we will not adopt a contradictory value.

Algorithm 6 Algorithm solving (3,2)-adopt-commit for an infinite number of anonymous processes using three non-anonymous registers numbered 0, 1, and 2.

Theorem 11.

Algorithm 6 is a bounded wait-free solution to $(3,2)$ -adopt-commit.

Proof.

If all processes have the same input, then it is easy to see that all commit their input and we are done. So, assume that there are two different inputs $\{v_{1},v_{2}\}\subseteq\{0,1,2\}$ . Let $c$ be the missing value (i.e., such that $\{0,1,2\}\setminus\{v_{1},v_{2}\}=\{c\}$ ). Note that $c=\texttt{CReg}(v_{1},v_{2})$ , i.e., register $c$ is the commit register.

First, note that at most one value is ever written to the commit register $c$ . To see this, let $b=(c-1)\mod 3$ (i.e. $b$ is the predecessor of $c$ in the ring) and let $a$ be the other input value. We have two cases. First, assume that a process $p$ with input $b$ first writes to register $c$ . Then $p$ did not find value $a$ in any register before writing to register $c$ . Thus, any process $p^{\prime}$ with input $a$ must still read register $b$ before writing to it; that read will return value $b$ and thus process $p^{\prime}$ will not proceed to registers $b$ and $c$ . Second, assume that a process $p$ with input $a$ first writes to register $c$ . This means that, when $p$ last read, register $a$ contained value $a$ and no process $p^{\prime}$ with input $b$ had written yet; therefore, any such process $p^{\prime}$ must read value $a$ and will never attempt to write to $c$ .

Next, observe that a process that commits must have written its input to register $c$ (because it writes its input to all registers in that case). Thus, because at most one value is ever written to register $c$ , every process that commits must commit the same value.

Next, when a process $p$ reaches line 25, if another process committed a value $v$ , then $p$ will find $v$ in register $c$ and adopt it. It remains to show that if $p$ adopts a value on lines 29 or 31, then no process later commits a different value. Note that, in this case, no process has written to register $c$ yet. Moreover, the value adopted by $p$ is never obliterated, because $p$ chooses the earlier value in the cyclic write order. Thus, any process $q$ that commits after $p$ adopts must first read $p$ ’s adopted value. Hence, $q$ commits $p$ ’s value.

Finally, since it has no loops, the algorithm is trivially bounded wait-free. $\hfill\blacktriangleleft$

Next, we show that $(4,2)$ -adopt-commit has strictly higher space complexity than $(3,2)$ -adopt-commit:

Theorem 12.

No bounded wait-free algorithm solves $(4,2)$ -adopt-commit using only 3 non-anonymous registers in a system of infinitely many non-anonymous processes.

Proof.

Suppose, towards a contradiction, that there is a wait-free algorithm solving $(4,2)$ -AC using 3 non-anonymous registers for infinitely many non-anonymous processes.

First, note that we easily get a contradiction if some process never writes. Thus, we assume that every process writes at least once.

Next, note that, for each input value $v$ , there is a register $r_{v}$ such that there is an infinite set of processes $Q_{v}$ such that, for every $q\in Q_{v}$ , if $q$ has input $v$ then, in a solo execution, $q$ ’s first write is to $r_{v}$ . Therefore, because there are 3 registers and 4 different input values, by the Pigeonhole Principle, there are two different input values $v_{1}$ and $v_{2}$ , a register $r$ , and two unbounded, disjoint sequences of processes $Q_{1}=q^{1}_{1},q^{1}_{2},\dots$ and $Q_{2}=q^{2}_{1},q^{2}_{2},\dots$ such that, for every $i$ :

$\blacksquare$

if $q^{1}_{i}$ has input $v_{1}$ , then the first write of $q^{1}_{i}$ in a solo run is to register $r$ , and
$\blacksquare$

if $q^{2}_{i}$ has input $v_{2}$ , then the first write of $q^{2}_{i}$ in a solo run is to register $r$ .

Next, let $c$ be a constant such that each process produces an output in at most $c$ of its own steps (which must exist, since the algorithm is bounded wait-free). Hence, each process reads at most $c$ times.

Now consider the executions in which the participating set consists of 3 processes $p_{1}$ , $p_{2}$ , and $p_{3}$ , each with input drawn from $\{v_{1},v_{2}\}$ , and an additional $3c$ processes from $Q_{1}$ , each with input $v_{1}$ , and an additional $3c$ processes from $Q_{2}$ , each with input $v_{2}$ (so we have $3+6c$ participating processes in total). Let the $6c$ processes of $Q_{1}$ and $Q_{2}$ run until they are all poised on register $r$ , ready to perform their first write. Now let $p_{1}$ , $p_{2}$ , and $p_{3}$ run, but each time one of them, say $p$ , reads register $r$ : if $p$ has input $v_{1}$ , then arrange for a member of $Q_{1}$ who has never written to write to $r$ just before $p$ ’s read; similarly, if $p$ has input $v_{2}$ , arrange for a member of $Q_{2}$ who has never written to write to $r$ just before $p$ ’s read.

To $p_{1}$ , $p_{2}$ , and $p_{3}$ , such executions are indistinguishable from executions where only $p_{1}$ , $p_{2}$ , and $p_{3}$ participate and where, instead of reading $r$ , each process just behaves as if it read its input value, and where processes just skip writing $r$ . Conversely, it is easy to see that, for each such execution, there is an execution of the original algorithm with $3+6c$ processes, as described above, that is indistinguishable to $p_{1}$ , $p_{2}$ , and $p_{3}$ . Thus we obtain an algorithm that solves the binary adopt-commit task for 3 processes using only 2 non-anonymous registers. This contradicts Theorem 5. $\hfill\blacktriangleleft$

7 Related Work

There is a long list of works that study related notions of space complexity. They differ from this work in one or more aspects: they consider communication primitives other than MRMW registers (e.g., test-and-set objects), they consider progress conditions other than wait-freedom (e.g., obstruction-freedom), they consider problems that are not tasks (e.g., mutual exclusion), or they measure the size of registers rather than their number. We now give an overview of the most relevant results.

Space complexity as number of registers.

In one of the earliest results in the field, Burns and Lynch [7] show, using a so-called “covering argument”, that $n$ atomic read/write registers are necessary and sufficient for mutual exclusion among asynchronous processes.

A series of papers [18, 41, 20, 16] study the number of MRMW registers needed to solve consensus under variants of obstruction-freedom, culminating in a lower bound of $n$ registers [16] for nondeterministic solo-terminating consensus.

Other works generalize this line of inquiry to set-agreement. Delporte-Gallet et al. [11] and Bouzid et al. [6] give algorithms for $n$ -valued $x$ -obstruction-free $k$ -set agreement using $n-k+x$ registers. Ellen et al. [16] give a lower bound of $\lfloor\frac{n-x}{k+1-x}\rfloor+1$ registers needed to solve $n$ -valued $k$ -set agreement under $x$ -obstruction-freedom. Their proof relies on a novel simulation to reduce the lower bound to the impossibility of read/write wait-free $k$ -set agreement.

Ellen et al. [14] consider instructions, such as read, write, fetch-and-increment, test-and-set, write-max, etc., each of which can be applied to any register given as a parameter. Their results include upper and lower bounds on the number of registers required for solving obstruction-free $n$ -valued consensus among $n$ processes, for various sets of instructions (e.g., given read-max and write-max instructions, two registers are necessary and sufficient to solve obstruction-free $n$ -valued consensus among $n$ processes).

Two papers study the number of registers needed to solve problems when only read-write instructions are allowed during uncontended operations, but more powerful instructions are allowed if there is contention. Luchangco et al. [27] show that the wait-free CAS object needs only a constant number of registers. Capdevielle et al. [8] show that, if processes are anonymous, then the space complexity depends non-trivially on the number of processes and the maximal number of input values allowed.

Fatourou et al. [17] show that $m$ registers are necessary and sufficient for wait-free $m$ -valued atomic snapshot (which is not a task). Thus, instances of the $m$ -valued atomic snapshot problem form an infinite space hierarchy in the read/write wait-free model, similarly to the hierarchy of Section 3. However, it is not clear how this result could be turned into a result about tasks. Ellen et al. [13] and Helmi et al. [22] study the number of registers needed to implement wait-free and obstruction-free timestamp objects.

In a preamble to this paper, the same authors [19] propose the notion of a stranger-free task and show that their wait-free solution requires $n$ registers. They also show that $k$ -bounded lattice agreement is stranger-free for $k+1$ processes, and thus that it requires at least $k+1$ registers.

Space complexity as number of objects.

Jayanti et al. [24] study the number of base objects needed for non-blocking randomized implementations of higher-level objects, for some particular sets of objects that they define. Ovens studies the space complexity of consensus and set-agreement using base objects such as swap or test-and-set [32, 33, 30, 31].

Tasks solvable wait-free with fewer registers than processes.

The splitter task of Moir and Anderson [29] has a wait-free implementation for an unbounded number of processes using only two non-anonymous registers. Lamport [25] previously described a similar construction.

Aspnes and Ellen [4] study the step complexity of adopt-commit, but their work also contains implementations of tasks with a fixed number of registers. They implement a binary conflict detector for anonymous processes using 2 non-anonymous registers, and generalize to a $k!$ -valued conflict detector using $k$ non-anonymous registers. They also implement adopt-commit using a conflict detector and 2 additional registers. This means 4 non-anonymous registers for binary adopt-commit and $k+2$ non-anonymous registers for $k!$ -valued adopt-commit, which gives an upper bound of $O(\log(k)/\log(\log(k)))$ on the space complexity of $k$ -valued adopt-commit for any number of anonymous processes.

Register allocation.

As we have seen in this paper, a major difficulty when trying to solve a task for $n$ processes using fewer than $n$ shared read/write registers is that processes may overwrite each other. A similar difficulty arises even with $n$ or more registers if the registers are not a priori allocated to unique processes. Delporte-Gallet et al. [12] present a non-blocking algorithm that emulates pre-allocated registers using $n$ non-pre-allocated registers, and show that this is optimal. Subsequent work [10] presents an adaptive register-allocation algorithm for an unknown $n$ that uses a number of non-pre-allocated registers that is linear in the number of participating processes.

Anonymous memory.

Taubenfeld [37, 39] recently asked what coordination can be achieved, and how, if there is no a priori agreement among processes about the names (or numbering) of shared registers; in this case, we say that the registers are anonymous. An interesting phenomenon arising only with anonymous memory is that a problem may be solvable with some number $k$ of registers but not with $k+1$ registers. For example, Taubenfeld [39] shows that deadlock-free mutual exclusion for two processes is solvable with an odd number of registers but not with an even number of registers. Recent work [40, 37, 38] gives a number of impossibility results separating anonymous memory from non-anonymous memory, but none are for wait-free computation.

The fully-anonymous model, where both processes and registers are anonymous, was first investigated by Raynal and Taubenfeld [35, 36]. Losa and Gafni [26] propose a fully-anonymous lattice-agreement algorithm in this model; Algorithm 4 provides a simpler solution based on an idea of Guerraoui and Ruppert [21].

Register size.

In a recent paper, Delporte-Gallet et al. [9] investigate the distributed-computability implications of bounding not the number of registers but their size. Their results include the observation that 1-bit registers are universal for 1-resilient computation but not for wait-free computation. Ellen et al. [15] consider a read-modify-write object holding $m$ bits and study the solvability of the signal-detection problem depending on $m$ . Aksenov et al. and Anoprenko et al. study the implementation of queues and unique IDs, respectively, from bounded registers [2, 3].

8 Future Work

In Section 3, we have exhibited an infinite space-complexity hierarchy in the case of non-anonymous processes. Thus, the next questions to ask are whether there are infinite space-complexity hierarchies in the process-anonymous case and in the fully-anonymous case. Those questions remain open, but the paper and related work provide some initial clues.

With anonymous processes and non-anonymous registers, we have shown that CD has complexity two (Section 5) and binary adopt-commit has space complexity three (Section 4.1). In Section 6, we have shown that $(3,2)$ -adopt-commit is solvable with three registers but $(4,2)$ -adopt-commit is not. Aspnes and Ellen [4] implement $k!$ -valued adopt-commit (i.e., $(k!,k!)$ -adopt-commit) using $k+2$ registers. This suggests an interesting space-complexity hierarchy among $(k,\ell)$ -adopt-commit tasks.

Under full anonymity, the $(3,2)$ -adopt-commit and $(k!,k!)$ -adopt-commit algorithms mentioned above do not work. However, we have shown that CD has space complexity two (Section 5) and that binary adopt-commit has space complexity $n$ (Section 4.2).

Finally, as shown by Taubenfeld [39], the mutual exclusion problem (which is not a task) for two processes is solvable for symmetric processes only with an odd number of anonymous registers. Thus, with anonymous memory, it is likely worthwhile to investigate space-complexity as a vector of natural numbers describing for which numbers of registers the task is solvable.

References

[1] Yehuda Afek, Hagit Attiya, Danny Dolev, Eli Gafni, Michael Merritt, and Nir Shavit. Atomic snapshots of shared memory. Journal of the ACM, 40(4):873–890, September 1993. doi:10.1145/153724.153741.
[2] Vitaly Aksenov, Nikita Koval, Petr Kuznetsov, and Anton Paramonov. Memory Bounds for Concurrent Bounded Queues. In Proceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming, PPoPP ’24, pages 188–199, New York, NY, USA, February 2024. Association for Computing Machinery. doi:10.1145/3627535.3638497.
[3] Michael Anoprenko, Petr Kuznetsov, and Vitaly Aksenov. Brief Announcement: Optimal Construction of Unique Identifiers from Bounded Registers. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC ’25, pages 62–65, New York, NY, USA, June 2025. Association for Computing Machinery. doi:10.1145/3732772.3733539.
[4] James Aspnes and Faith Ellen. Tight Bounds for Adopt-Commit Objects. Theory of Computing Systems, 55(3):451–474, October 2014. doi:10.1007/s00224-013-9448-1.
[5] Hagit Attiya, Maurice Herlihy, and Ophir Rachman. Atomic snapshots using lattice agreement. Distributed Computing, 8(3):121–132, March 1995. doi:10.1007/BF02242714.
[6] Zohir Bouzid, Michel Raynal, and Pierre Sutra. Anonymous obstruction-free (n, k)-set agreement with $$n-k+1$$atomic read/write registers. Distributed Computing, 31(2):99–117, April 2018. doi:10.1007/s00446-017-0301-7.
[7] J. E. Burns and N. A. Lynch. Bounds on Shared Memory for Mutual Exclusion. Information and Computation, 107(2):171–184, December 1993. doi:10.1006/inco.1993.1065.
[8] Claire Capdevielle, Colette Johnen, Petr Kuznetsov, and Alessia Milani. On the Uncontended Complexity of Anonymous Consensus. In DROPS-IDN/v2/Document/10.4230/LIPIcs.OPODIS.2015.12. Schloss-Dagstuhl - Leibniz Zentrum für Informatik, 2016. doi:10.4230/LIPIcs.OPODIS.2015.12.
[9] Carole Delporte-Gallet, Hugues Fauconnier, Pierre Fraigniaud, Sergio Rajsbaum, and Corentin Travers. The Computational Power of Distributed Shared-Memory Models with Bounded-Size Registers. In Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing, PODC ’24, pages 310–320, New York, NY, USA, June 2024. Association for Computing Machinery. doi:10.1145/3662158.3662789.
[10] Carole Delporte-Gallet, Hugues Fauconnier, Eli Gafni, and Leslie Lamport. Adaptive register allocation with a linear number of registers. In International Symposium on Distributed Computing, pages 269–283. Springer, 2013. doi:10.1007/978-3-642-41527-2_19.
[11] Carole Delporte-Gallet, Hugues Fauconnier, Eli Gafni, and Sergio Rajsbaum. Black art: Obstruction-free k-set agreement with $|$ mwmr registers $|$ < $|$ proccesses $|$ . In Vincent Gramoli and Rachid Guerraoui, editors, Networked Systems - First International Conference, NETYS 2013, Marrakech, Morocco, May 2-4, 2013, Revised Selected Papers, volume 7853 of Lecture Notes in Computer Science, pages 28–41, Berlin, Heidelberg, 2013. Springer. doi:10.1007/978-3-642-40148-0_3.
[12] Carole Delporte-Gallet, Hugues Fauconnier, Eli Gafni, and Sergio Rajsbaum. Linear Space Bootstrap Communication Schemes. In Davide Frey, Michel Raynal, Saswati Sarkar, Rudrapatna K. Shyamasundar, and Prasun Sinha, editors, Distributed Computing and Networking, pages 363–377, Berlin, Heidelberg, 2013. Springer. doi:10.1007/978-3-642-35668-1_25.
[13] Faith Ellen, Panagiota Fatourou, and Eric Ruppert. The space complexity of unbounded timestamps. Distributed Computing, 21(2):103–115, July 2008. doi:10.1007/s00446-008-0060-6.
[14] Faith Ellen, Rati Gelashvili, Nir Shavit, and Leqi Zhu. A complexity-based classification for multiprocessor synchronization. Distributed Computing, 33(2):125–144, April 2020. doi:10.1007/s00446-019-00361-3.
[15] Faith Ellen, Rati Gelashvili, Philipp Woelfel, and Leqi Zhu. Space Lower Bounds for the Signal Detection Problem. In Rolf Niedermeier and Christophe Paul, editors, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), volume 126 of Leibniz International Proceedings in Informatics (LIPIcs), pages 26:1–26:13, Dagstuhl, Germany, 2019. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.STACS.2019.26.
[16] Faith Ellen, Rati Gelashvili, and Leqi Zhu. Revisionist Simulations: A New Approach to Proving Space Lower Bounds. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC ’18, pages 61–70, New York, NY, USA, July 2018. Association for Computing Machinery. doi:10.1145/3212734.3212749.
[17] Panagiota Fatourou, Faith Fich, and Eric Ruppert. Space-optimal multi-writer snapshot objects are slow. In Proceedings of the Twenty-First Annual Symposium on Principles of Distributed Computing, PODC ’02, pages 13–20, New York, NY, USA, July 2002. Association for Computing Machinery. doi:10.1145/571825.571828.
[18] Faith Fich, Maurice Herlihy, and Nir Shavit. On the space complexity of randomized synchronization. J. ACM, 45(5):843–862, September 1998. doi:10.1145/290179.290183.
[19] Eli Gafni, Giuliano Losa, Michel Raynal, and Gadi Taubenfeld. Brief Announcement: Stranger-Free Tasks. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC ’25, pages 203–206, New York, NY, USA, June 2025. Association for Computing Machinery. doi:10.1145/3732772.3733545.
[20] Rati Gelashvili. On the optimal space complexity of consensus for anonymous processes. Distributed Computing, 31(4):317–326, August 2018. doi:10.1007/s00446-018-0331-9.
[21] Rachid Guerraoui and Eric Ruppert. What Can Be Implemented Anonymously? Technical report, EPFL, 2004. URL: https://infoscience.epfl.ch/handle/20.500.14299/214730.
[22] Maryam Helmi, Lisa Higham, Eduardo Pacheco, and Philipp Woelfel. The Space Complexity of Long-Lived and One-Shot Timestamp Implementations. J. ACM, 61(1):7:1–7:25, January 2014. doi:10.1145/2559904.
[23] Maurice Herlihy. Wait-free Synchronization. ACM Transactions on Programming Languages and Systems, 13(1):124–149, January 1991. doi:10.1145/114005.102808.
[24] Prasad Jayanti, King Tan, and Sam Toueg. Time and Space Lower Bounds for Nonblocking Implementations. SIAM Journal on Computing, 30(2):438–456, January 2000. doi:10.1137/S0097539797317299.
[25] Leslie Lamport. A fast mutual exclusion algorithm. ACM Trans. Comput. Syst., 5(1):1–11, January 1987. doi:10.1145/7351.7352.
[26] Giuliano Losa and Eli Gafni. Brief Announcement: Understanding Read-Write Wait-Free Coverings in the Fully-Anonymous Shared-Memory Model. In Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing, PODC ’24, pages 465–468, New York, NY, USA, June 2024. Association for Computing Machinery. doi:10.1145/3662158.3662786.
[27] Victor Luchangco, Mark Moir, and Nir Shavit. On the Uncontended Complexity of Consensus. In Faith Ellen Fich, editor, Distributed Computing, pages 45–59, Berlin, Heidelberg, 2003. Springer. doi:10.1007/978-3-540-39989-6_4.
[28] Maged M. Michael and Michael L. Scott. Simple, fast, and practical non-blocking and blocking concurrent queue algorithms. In Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing - PODC ’96, pages 267–275, Philadelphia, Pennsylvania, United States, 1996. ACM Press. doi:10.1145/248052.248106.
[29] Mark Moir and James H. Anderson. Wait-free algorithms for fast, long-lived renaming. Science of Computer Programming, 25(1):1–39, October 1995. doi:10.1016/0167-6423(95)00009-H.
[30] Sean Ovens. The Space Complexity of Scannable Binary Objects. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, PODC’21, pages 509–519, New York, NY, USA, July 2021. Association for Computing Machinery. doi:10.1145/3465084.3467916.
[31] Sean Ovens. The Space Complexity of Scannable Objects with Bounded Components. In Christian Scheideler, editor, 36th International Symposium on Distributed Computing (DISC 2022), volume 246 of Leibniz International Proceedings in Informatics (LIPIcs), pages 30:1–30:18, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.DISC.2022.30.
[32] Sean Ovens. Brief Announcement: The Space Complexity of Set Agreement Using Swap. In Rotem Oshman, editor, 37th International Symposium on Distributed Computing (DISC 2023), volume 281 of Leibniz International Proceedings in Informatics (LIPIcs), pages 46:1–46:6, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.DISC.2023.46.
[33] Sean Ovens. The Space Complexity of Consensus from Swap. J. ACM, 71(1):1:1–1:26, February 2024. doi:10.1145/3631390.
[34] Michel Raynal. About Informatics, Distributed Computing, and Our Job: A Personal View. In Sergio Rajsbaum, Alkida Balliu, Joshua J. Daymude, and Dennis Olivetti, editors, Structural Information and Communication Complexity, pages 33–45, Cham, 2023. Springer Nature Switzerland. doi:10.1007/978-3-031-32733-9_3.
[35] Michel Raynal and Gadi Taubenfeld. Mutual exclusion in fully anonymous shared memory systems. Information Processing Letters, 158:105938, June 2020. doi:10.1016/j.ipl.2020.105938.
[36] Michel Raynal and Gadi Taubenfeld. Fully Anonymous Consensus and Set Agreement Algorithms. In Chryssis Georgiou and Rupak Majumdar, editors, Networked Systems, Lecture Notes in Computer Science, pages 314–328, Cham, 2021. Springer International Publishing. doi:10.1007/978-3-030-67087-0_20.
[37] Gadi Taubenfeld. Coordination Without Prior Agreement. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC ’17, pages 325–334, New York, NY, USA, July 2017. Association for Computing Machinery. doi:10.1145/3087801.3087807.
[38] Gadi Taubenfeld. Set Agreement Power Is Not a Precise Characterization for Oblivious Deterministic Anonymous Objects. In Michele Flammini and Keren Censor-Hillel, editors, Structural Information and Communication Complexity, volume 11639, pages 293–308. Springer International Publishing, Cham, 2019. doi:10.1007/978-3-030-24922-9_20.
[39] Gadi Taubenfeld. Anonymous Shared Memory. Journal of the ACM, 69(4):24:1–24:30, August 2022. doi:10.1145/3529752.
[40] Gadi Taubenfeld. Memory-Anonymous Starvation-Free Mutual Exclusion: Possibility and Impossibility Results, September 2023. doi:10.48550/arXiv.2309.11337.
[41] Leqi Zhu. A tight space bound for consensus. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’16, pages 345–350, New York, NY, USA, June 2016. Association for Computing Machinery. doi:10.1145/2897518.2897565.

Appendix A Proof of Safety of the Bounded Lattice-Agreement Algorithm

In this section, we prove that Algorithm 1 is a safe implementation of $k$ -bounded lattice agreement. To do so, we first, we need some terminology. We say that a shared register $r$ contains a process $p$ , written $p\in r$ , when the seen component of $A[r]$ contains $p$ . Similarly, $r$ contains a set of processes $Q$ , written $Q\subseteq r$ , when $q\in r$ for every $q\in Q$ . We say that a process $p$ appears in the shared array when there is a register $r$ such that $p\in r$ ; we say that a set of processes $Q$ appears in the shared array when, for every $q\in Q$ , there is a register $r$ such that $q\in r$ . We say that a process obtains a snapshot of the shared array when it reaches line 20 with its local snapshot variable set to true.

Lemma 13.

If a process $p$ obtains a snapshot, then, at some time between the time $p$ starts its preceding double collect and the time at which $p$ finishes it, the shared array has the same contents as $p$ ’s local collect array when it obtains the snapshot.

Proof.

Since no array value is written more than once, two identical collects guarantee that no write happened in between. $\hfill\blacktriangleleft$

Lemma 14.

Consider a process $p$ that terminates and outputs a set of identifiers $O_{p}$ of cardinality at most $k$ (i.e. $p$ outputs at line 23). There is a time $t$ before $p$ outputs such that, from $t$ onwards, either there is a shared register $r$ such that $O_{p}\subseteq r$ or at least $k+1$ processes appear in the shared array.

Proof.

By Lemma 13, there is a time $t$ before $p$ outputs such that, at time $t$ , all registers contain exactly $O_{p}$ . Now consider the state predicate $\mathcal{P}$ asserting that, for each shared register $r$ such that $O_{p}\not\subseteq r$ , we can associate a unique process $p_{r}$ such that $p_{r}\in r$ and $p_{r}$ wrote (anywhere) after time $t$ . Note that is suffices to that $\mathcal{P}$ holds at all times after $t$ , which we now do using strong induction.

First, note that the property holds at time $t$ since every register contains exactly $O_{p}$ . Next, suppose that the property holds from time $t$ to time $t^{\prime}\geq t$ and that a process $q$ takes a step at time $t^{\prime}$ . We now show by case analysis that $\mathcal{P}$ holds again after $q$ ’s step.

1.

If $q$ writes a superset of $O_{p}$ , then $\mathcal{P}$ still holds with the same mapping as before the step.
2.
Suppose that $q$ writes a set $Q$ such that $O_{p}\not\subseteq Q$ .
1. (a)
  Suppose that, before $q$ ’s step, $q=p_{r}$ for some $r$ .
  1. i.
    
    If $q$ writes to $r$ , then $\mathcal{P}$ still holds, with the same mapping as before the step, since processes always write at least their own identifier.
  2. ii.
    
    Suppose that $q$ writes to $r^{\prime}\neq r$ . By the induction hypothesis, this is at least the second write of $q$ after $t$ , and thus $q$ obtains a snapshot $S$ between $t$ and $t^{\prime}$ , which, by Lemma 13, is equal to the contents of memory at some time between $t$ and $t^{\prime}$ . Hence, by the induction hypothesis, either (a) $q$ sees $O_{p}$ in its snapshot $S$ or (b) $q$ sees at least $k+1$ (the number of registers) processes in its snapshot $S$ who all wrote between $t$ and $t^{\prime}$ . Since $q$ writes $Q$ where $O_{p}\not\subseteq Q$ , case (a) is not possible and thus $q$ sees at least $k+1$ processes who all wrote after $t$ . Hence, $Q$ contains at least $k+1$ processes who all wrote after $t$ . Since there are $k+1$ registers, among the $k+1$ processes above there exists a process $q^{\prime}$ such that, for every $r^{\prime\prime}\neq r^{\prime}$ , $p_{r^{\prime\prime}}\neq q^{\prime}$ . Letting $p_{r^{\prime}}=q^{\prime}$ and keeping the mapping otherwise unchanged, we establish that $\mathcal{P}$ holds again.
2. (b)
  
  Suppose that, for every register $r$ such that $O_{p}\not\subseteq r$ , $q\neq p_{r}$ , and that $q$ writes to a register $r^{\prime}$ . Then we can simply update the mapping with $p_{r^{\prime}}=q$ , and $\mathcal{P}$ holds again.
3.

If $q$ reads, then $\mathcal{P}$ is trivially preserved.

$\hfill\blacktriangleleft$

Lemma 15.

The algorithm satisfies the containment property.

Proof.

We must show that if a process $p$ outputs a set $O_{p}$ and a process $q$ outputs a set $O_{q}$ , and both $O_{p}$ and $O_{q}$ are of cardinality at most $k$ , then $O_{p}$ and $O_{q}$ are related by containment (that is, either $O_{p}\subseteq O_{q}$ or $O_{q}\subseteq O_{p}$ ). This is immediate from Lemma 14 and the fact that each process that returns a set of cardinality at most $k$ returns values appearing in an atomic snapshot of the shared array. $\hfill\blacktriangleleft$

[bib.bib1] [1] Yehuda Afek, Hagit Attiya, Danny Dolev, Eli Gafni, Michael Merritt, and Nir Shavit. Atomic snapshots of shared memory. Journal of the ACM, 40(4):873–890, September 1993. doi:10.1145/153724.153741.

[bib.bib2] [2] Vitaly Aksenov, Nikita Koval, Petr Kuznetsov, and Anton Paramonov. Memory Bounds for Concurrent Bounded Queues. In Proceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming, PPoPP ’24, pages 188–199, New York, NY, USA, February 2024. Association for Computing Machinery. doi:10.1145/3627535.3638497.

[bib.bib3] [3] Michael Anoprenko, Petr Kuznetsov, and Vitaly Aksenov. Brief Announcement: Optimal Construction of Unique Identifiers from Bounded Registers. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC ’25, pages 62–65, New York, NY, USA, June 2025. Association for Computing Machinery. doi:10.1145/3732772.3733539.

[bib.bib4] [4] James Aspnes and Faith Ellen. Tight Bounds for Adopt-Commit Objects. Theory of Computing Systems, 55(3):451–474, October 2014. doi:10.1007/s00224-013-9448-1.

[bib.bib5] [5] Hagit Attiya, Maurice Herlihy, and Ophir Rachman. Atomic snapshots using lattice agreement. Distributed Computing, 8(3):121–132, March 1995. doi:10.1007/BF02242714.

[bib.bib6] [6] Zohir Bouzid, Michel Raynal, and Pierre Sutra. Anonymous obstruction-free (n, k)-set agreement with $$n-k+1$$atomic read/write registers. Distributed Computing, 31(2):99–117, April 2018. doi:10.1007/s00446-017-0301-7.

[bib.bib7] [7] J. E. Burns and N. A. Lynch. Bounds on Shared Memory for Mutual Exclusion. Information and Computation, 107(2):171–184, December 1993. doi:10.1006/inco.1993.1065.

[bib.bib8] [8] Claire Capdevielle, Colette Johnen, Petr Kuznetsov, and Alessia Milani. On the Uncontended Complexity of Anonymous Consensus. In DROPS-IDN/v2/Document/10.4230/LIPIcs.OPODIS.2015.12. Schloss-Dagstuhl - Leibniz Zentrum für Informatik, 2016. doi:10.4230/LIPIcs.OPODIS.2015.12.

[bib.bib9] [9] Carole Delporte-Gallet, Hugues Fauconnier, Pierre Fraigniaud, Sergio Rajsbaum, and Corentin Travers. The Computational Power of Distributed Shared-Memory Models with Bounded-Size Registers. In Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing, PODC ’24, pages 310–320, New York, NY, USA, June 2024. Association for Computing Machinery. doi:10.1145/3662158.3662789.

[bib.bib10] [10] Carole Delporte-Gallet, Hugues Fauconnier, Eli Gafni, and Leslie Lamport. Adaptive register allocation with a linear number of registers. In International Symposium on Distributed Computing, pages 269–283. Springer, 2013. doi:10.1007/978-3-642-41527-2_19.

[bib.bib11] [11] Carole Delporte-Gallet, Hugues Fauconnier, Eli Gafni, and Sergio Rajsbaum. Black art: Obstruction-free k-set agreement with $|$ mwmr registers $|$ < $|$ proccesses $|$ . In Vincent Gramoli and Rachid Guerraoui, editors, Networked Systems - First International Conference, NETYS 2013, Marrakech, Morocco, May 2-4, 2013, Revised Selected Papers, volume 7853 of Lecture Notes in Computer Science, pages 28–41, Berlin, Heidelberg, 2013. Springer. doi:10.1007/978-3-642-40148-0_3.

[bib.bib12] [12] Carole Delporte-Gallet, Hugues Fauconnier, Eli Gafni, and Sergio Rajsbaum. Linear Space Bootstrap Communication Schemes. In Davide Frey, Michel Raynal, Saswati Sarkar, Rudrapatna K. Shyamasundar, and Prasun Sinha, editors, Distributed Computing and Networking, pages 363–377, Berlin, Heidelberg, 2013. Springer. doi:10.1007/978-3-642-35668-1_25.

[bib.bib13] [13] Faith Ellen, Panagiota Fatourou, and Eric Ruppert. The space complexity of unbounded timestamps. Distributed Computing, 21(2):103–115, July 2008. doi:10.1007/s00446-008-0060-6.

[bib.bib14] [14] Faith Ellen, Rati Gelashvili, Nir Shavit, and Leqi Zhu. A complexity-based classification for multiprocessor synchronization. Distributed Computing, 33(2):125–144, April 2020. doi:10.1007/s00446-019-00361-3.

[bib.bib15] [15] Faith Ellen, Rati Gelashvili, Philipp Woelfel, and Leqi Zhu. Space Lower Bounds for the Signal Detection Problem. In Rolf Niedermeier and Christophe Paul, editors, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), volume 126 of Leibniz International Proceedings in Informatics (LIPIcs), pages 26:1–26:13, Dagstuhl, Germany, 2019. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.STACS.2019.26.

[bib.bib16] [16] Faith Ellen, Rati Gelashvili, and Leqi Zhu. Revisionist Simulations: A New Approach to Proving Space Lower Bounds. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC ’18, pages 61–70, New York, NY, USA, July 2018. Association for Computing Machinery. doi:10.1145/3212734.3212749.

[bib.bib17] [17] Panagiota Fatourou, Faith Fich, and Eric Ruppert. Space-optimal multi-writer snapshot objects are slow. In Proceedings of the Twenty-First Annual Symposium on Principles of Distributed Computing, PODC ’02, pages 13–20, New York, NY, USA, July 2002. Association for Computing Machinery. doi:10.1145/571825.571828.

[bib.bib18] [18] Faith Fich, Maurice Herlihy, and Nir Shavit. On the space complexity of randomized synchronization. J. ACM, 45(5):843–862, September 1998. doi:10.1145/290179.290183.

[bib.bib19] [19] Eli Gafni, Giuliano Losa, Michel Raynal, and Gadi Taubenfeld. Brief Announcement: Stranger-Free Tasks. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC ’25, pages 203–206, New York, NY, USA, June 2025. Association for Computing Machinery. doi:10.1145/3732772.3733545.

[bib.bib20] [20] Rati Gelashvili. On the optimal space complexity of consensus for anonymous processes. Distributed Computing, 31(4):317–326, August 2018. doi:10.1007/s00446-018-0331-9.

[bib.bib21] [21] Rachid Guerraoui and Eric Ruppert. What Can Be Implemented Anonymously? Technical report, EPFL, 2004. URL: https://infoscience.epfl.ch/handle/20.500.14299/214730.

[bib.bib22] [22] Maryam Helmi, Lisa Higham, Eduardo Pacheco, and Philipp Woelfel. The Space Complexity of Long-Lived and One-Shot Timestamp Implementations. J. ACM, 61(1):7:1–7:25, January 2014. doi:10.1145/2559904.

[bib.bib23] [23] Maurice Herlihy. Wait-free Synchronization. ACM Transactions on Programming Languages and Systems, 13(1):124–149, January 1991. doi:10.1145/114005.102808.

[bib.bib24] [24] Prasad Jayanti, King Tan, and Sam Toueg. Time and Space Lower Bounds for Nonblocking Implementations. SIAM Journal on Computing, 30(2):438–456, January 2000. doi:10.1137/S0097539797317299.

[bib.bib25] [25] Leslie Lamport. A fast mutual exclusion algorithm. ACM Trans. Comput. Syst., 5(1):1–11, January 1987. doi:10.1145/7351.7352.

[bib.bib26] [26] Giuliano Losa and Eli Gafni. Brief Announcement: Understanding Read-Write Wait-Free Coverings in the Fully-Anonymous Shared-Memory Model. In Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing, PODC ’24, pages 465–468, New York, NY, USA, June 2024. Association for Computing Machinery. doi:10.1145/3662158.3662786.

[bib.bib27] [27] Victor Luchangco, Mark Moir, and Nir Shavit. On the Uncontended Complexity of Consensus. In Faith Ellen Fich, editor, Distributed Computing, pages 45–59, Berlin, Heidelberg, 2003. Springer. doi:10.1007/978-3-540-39989-6_4.

[bib.bib28] [28] Maged M. Michael and Michael L. Scott. Simple, fast, and practical non-blocking and blocking concurrent queue algorithms. In Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing - PODC ’96, pages 267–275, Philadelphia, Pennsylvania, United States, 1996. ACM Press. doi:10.1145/248052.248106.

[bib.bib29] [29] Mark Moir and James H. Anderson. Wait-free algorithms for fast, long-lived renaming. Science of Computer Programming, 25(1):1–39, October 1995. doi:10.1016/0167-6423(95)00009-H.

[bib.bib30] [30] Sean Ovens. The Space Complexity of Scannable Binary Objects. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, PODC’21, pages 509–519, New York, NY, USA, July 2021. Association for Computing Machinery. doi:10.1145/3465084.3467916.

[bib.bib31] [31] Sean Ovens. The Space Complexity of Scannable Objects with Bounded Components. In Christian Scheideler, editor, 36th International Symposium on Distributed Computing (DISC 2022), volume 246 of Leibniz International Proceedings in Informatics (LIPIcs), pages 30:1–30:18, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.DISC.2022.30.

[bib.bib32] [32] Sean Ovens. Brief Announcement: The Space Complexity of Set Agreement Using Swap. In Rotem Oshman, editor, 37th International Symposium on Distributed Computing (DISC 2023), volume 281 of Leibniz International Proceedings in Informatics (LIPIcs), pages 46:1–46:6, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.DISC.2023.46.

[bib.bib33] [33] Sean Ovens. The Space Complexity of Consensus from Swap. J. ACM, 71(1):1:1–1:26, February 2024. doi:10.1145/3631390.

[bib.bib34] [34] Michel Raynal. About Informatics, Distributed Computing, and Our Job: A Personal View. In Sergio Rajsbaum, Alkida Balliu, Joshua J. Daymude, and Dennis Olivetti, editors, Structural Information and Communication Complexity, pages 33–45, Cham, 2023. Springer Nature Switzerland. doi:10.1007/978-3-031-32733-9_3.

[bib.bib35] [35] Michel Raynal and Gadi Taubenfeld. Mutual exclusion in fully anonymous shared memory systems. Information Processing Letters, 158:105938, June 2020. doi:10.1016/j.ipl.2020.105938.

[bib.bib36] [36] Michel Raynal and Gadi Taubenfeld. Fully Anonymous Consensus and Set Agreement Algorithms. In Chryssis Georgiou and Rupak Majumdar, editors, Networked Systems, Lecture Notes in Computer Science, pages 314–328, Cham, 2021. Springer International Publishing. doi:10.1007/978-3-030-67087-0_20.

[bib.bib37] [37] Gadi Taubenfeld. Coordination Without Prior Agreement. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC ’17, pages 325–334, New York, NY, USA, July 2017. Association for Computing Machinery. doi:10.1145/3087801.3087807.

[bib.bib38] [38] Gadi Taubenfeld. Set Agreement Power Is Not a Precise Characterization for Oblivious Deterministic Anonymous Objects. In Michele Flammini and Keren Censor-Hillel, editors, Structural Information and Communication Complexity, volume 11639, pages 293–308. Springer International Publishing, Cham, 2019. doi:10.1007/978-3-030-24922-9_20.

[bib.bib39] [39] Gadi Taubenfeld. Anonymous Shared Memory. Journal of the ACM, 69(4):24:1–24:30, August 2022. doi:10.1145/3529752.

[bib.bib40] [40] Gadi Taubenfeld. Memory-Anonymous Starvation-Free Mutual Exclusion: Possibility and Impossibility Results, September 2023. doi:10.48550/arXiv.2309.11337.

[bib.bib41] [41] Leqi Zhu. A tight space bound for consensus. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’16, pages 345–350, New York, NY, USA, June 2016. Association for Computing Machinery. doi:10.1145/2897518.2897565.

Solving Tasks with Fewer Registers Than Processes

Abstract

Keywords and phrases:

Copyright and License:

2012 ACM Subject Classification:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

2 Computation Model

3 For Every 𝒌>𝟏, There is a Task of Space Complexity 𝒌

Definition 1.

3.1 Lower Bound: 𝒌+𝟏 Registers Are Necessary

Theorem 2 (Space Complexity Lower Bound for k-Bounded Lattice Agreement).

3.2 Upper Bound: 𝒌+𝟏 Registers Are Sufficient

4 Space-Complexity Separates Anonymous From Non-Anonymous Memory

Definition 3.

4.1 Binary AC Has Space Complexity 3 if Registers Are Non-anonymous

Theorem 4.

Property 1.

Theorem 5 (Lower bound for solving adopt-commit using non-anonymous registers).

Proof.

▶ Claim 1.

Proof of Claim 1.

▶ Claim 2.

Proof of Claim 2.

▶ Claim 3.

Proof of Claim 3.

▶ Claim 4.

Proof of Claim 4.

4.2 Binary AC Has Space Complexity n if Registers Are Anonymous

Theorem 6.

Proof.

Property 2.

Theorem 7 (Lower bound for anonymous registers).

Proof.

5 A Task Achieving Minimal Space Complexity in All Models

Definition 8.

Theorem 9.

Proof.

6 A Space-Complexity Separation Among Sub-Cases of Adopt-Commit

Definition 10.

Theorem 11.

Proof.

Theorem 12.

Proof.

7 Related Work

Space complexity as number of registers.

Space complexity as number of objects.

Tasks solvable wait-free with fewer registers than processes.

Register allocation.

Anonymous memory.

Register size.

8 Future Work

References

Appendix A Proof of Safety of the Bounded Lattice-Agreement Algorithm

Lemma 13.

Proof.

Lemma 14.

Proof.

Lemma 15.

Proof.

3 For Every $k>1$ , There is a Task of Space Complexity $𝒌$

3.1 Lower Bound: $k+1$ Registers Are Necessary

3.2 Upper Bound: $k+1$ Registers Are Sufficient

$\blacktriangleright$ Claim 1.

$\blacktriangleright$ Claim 2.

$\blacktriangleright$ Claim 3.

$\blacktriangleright$ Claim 4.

4.2 Binary AC Has Space Complexity $n$ if Registers Are Anonymous