Upper and Lower Bounds on the Space Complexity of Multi-word Single-Writer Registers

Upper and Lower Bounds on the Space Complexity of Multi-word Single-Writer Registers Yuanhao Wei # University of British Columbia, Vancouver, Canada

Yousof Yavari # University of British Columbia, Vancouver, Canada

arXiv:2608.19167v1 [cs.DC] 19 Aug 2026

Abstract We prove matching upper and lower bounds on the space complexity of simulating a large shared register using smaller shared registers. We focus on the case where both the simulated and base registers are single-writer, which means they can be accessed concurrently by multiple readers but only by a single writer. To strengthen our lower bounds, we prove that they hold even when the base registers are atomic and the simulated register is regular. Furthermore, the lower bounds hold for obstruction-free implementations, which means they also hold for lock-free and wait-free implementations. If m is the number of values representable by the large register and b is the number of values representable by each base register, our first lower bound says that any obstruction-free implemen⌉ base registers. A reader is considered tation that has an invisible reader requires at least ⌈ m−1 b−1 invisible if it never writes to base registers. This lower bound is asymptotically tight for the invisible-reader case and represents an exponential improvement over the previous best known lower bound. For the general case, which allows any combination of visible and invisible readers, we prove m a ⌈min( m−1 , r + log )⌉ space lower bound, where r is the number of readers. b−1 log b To show that this lower bound is asymptotically tight, we develop a wait-free algorithm for simum lating a multi-word atomic register from atomic base registers using Θ(r + log ) space. Combining log b m m this algorithm with known invisible-reader constructions gives a Θ(min( b , r + log )) space upper log b m m bound. This improves upon the previously known space upper bound of Θ(min( b , r log )). log b 2012 ACM Subject Classification Theory of computation → Concurrent algorithms Keywords and phrases Shared memory, Concurrency, Non-blocking, Multi-word, Register, Space Funding This work was supported by the Natural Sciences and Engineering Research Council of Canada (NSERC) through a Discovery Grant and an Undergraduate Student Research Award (USRA). Acknowledgements We thank the anonymous reviewers of the paper for their helpful comments and suggestions. We also thank Faith Ellen, Tian Ze Chen and Alexander Spiegelman for the many helpful discussions.

1

Introduction

Shared registers are among the most fundamental abstractions in concurrent and distributed computing. A register supports two operations: a write, which stores a value, and a read, which retrieves one. Registers are classified by their consistency guarantees — safe, regular, and atomic — in increasing order of strength [7]. A safe register guarantees that a read not concurrent with any write returns the last written value, while concurrent reads may return any value in the register’s domain. A regular register additionally ensures that a concurrent read returns either the last written value or the value being written concurrently. An atomic register, the strongest of the three, additionally requires that operations appear to take effect instantaneously at some point during their execution, inducing a total order consistent with real time — a property also known as linearizability. In this paper, we focus our attention

2

Space Complexity of Multi-word Single-Writer Registers

Algorithm Peterson [9] Chaudhuri and Welch [4] Vidyasankar [10] Vidyasankar [11] + Chaudhuri and Welch [4] Chaudhuri, Kosa and Welch [3] Chaudhuri, Kosa and Welch [3] Chen and Wei [5] Chen and Wei [5] This paper

Simulated Base Readers Register Register Invisible atomic atomic no regular regular yes atomic atomic yes

Space

Read

Write

m ) Θ(r log log b Θ( m ) b m Θ( log ) b

m ) Θ( log log b m Θ( log ) log b m Θ( log ) b

m ) Θ(r log log b m Θ( log ) log b m Θ( log ) b

atomic

atomic

yes

) Θ( m b

m ) Θ( log log b

m ) Θ( log log b

atomic regular atomic atomic

atomic regular atomic atomic

yes yes yes no

Θ(m2 ) Θ(m2 ) 2 ) Θ( m b2 m Θ(r log ) log b

Θ(m2 ) Θ(m2 ) m ) Θ( log log b log m Θ( log b )

1 1

atomic

atomic

no

m ) Θ( log log b log m Θ( log b )

2

m m m Θ(r + log ) Θ( log ) Θ(r + log ) log b log b log2 b

Table 1 Wait-free m-valued SW register implementations from b-valued SW registers, where r is the number of readers.

on regular and atomic registers. In practice, the values a register must store can be larger than the base registers available in hardware. Implementing multi-word shared registers is challenging because data being accessed by slow readers can be overwritten by fast writers. To ensure the regular and atomic consistency guarantees, careful synchronization and additional base registers are required. This gives rise to a natural problem in the theory of shared memory algorithms: how many b-valued regular or atomic registers are needed to implement an m-valued register of the same type? Since Lamport’s foundational work [7], a rich line of research [9, 4, 10, 3, 5] has studied this question in the setting where the implemented and the base registers are single-writer (SW), meaning that each register can be accessed concurrently by multiple readers but only a single process can write to the register. This line of work has focused on developing wait-free implementations where each read and write is guaranteed to finish within a finite number of its own steps regardless of the schedule. The step and space complexity of these implementations are summarized in Table 1, where r represents the number of readers. Existing implementations of multi-word SW regular or atomic registers from base registers of the same type fall into two broad categories: ones where all readers are invisible (meaning they do not write to any base registers) and ones where all readers are visible. The invisiblereader implementations in Table 1 all use at least Ω( m b ) space, which is exponentially higher m than the trivial information-theoretic lower bound of Ω( log log b ). Researchers have improved the constant factors of this lower bound [4], but asymptotic improvements have only been shown for restricted classes of algorithms [2, 3]. A similar but smaller gap exists in the visible reader case. Since all readers write to a different SW base register, it is easy to show a space m lower bound of ⌈r + log log b ⌉ in this setting. However, the visible-reader implementations in m Table 1 all use at least Ω(r log log b ) space, and a natural question is whether this is inherently required. In this paper, we close both gaps by exponentially strengthening the lower bound in the invisible reader setting and improving the upper bound in the visible reader setting. Specifically, we prove that any algorithm with at least one invisible reader requires at least ⌈ m−1 b−1 ⌉ base registers. This lower bound holds even when implementing a regular register from atomic base registers, so it also holds in the regular-from-regular and atomic-fromatomic cases. Our lower bound is proven for the weaker obstruction-free progress property, which means it also holds for lock-free and wait-free implementations. This lower bound is asymptotically tight because there exist wait-free regular-from-regular [4] and atomic-from-

Y. Wei and Y. Yavari

3

atomic [11] implementations that use Θ( m b ) space. In the setting with visible readers, we m develop a wait-free algorithm for the atomic-from-atomic case that uses only Θ(r + log log b ) m log m base registers. Chen and Wei’s visible-reader algorithm uses Θ(r log log b ) space and Θ( log b ) 2

m log m steps per read and write [5], whereas our algorithm uses Θ(r + log log b ) space, Θ( log2 b ) read m log m steps, and Θ(r + log log b ) write steps. Whether the optimal Θ(r + log b ) space bound can be m achieved together with Θ( log log b ) read and write step complexity remains open. Putting together the case with at least one invisible reader and the case in which every log m reader is visible, we show a lower bound of ⌈min( m−1 b−1 , r + log b )⌉ and a matching upper log m bound of Θ(min( m b , r + log b )) on the space complexity of implementing multi-word SW registers. The lower bound holds in the weaker regular-from-atomic setting and it holds for all obstruction-free implementations. The upper bound is wait-free and holds in the atomic-fromatomic setting. It can be derived by combining our algorithm with Vidyasankar’s [11] plus Chaudhuri and Welch’s [4] algorithm from Table 1, and using whichever requires less space. The invisible-reader construction uses Θ( m b ) space, whereas our visible-reader construction m uses Θ(r + log ) space. Therefore, the former gives the smaller asymptotic space bound log b log m when m b is smaller, and the latter does so when r + log b is smaller. Outline. The remainder of the paper is organized as follows. Related work is described in Section 2. The model of computation and important terminology are defined in Section 3. Our lower bound is proven in Section 4 and the algorithm for our upper bound is described in Section 5. Finally, we conclude in Section 6.

2

Related Work

Table 1 summarizes the step and space complexity of known implementations of an m-valued SW register from b-valued base registers of the same type; all of them are wait-free. We organize prior work into the space upper bounds these implementations achieve and the lower bounds known for the problem, relating each to our results. Prior upper bounds. In the invisible-reader setting, Chaudhuri and Welch [4] build a tree over the represented values to implement a multi-word regular register from regular base registers. Their construction was first given for b = 2, and Chen and Wei [5] later generalized it to arbitrary b ≥ 2. When m is a power of b, it uses m−1 b−1 base registers, matching our lower bound exactly. For the atomic case, Vidyasankar [11] implements an m-valued atomic register from two m-valued regular registers and one binary atomic register; instantiating the two regular registers with the algorithm of Chaudhuri and Welch [4] yields an m-valued atomic register from b-valued atomic registers using 2 m−1 b−1 + 1 space when m is a power of b, which matches our lower bound asymptotically. In the visible-reader setting, the best previously m known space bound is Θ(r log log b ), achieved by Peterson [9] and by Chen and Wei [5]; our m visible-reader algorithm improves this to Θ(r + log log b ). Prior lower bounds. The only previously known lower bound that applies to all m implementations is the trivial Ω( log log b ) bound, refined by Chaudhuri and Welch [4] to ⌈max(log m + 1, (2 log m) − (log log m) − 2)⌉ for regular registers built from binary regular registers. This is exponentially smaller than the Ω( m b ) space used by every known invisiblereader implementation, and closing this gap is the main contribution of our lower bound. Stronger bounds were known only for restricted classes of algorithms. In the case of algorithms in which each simulated write performs only a single base-register write, Chaudhuri, Kosa and Welch [3] prove two space lower bounds. The first is a 2m − 1 − ⌊log m⌋ lower bound for one-write implementations satisfying the symmetric property, meaning that whenever a write

4

Space Complexity of Multi-word Single-Writer Registers

changing the logical value from v to w modifies a base register x, if the subsequent write changes the value back from w to v, then the write restores x to its original contents. For a more restricted class of one-write implementations satisfying the toggle property where, for each unordered pair of logical values, there is a unique register that is changed when switching between the two logical values, they show that Ω(m2 ) space is needed, establishing that their one-write algorithm is space-optimal for this class. Berger, Keidar and Spiegelman [2] consider implementations in which each simulated read must observe at least τ ≥ 2 values written by the same simulated write before it may return. They prove that any wait-free regular-from-atomic implementation in this class requires at least τ m space with an invisible reader and τ + (τ − 1) min(m − 1, r) space in general. Their bound helps explain the space usage of the visible-reader implementations of Peterson [9] and Chen and Wei [5], for which m τ = log log b . However, every invisible-reader implementation in Table 1 has τ ≤ 1, so this bound does not apply to any of them; in contrast, our ⌈ m−1 b−1 ⌉ bound holds for all invisible-reader implementations. Other models. Some papers [8] assume stronger atomic primitives such as swap, fetchand-add, and compare-and-swap; we focus on implementations that use only read/write base registers.

3

Model

We will work in the standard asynchronous shared memory model [1] with r readers and one writer, which communicate through shared base registers. Unless otherwise stated, all base registers are atomic. Processes may fail by crashing, and each process invokes at most one operation at a time. An execution is an alternating sequence of configurations and steps C0 , e1 , C1 , e2 , C2 , . . . , beginning with an initial configuration C0 . Each step ei is a read or write of a single base register performed by one process, and the configuration Ci records the state of every base register together with the local state of every process after ei is applied to Ci−1 . Given two configurations C and C ′ of the same execution with C no later than C ′ , the interval from C to C ′ consists of all configurations and steps from C through C ′ , inclusive. An operation is complete if it has returned a response, and pending otherwise. The execution interval of a complete operation is the set of all configurations and steps from its first step to the configuration immediately after its last step; for a pending operation, the execution interval consists of all configurations and steps from its first step onward. Two operations are concurrent if their execution intervals intersect. A register is atomic if its operations are linearizable [6]: for every execution, each completed operation can be assigned a linearization point — a configuration within its execution interval — so that all operations behave as if they occurred sequentially in the order of their linearization points. When we say that an operation is linearized at a step, we mean that its linearization point is the configuration immediately after that step. A register is regular if every read returns either the initial value if no write completed before the read’s first step, the value written by the last write that completed before the read’s first step, or the value written by some write concurrent with the read. Every atomic register is also regular. An implementation is obstruction-free if, from any reachable configuration, an operation that runs in isolation — with all other processes suspended — terminates in a finite number of steps. It is lock-free if, in every infinite execution, infinitely many operations complete, and wait-free if every operation completes in a finite number of its own steps, regardless of

Y. Wei and Y. Yavari

the steps taken by other processes. Every wait-free implementation is lock-free, and every lock-free implementation is obstruction-free. The step complexity of an operation is the maximum number of base-register accesses it performs, over all executions. The space complexity of an implementation is the number of base registers it uses.

4

Space Lower Bound

This section proves new lower bounds on the number of atomic base registers needed to implement a multi-word regular register. Throughout, we abbreviate “obstruction-free implementation of a regular SW register from atomic SW base registers” to simply implementation. The first bound, Theorem 4, applies whenever at least one reader is invisible, including implementations that also contain visible readers. The second, Theorem 5, extends it to all implementations by combining this case with the case in which every reader is visible. We begin by introducing the notions used in the proofs. Throughout this section, let m be the number of values of the simulated register and let N be the number of base registers of the implementation under consideration. Let bi be the number of values that the ith base P register can represent. The total fanout of the implementation, denoted S, is the sum i bi of these quantities. When every base register is b-valued we have S = N b, but it is convenient in the proof to allow base registers of different sizes. The intuition behind the term total fanout comes from viewing the invisible reader’s algorithm as a decision tree. The internal nodes of the decision tree are labeled by base registers and the same base register can appear multiple times in the decision tree. The leaves are labeled by return values. When a reader reads the i-th base register, the algorithm can branch in bi different directions based on the value read; thus, bi represents the branching factor, or fanout of that register.

4.1

Proof Overview

The key step is Lemma 2, which transforms an m-valued implementation with total fanout S and an invisible reader into an (m − 1)-valued implementation with total fanout S − 1. We later apply this lemma inductively to argue that S must be large whenever m is large. To prove Lemma 2, we fix one invisible reader and represent its algorithm as a decision tree. We select a minimum-depth leaf ℓ returning a value v. Let p be its parent, let t be the base register read at p, and let x be the value labeling the edge from p to ℓ. If returning v is legal whenever the reader is poised at p, we simplify the algorithm by replacing the subtree rooted at p by a leaf returning v. Repeating this simplification eventually yields an execution in which a pending read R is poised at p, but returning v would violate regularity. From this execution, we complete every other pending operation while leaving R paused, resulting in a configuration C. Since v is not a legal response for R at this point due to regular-register semantics, no write of v is pending or concurrent with R. Since no new operations are invoked, no write of v occurs while the other pending operations are completed, and t cannot take the value x during this interval; otherwise, resuming R immediately after t takes on the value x would make it return the illegal value v. We then run R to completion to obtain a configuration with no pending operations. Because the reader is invisible, this configuration has the same shared memory and the same local states for every other process as the preceding configuration in which R was still poised at p. We use this resulting configuration, in which all pending operations including R have completed, as the initial configuration of an implementation whose simulated domain excludes

5

6

Space Complexity of Multi-word Single-Writer Registers

v. If t could ever contain x in an execution of this (m − 1)-valued register implementation, we could remove the invisible reader’s steps, replay the remaining execution from the preceding configuration C in which all other pending operations have completed and R is still poised at p, and then resume R. It would read x and return v, contradicting regularity. Thus x is never stored in t in the (m − 1)-valued implementation and can be removed from t’s domain, decreasing total fanout by one. Thus, we obtain an (m − 1)-valued implementation with N base registers, total fanout S − 1, and an invisible reader, as claimed. Lemma 3 applies this reduction inductively to show that S − N + 1 ≥ m. The invisible-reader bound, Theorem 4, proves that when all base registers are b-valued, S = N b yields N ≥ ⌈ m−1 b−1 ⌉. If every reader m is visible, the readers require r distinct base registers and the writer requires at least ⌈ log log b ⌉ additional registers. The general lower bound, Theorem 5, follows by combining Theorem 4 with the lower bound for implementations in which every reader is visible.

4.2

Lower Bound Proof

Before diving into the main technical lemma, we define a useful predicate. ▶ Definition 1. The predicate E(m, N, S) holds if there exists an obstruction-free implementation of an m-valued regular SW register using N atomic SW base registers with total fanout S in which at least one reader is invisible. ▶ Lemma 2. For m ≥ 2, E(m, N, S) implies E(m − 1, N, S − 1). Proof. Without loss of generality, we represent the algorithm of an invisible reader as a set of decision trees, one for each possible local state at the start of a read operation, since the reader may retain local state between operations. Each internal node represents the reader’s complete local state immediately before its next base-register read and is labeled by that base register. Each such node has bi outgoing edges, where i is the index of the base register labeling the node, and each outgoing edge is labeled by a value that can be read from the base register. The invisible reader chooses a decision tree based on its local state and starts at the root of that decision tree. It then repeatedly performs the following steps until it reaches a leaf: read the register labeling the current node and follow the edge corresponding to the value that was read. After following an edge from node n1 to node n2 , we say that the reader has reached node n2 . Each leaf is labeled by a value from the simulated register and by the complete local state of the reader after returning that value. Once the invisible reader reaches a leaf, it returns the value labeling that leaf and enters the corresponding local state. We say that an invisible reader is poised at a node in its decision tree if it has reached that node but has not yet performed the corresponding read. For a pending read R after an execution E, we say that R can return a value v immediately after E if returning v at that point would satisfy regular-register semantics; that is, v is the initial value if no write completed before R began, the value of the last write that completed before R began, or the value of a write concurrent with R. We say that a process runs solo during an interval of an execution if no other processes take any steps in that interval. Suppose E(m, N, S) holds, witnessed by an implementation Am satisfying Definition 1. Let IV be one of the invisible readers in Am . Fix the initial configuration of Am , let s be the local state of IV in that configuration, and consider the decision tree D for a read invoked by IV from local state s. To simplify Am , we begin by changing the post-return local state of every leaf in D to s and we call the resulting implementation A′m . This change forces IV to use D for every read operation.

Y. Wei and Y. Yavari

We first show that A′m still implements a regular register. Suppose otherwise, and let E be an execution prefix of A′m ending when a read R returns a value that violates regular-register semantics. If R is performed by IV , let E ′ be obtained from E by removing all earlier completed reads by IV , but retaining R. Since every read by IV in A′m leaves it in state s, the read R begins in state s. After removing the earlier reads, IV also begins R in state s in Am and therefore follows the same decision tree D. If R is performed by another reader, let E ′ be obtained from E by removing all steps by IV . In either case, since IV is invisible, the removed steps do not change shared memory or the local states of any other process. Therefore, there is a corresponding execution prefix of Am in which the same base-register steps occur as in E ′ , and R reads the same base-register values and returns the same value. The writer steps and their order relative to R are unchanged. Therefore, the initial value if no write completed before R began, or otherwise the value of the last such write, and the values written by all writes concurrent with R are unchanged. Thus, R violates regular-register semantics in Am , contradicting the correctness of Am . Therefore, A′m implements a regular register. We next show that A′m is also obstruction-free. Consider any configuration C reachable in A′m , and fix an execution of A′m ending in C. If IV has a pending read, remove from this execution all of its earlier completed reads while retaining the pending read. Otherwise, remove all of its completed reads. Since every completed read by IV in A′m leaves it in state s and IV is invisible, the resulting sequence is an execution of Am . If IV has a pending read, that read began in state s, and the two implementations behave identically until the read returns. Thus, the resulting sequence reaches the same complete configuration C in Am . Therefore, any operation running solo from C takes the same steps until it completes as it would in Am , and hence terminates after finitely many steps. For the remainder of the proof, we write Am for A′m . Consider a leaf ℓ of minimum depth in the decision tree D and let v be its value. The decision tree is fixed by IV ’s algorithm and the chosen starting local state s: the actions of other processes do not change the tree, but may change the base-register values observed by IV and therefore the path it follows. Although the tree may have infinite depth and may contain infinite-length paths, it has at least one leaf at finite depth: let IV invoke the read from the initial configuration, suspend all other processes, and let IV run alone. The values returned by its base-register reads determine one path through the tree. By obstruction-freedom, this solo read terminates after finitely many of its own steps, so this path reaches a leaf at finite depth. Thus, at least one leaf has finite depth, and consequently the minimum leaf depth is finite. Moreover, ℓ is not the root: starting from the initial configuration, consider two executions in which IV takes no steps: in one, the writer runs solo and completes a write of some value a, and in the other, the writer runs solo and completes a write of a different value b. In both executions, IV subsequently invokes a read from the same local state s. If the root were a leaf, the read would return the same value in both executions, contradicting regular-register semantics in at least one of them. Let p be the parent of ℓ. If IV can return v immediately after every execution in which it is poised at p, replace the subtree rooted at p with a leaf labeled by v and the post-return local state s. This preserves correctness because every newly introduced return of v is permitted by regular-register semantics, IV does not modify shared memory, and its post-return local state is the initial local state of IV. It preserves obstruction-freedom because it only shortens reads. The minimum leaf depth decreases by one. Repeating this process must terminate because the minimum leaf depth is a nonnegative integer, and it cannot decrease to zero by the preceding argument. Continue to denote the resulting implementation by Am . We therefore

7

8

Space Complexity of Multi-word Single-Writer Registers

obtain a leaf ℓ with value v, its parent p, and an execution E0 ending in a configuration C0 after which a pending read R by IV is poised at p and cannot return v immediately without violating regular-register semantics. Since R cannot return v immediately after E0 , if no write completed before R began, then the initial value is not v; otherwise, the last write that completed before R began did not write v. Moreover, no write of v is concurrent with R in E0 . In particular, there is no pending write of v at C0 . Extend E0 , without invoking any new operations, by running each process with a pending operation, except for the pending read R, solo until its operation completes, which it does after a finite number of steps by obstruction-freedom. Let E1 denote the resulting execution and let C1 denote its final configuration. No write of v occurs between C0 and C1 , so R still cannot return v at C1 . Let x be the value labeling the edge from p to ℓ, and let t be the register labeling p. We next show that t does not store x at C0 or in any configuration between C0 and C1 . Suppose otherwise. At the first such configuration, we could resume R; it would read x from t, reach ℓ, and return v. Since no write of v occurred, this would violate regular-register semantics. In particular, t ̸= x at C1 . Extend E1 by running R solo until it completes, which it does after a finite number of steps by obstruction-freedom. Let E2 denote the resulting execution and let C2 denote its final configuration. Because IV is invisible, C1 and C2 contain the same values in every base register and the same local states for every process other than IV . In particular, t = ̸ x at C2 . Every process has no pending operation at C2 . Let w0 be the value of the last write that completed before C2 , or the original initial value if no write has completed. We have w0 ̸= v, since if no write completed before R began, then the initial value was not v; otherwise, the last write preceding R did not write v. Moreover, no write of v was concurrent with R or occurred while constructing C2 . We define an implementation Am−1 of an (m − 1)-valued regular register by (1) using the same set of base registers as Am , (2) using C2 as the initial configuration and w0 as the initial simulated value, (3) using the same reader algorithms as in Am , and (4) using the same writer algorithm as Am for all values w ̸= v. This is a correct implementation of a regular (m − 1)-valued register because any execution of Am−1 can be concatenated after E2 to obtain an execution of Am . Since every process has no pending operation at C2 and its last completed write has value w0 , an incorrect execution of Am−1 would therefore give an incorrect execution of Am . Obstruction-freedom is also inherited because every configuration reachable in Am−1 is reachable in Am , and the processes use the same algorithms. We argue that t never stores value x in any configuration of any execution of Am−1 . Suppose for contradiction that some execution E3 of Am−1 ends in a configuration C3 in which t stores x. Remove from E3 all steps taken by IV , resulting in an execution E4 . Since IV is invisible, removing its steps does not change the shared-memory states observed by any other process. Furthermore, C1 and C2 have identical shared memory and identical local states for every process other than IV . Therefore, the same sequence of steps in E4 is executable from C1 and reaches the same shared-memory configuration; in particular, it reaches a configuration in which t stores x. Concatenating E1 with the same sequence of steps as in E4 produces an execution E5 of Am in which the original read R remains poised at p. If we extend E5 by resuming R, it reads x from t, reaches ℓ, and returns v. If no write completed before R began, then the initial value is not v; otherwise, the last write that completed before R began did not write v. Moreover, every write concurrent with R writes a value different from v: this was true at C0 , no write of v occurred while constructing C1 , and Am−1 does not permit writes of v.

Y. Wei and Y. Yavari

Thus, R returning v contradicts the correctness of Am . Therefore, t never stores x in any reachable configuration of Am−1 . Since t does not initially store x and never stores x in any reachable execution, we can remove x from the set of values representable by t without changing any reachable execution. This reduces the total fanout by exactly one while preserving correctness and obstruction-freedom. Since Am−1 has at least one invisible reader, inherited from Am , it follows that E(m − 1, N, S − 1) holds. ◀ The next lemma applies Lemma 2 inductively to show that S must be large when m is. For intuition, a finite rooted tree with q internal nodes whose branching factors sum to T has T − q + 1 leaves. ▶ Lemma 3. E(m, N, S) implies S − N + 1 ≥ m. Proof. We proceed by induction on m. For the base case where m = 1, every base register has fanout at least one, so S ≥ N and hence S − N + 1 ≥ 1 = m. For the inductive step, assume the lemma holds for some m = k, where k ≥ 1. By Lemma 2, E(k + 1, N, S) implies E(k, N, S − 1) since k + 1 ≥ 2. By the inductive hypothesis E(k, N, S − 1) implies (S − 1) − N + 1 ≥ k. Adding one to both sides gives S − N + 1 ≥ k + 1, as required. ◀ ▶ Theorem 4. Any obstruction-free implementation of an m-valued regular SW register from b-valued atomic base registers in which some reader is invisible uses at least ⌈ m−1 b−1 ⌉ base registers. Proof. Any such implementation using N base registers witnesses E(m, N, N b). By Lemma 3, m−1 N b − N ≥ m − 1, that is, N ≥ m−1 ◀ b−1 . Since N is an integer, N ≥ ⌈ b−1 ⌉. ▶ Theorem 5. Any obstruction-free implementation of an m-valued regular SW register from log m b-valued atomic base registers uses at least ⌈min( m−1 b−1 , r + log b )⌉ base registers, where r is the number of readers. Proof. Let A be any obstruction-free implementation of an m-valued regular SW register from b-valued atomic base registers. If A has an invisible reader, then by Theorem 4 it uses at least ⌈ m−1 b−1 ⌉ base registers. Otherwise every reader is visible, and since base registers are single-writer, each reader writes to a different base register, accounting for r of them; the m writer needs a further ⌈ log log b ⌉ base registers to represent the m possible values, for a total m space usage of at least ⌈r + log log b ⌉. Putting these two cases together yields the desired lower bound. ◀

5

Space Upper Bound

In Section 4, we proved that every obstruction-free implementationlof an m-valued regular m log m SW register from b-valued atomic base registers requires at least min m−1 , r + b−1 log b base registers. We now show that this bound is asymptotically tight, even for the stronger goal of implementing an atomic register with a wait-free algorithm. The first term of the minimum is already matched by known invisible-reader constructions: instantiating Vidyasankar’s regular-to-atomic transformation [11] with the tree-based regular register of Chaudhuri and Welch [4] yields a wait-free atomic-from-atomic implementation using Θ( m b ) base registers. This section supplies an upper bound matching the second term. We give a

9

10

Space Complexity of Multi-word Single-Writer Registers

wait-free implementation of an m-valued  atomic SW register from b-valued atomic SW base m registers in Figure 1 that uses only Θ r + log base registers. Running whichever of the log b two implementations is cheaper  for the given  parameters then matches the lower bound with log m a space complexity of Θ min m , r + , improving on the previous best space bound of b log b    log m Θ min m , obtained by combining the invisible-reader construction above with the b , r log b visible-reader algorithms of Peterson and Chen and Wei [9, 5]. The space savings come at a

m modest cost in step complexity: in our implementation each write completes in Θ r + log log b  2  m steps and each read in Θ log steps. log2 b At a high level, the algorithm combines the double buffering technique with helping: a reader first tries to scan the active global buffer directly, and if it fails this scan too many times, it returns the value that the writer delivered one piece at a time. Between every two failed scan attempts on the global buffer, the reader is guaranteed to receive a piece of a value that is safe to return from the writer. We first define notation and conventions for the implementation in Section 5.1 and then give a detailed description of the algorithm in Section 5.2. The remaining subsections prove that the algorithm is linearizable and wait-free with the desired bounds.

5.1

Definitions and Initialization

For the implementation in Figure 1, a register value consists of L pieces, where L =

l

log m log b

m

.

The global buffers G[0] and G[1] are arrays of L atomic registers. A scan of G[s] means reading from all L registers of G[s] in some fixed order. A write of G[s] means writing to all L registers of G[s] in some fixed order. The order of the pieces is irrelevant for the proof. A reader returning an L-piece sequence returns the value encoded by that sequence. The pointer register V ∈ {0, 1} identifies the active buffer. For each reader i, there are registers ReadReqi , ReadAcki , AttemptReqi , AttemptAcki , PieceAcki , PieceReadyi , and Mailboxi . The writer alone writes to ReadAcki , AttemptAcki , PieceReadyi , and Mailboxi . Reader i alone writes to ReadReqi , AttemptReqi , and PieceAcki . The writer also maintains local variables localVali and idxi . For a read request, localVali stores the fixed L-piece value being delivered to reader i, and idxi is the index of the next piece to send. We call this ordered delivery a stream. A value written to Mailboxi is a mailbox piece; the condition PieceReadyi ̸= PieceAcki is a mailbox signal indicating that an unacknowledged piece is ready, and such a signal is stale if it belongs to an earlier stream. The initial configuration satisfies ReadReqi = ReadAcki , AttemptReqi = AttemptAcki , PieceAcki = PieceReadyi , and idxi = L for every reader i, and both global buffers contain the initial value of the simulated register. The condition idxi = L ensures that the writer sends no mailbox piece to reader i before it has captured a value for some read request. For a multi-word write operation W , let c(W ) denote the configuration immediately after W ’s write to V . The write to V is called the commit step of W . After c(W ), the writer scans the readers once. For reader i, the part of this scan that inspects and updates the registers associated with i is called the service block of W for reader i. A Write operation does not return until after it has completed all of its service blocks. Since the writer process invokes at most one operation at a time, no later Write operation begins before the previous Write operation has completed all of its service blocks. During the service blocks of a write W , the current committed value is the value of W , since W has already executed its commit step and no later write has begun. When W acknowledges a new read request from reader i, it fixes this value for the read by storing it in localVali .

Y. Wei and Y. Yavari

11

Shared Variables: m L = ⌈ log ⌉: number of pieces per value log b G[0], G[1]: arrays of L registers V : 1-bit pointer register (active buffer pointer) For each reader i ∈ {1, . . . , r}: M ailboxi : 1 register (holds 1 piece of the value) ReadReqi , ReadAcki : 1-bit handshake for new read operation AttemptReqi , AttemptAcki : 1-bit handshake for interruption tripwire P ieceAcki , P ieceReadyi : 1-bit handshake for piece transfer Writer Local Variables: localV al[1 . . . r]: one L-piece value per reader idx[1 . . . r]: integer 0 . . . L (next piece to send) Initialization: V ← 0, and both G[0] and G[1] contain the initial value For each reader i: Set every handshake bit to 0, and idx[i] ← L 0: procedure Write(value) 1: s ← 1 − read(V ) 2: write(G[s], value) 3: write(V, s) 4: for k = 1 to r do 5: rReq ← read(ReadReqk ) 6: if rReq ̸= ReadAckk then 7: localV al[k] ← value 8: idx[k] ← 0 9: write(P ieceReadyk , read(P ieceAckk )) 10: write(ReadAckk , rReq)

▷ Inactive buffer ▷ Write data ▷ Commit active buffer ▷ Check all readers ▷ Check if a new read has started ▷ Fix this committed value for reader k ▷ Reset next-piece index ▷ Clear stale mailbox signal ▷ Acknowledge new read

11: 12: 13: 14:

if read(P ieceAckk ) = P ieceReadyk and idx[k] < L then write(M ailboxk , localV al[k][idx[k]]) write(P ieceReadyk , 1 − P ieceReadyk ) idx[k] ← idx[k] + 1

15: 16:

aReq ← read(AttemptReqk ) write(AttemptAckk , aReq)

0: procedure Readi 1: myReq ← 1 − read(ReadAcki ) 2: write(ReadReqi , myReq) 3: pieces ← [] 4: while length(pieces) < L do 5: aReq ← 1 − read(AttemptAcki ) 6: write(AttemptReqi , aReq) 7: s ← read(V ) 8: val ← read(G[s]) 9: if read(AttemptAcki ) ̸= aReq then 10: return val 11: 12: 13: 14: 15:

if read(ReadAcki ) = myReq then if read(P ieceReadyi ) ̸= P ieceAcki then pieces.append(read(M ailboxi )) write(P ieceAcki , read(P ieceReadyi )) return pieces

▷ Is reader ready? ▷ Send piece ▷ Signal piece ready

▷ Acknowledge tripwire

▷ Announce new read ▷ Empty local list ▷ Arm tripwire ▷ Active buffer ▷ Attempt global read ▷ Did writer interrupt? ▷ No, safe to return ▷ Wait for writer to sync ▷ Is piece ready? ▷ Grab piece ▷ Acknowledge piece ▷ All pieces received

Figure 1 Wait-Free atomic m-valued SW register from atomic b-valued SW registers.

12

Space Complexity of Multi-word Single-Writer Registers

5.2

Algorithm Overview

The algorithm combines two standard ideas: double buffering and per-reader assistance. Double buffering lets the writer prepare a new value without overwriting the current value. Per-reader assistance allows reads to eventually return a correct value after enough failed attempts at reading the active buffer. At any configuration, the active buffer is indicated by the bit V . To write a new value, the writer fills the inactive buffer completely and only then changes V to point to that buffer; the configuration immediately after this update to V is the linearization point of the write. This ensures that the active buffer G[V ] always contains the value of the most recently linearized write. After changing V , the writer executes one service block for each reader. These service blocks allow slow readers to make progress even if their direct buffer scans keep failing. For each reader i, the writer first checks whether reader i has announced a new read by comparing its request bit rReq := ReadReqi with ReadAcki . If they differ, the writer treats this as a new request: it fixes the current committed value as the value that will be streamed to reader i, stores that value locally as localVali , resets idxi to the first piece, and clears any stale mailbox signal by making PieceReadyi agree with PieceAcki . This clearing step ensures that the reader will not confuse a piece from an old mailbox stream with a piece from the new one. The writer then acknowledges the request by copying the request bit into ReadAcki . After handling the read request, the writer may send one mailbox piece: if PieceAcki =PieceReadyi , meaning there is no unacknowledged mailbox piece waiting for the reader, and there are still pieces left to send, the writer writes the next piece into Mailboxi , flips PieceReadyi to announce that a new piece is ready, and advances idxi . Finally, the writer triggers the reader’s tripwire by copying AttemptReqi into AttemptAcki . A read by reader i begins by creating a fresh read request. The reader reads its current acknowledgement bit ReadAcki , chooses the opposite bit as its new request bit myReq, writes myReq to ReadReqi , and starts with an empty list of mailbox pieces. The reader then first tries to read directly from the active global buffer. This is the optimistic, fast-path case. The difficulty is that a reader scans the buffer piece by piece, so the writer might switch buffers and later return to overwrite the same buffer while the reader is still scanning it. To detect this kind of interference, reader i uses a small tripwire formed by AttemptReqi and AttemptAcki . Before scanning, the reader reads AttemptAcki , chooses the opposite bit as its fresh attempt bit aReq, and writes aReq to AttemptReqi . If the writer makes enough progress to possibly endanger the scan, then during its service block of reader i it copies this attempt bit into AttemptAcki . Thus, after the scan, if the reader sees that the tripwire was not triggered, it knows the scan was safe and can return the value it read from the global buffer. If the tripwire is triggered, the reader does not trust the global scan. Instead, it relies on assistance from the writer. Each reader has a small mailbox, Mailboxi , through which the writer can deliver one piece of a value at a time. The reader first checks whether its read request has been acknowledged, by testing whether ReadAcki equals its request bit myReq. If the request has not yet been acknowledged, then the writer has not yet fixed a mailbox stream for this read, so the reader simply tries another iteration. If the request has been acknowledged, then the writer has fixed the current committed value for this read and stored it locally as localVali . From that point on, the writer streams the pieces of that fixed value through the reader’s mailbox. The writer and reader use a one-bit handshake, PieceReadyi and PieceAcki , to ensure that a new mailbox piece is not sent until the previous one has been received. When the two bits differ, the reader knows that a new piece is ready: it reads the piece from Mailboxi , appends it to its local list, and then acknowledges the piece by copying

Y. Wei and Y. Yavari

PieceReadyi into PieceAcki . This acknowledgement allows the writer to send the next piece later. The handshake prevents pieces from being skipped, duplicated, or overwritten before the reader consumes them. Thus a read has two possible outcomes. If it experiences little or no interference, it succeeds quickly by returning a direct scan of the active buffer G[V ]. If it repeatedly overlaps writes, then the writer’s service blocks gradually deliver the fixed value localVali through the mailbox. In either case, the reader eventually obtains a complete value: either directly from a stable global buffer, or piece by piece from the writer’s fixed mailbox stream.

5.3

Linearization Points

Writes: A write operation W that executes its commit step is linearized at configuration c(W ), the configuration immediately after its write to V (i.e., at line 3 of W ). Fast-Path Reads: A read operation R that returns through the fast path is linearized at the configuration immediately after the read of V in the successful fast-path iteration (i.e., at line 7 of R if R returns at line 10). Slow-Path Reads: For a read operation R by reader i, define myReq := 1 − ReadAcki , where ReadAcki is the value read by R at its first step. The read then writes ReadReqi := myReq. If R returns through the slow path, then R is linearized at the configuration immediately after the first writer step during R that writes ReadAcki := myReq (i.e., at the first writer’s line 10 during R that writes ReadAcki := myReq). This step exists for every slow-path read, as shown below. Pending operations are handled as follows. A pending write operation that has already executed its commit step is included and linearized at the corresponding configuration c(W ). A pending write that has not executed its commit step may be discarded. Pending reads may be discarded.

5.4

Proof Overview

The main correctness idea is that a reader either obtains a clean direct scan of the active global buffer, or else obtains all pieces of one fixed writer value through its mailbox. To prove linearizability, it suffices to prove that every completed read returns the value of the latest write linearized before the read’s assigned linearization point. The first key invariant is that, at every configuration, the active buffer G[V ] stores the value of the latest write that has linearized. This invariant holds because the writer first fills the inactive buffer with the new value and only then changes V to point to that buffer. Therefore, before the update to V , the old active buffer still stores the latest linearized write value; after the update to V , the new active buffer stores the newly linearized write value. For fast-path reads, namely reads whose tripwire is not triggered, the only danger is that the reader might scan a buffer while the writer is overwriting that same buffer. The tripwire prevents such a read from returning. Before scanning, the reader writes a fresh value to AttemptReqi . If the writer performs enough work to switch buffers and come back to overwrite the scanned buffer, then the writer must execute a service block for reader i in between. During that service block, it copies AttemptReqi into AttemptAcki . Hence, if the reader finishes its scan and still sees that AttemptAcki has not been updated to the fresh tripwire value, then the writer could not have overwritten the scanned buffer during the scan. The reader can therefore safely return the scanned value. For slow-path reads, namely reads whose tripwire is triggered until they collect all L mailbox pieces, the writer explicitly captures a stable value for the reader. When the writer

13

14

Space Complexity of Multi-word Single-Writer Registers

acknowledges reader i’s read request by writing to ReadAcki , it has already stored the current committed value in localVali and reset idxi to the beginning of that value. After this acknowledgement, the reader’s request and acknowledgement bits remain equal until the read returns, so the writer does not reset localVali or idxi for that reader during the read. The mailbox handshake then ensures that the reader receives the pieces of this fixed localVali in order. The writer does not send a new piece until the previous one has been acknowledged, so no piece is duplicated, skipped, or overwritten before the reader consumes it. Therefore, if the reader returns through the slow path, it returns exactly the fixed value captured by the writer at the acknowledgement configuration. The wait-freedom argument is based on bounding how many failed fast-path attempts a reader can suffer. Each writer operation has a bounded amount of work: it writes one global buffer and then scans the fixed set of readers once. For reads, each failed loop iteration either appends one mailbox piece or appends nothing. A productive failed iteration appends one piece, so there can be at most L such iterations. The key point is that two consecutive failed iterations cannot both be unproductive. If a writer service block causes the second failure, then immediately before the reader checks its mailbox in the second failed iteration, either a piece was already ready or the writer has just made one ready, unless all L pieces have already been received. Thus the second failed iteration must append a piece. Therefore the number of unproductive failed iterations is at most one more than the number of productive failed iterations. Since there are at most L productive failed iterations, every read completes after a bounded number of iterations. More concretely, each read executes at most 2L + 1 iterations, each costing O(L) reader steps, so every read completes in Θ(L2 ) reader steps. Similarly, writes complete in Θ(L + r) writer steps: the writer fills one L-piece buffer and then services r readers, each service costing Θ(1) steps. The Θ(r + L) bound on space usage can be shown by examination of the pseudo-code.

5.5

Fast-Path Correctness

▶ Invariant 6 (Active-buffer invariant). At every configuration, the active buffer G[V ] contains the value of the latest write whose commit step has occurred (i.e., the value of the most recently linearized write operation), or the initial value if no commit step has occurred. Proof. Initially, G[V ] contains the initial value. Consider a write operation W . The writer reads V , chooses the other buffer s := 1 − V , writes to all pieces of G[s], and only then writes V := s. Before c(W ), the active buffer is the old buffer G[V ] and is not modified by W . The step immediately preceding c(W ) changes V to s, and at configuration c(W ), G[s] has already been completely written to with the value of W . Therefore, at configuration c(W ), the active buffer G[s] contains the value of W . While G[s] remains active, the writer can write only to the inactive buffer G[1 − s]. Thus the active buffer cannot be modified until a later write first commits the other buffer. The invariant follows by induction over commit steps. ◀ ▶ Lemma 7 (Tripwire lemma). Consider one loop iteration of Readi . Suppose reader i writes AttemptReqi := aReq, then reads V = s, scans G[s], and finally observes AttemptAcki ̸= aReq. Then the writer writes to no piece of G[s] between the reader’s read of V and the end of the scan of G[s]. Proof. Let CV be the configuration immediately after the reader reads V = s, and let CE be the configuration immediately after the reader completes its scan of G[s]. Suppose, for contradiction, that the writer writes to some piece of G[s] between CV and CE . At

Y. Wei and Y. Yavari

configuration CV , buffer G[s] is active. The writer never writes to the active buffer. Therefore, before the writer can write to any piece of G[s], it must first make G[1 − s] active by writing V := 1 − s. Let W1 be the write operation that first writes V := 1 − s after CV . The write operation W1 cannot itself write to G[s] after publishing G[1 − s], because its buffer-writing phase precedes its commit step. Hence the first possible write to G[s] after CV occurs in a later write operation W2 . Between the commit step of W1 and the beginning of W2 , the single writer completes the reader scan of W1 . In the service block for reader i, the writer reads AttemptReqi and then writes the value read into AttemptAcki . Reader i wrote AttemptReqi := aReq before CV and does not change AttemptReqi again until after the final tripwire check of the same iteration. Since the service block of W1 occurs after CV and before any write to G[s] by W2 , the writer reads AttemptReqi = aReq and writes AttemptAcki := aReq before the alleged write to G[s] between CV and CE . Moreover, any later service block before the reader’s final tripwire check also reads AttemptReqi = aReq and writes AttemptAcki := aReq, because reader i has not changed AttemptReqi during this iteration. Therefore, immediately before the reader performs its final tripwire check, AttemptAcki equals aReq. This contradicts the assumption that the reader observes AttemptAcki ̸= aReq. Hence no piece of G[s] is written between CV and CE . ◀ ▶ Lemma 8 (Fast-path correctness). If a read returns through the fast path, then it returns the value of the latest write linearized before its fast-path linearization point. Proof. Let CV be the configuration immediately after the successful fast-path iteration reads V = s. By the active-buffer invariant, G[s] contains the value of the most recently linearized write at configuration CV , or the initial value if no write has committed. By the tripwire lemma, no piece of G[s] is modified between the read of V and the end of the scan of G[s]. Therefore the scan returns exactly the contents of G[s] at configuration CV . The read is linearized at configuration CV . Hence it returns the value of the latest write linearized before its linearization point. ◀

5.6

Slow-Path Correctness

Let R be a read operation by reader i, so myReq is the bit written by R to ReadReqi at its start. ▶ Lemma 9 (Acknowledgement occurs during the read). If R observes ReadAcki = myReq after its initial read of ReadAcki , then the writer executed a step ReadAcki := myReq after that initial read and before the observation. Proof. At the start of R, reader i reads the current value of ReadAcki and sets myReq to the opposite bit. Thus immediately after this read, ReadAcki ̸= myReq. Only the writer writes ReadAcki . Therefore, if reader i later observes ReadAcki = myReq, the writer must have written ReadAcki := myReq after the read of ReadAcki at the beginning of R and before that later observation. ◀ For a slow-path read R, let AR be the configuration immediately after the first writer step in the execution interval of R that writes ReadAcki := myReq (i.e., the first writer’s line 10 during R that writes ReadAcki := myReq). ▶ Lemma 10 (Stream initialization). Let R be a read by reader i that returns through the slow path. Earlier in the same read-request branch, before AR , the writer has set localVali to

15

16

Space Complexity of Multi-word Single-Writer Registers

the value of the write operation whose service block contains AR , set idxi := 0, and flushed the piece handshake by writing PieceReadyi := PieceAcki . Proof. The writer writes to ReadAcki only inside the read-request branch of the service block for reader i. In that branch, before writing to ReadAcki , the writer executes the assignments that set localVali to the value of the write whose service block is being executed, set idxi := 0, and write PieceReadyi := PieceAcki . Therefore the claim follows directly from the writer’s program order. ◀ ▶ Lemma 11 (No stream reset during the read). After configuration AR and before R returns, the writer does not reset localVali or idxi for reader i. Proof. After AR , we have ReadAcki = myReq. We show that from AR until R returns, ReadReqi = myReq always holds. If configuration AR is reached after R executes its write ReadReqi := myReq, then ReadReqi = myReq from that write until R returns, because reader i invokes no later new read and performs no later write to ReadReqi during R. Now suppose configuration AR is reached before R executes its write ReadReqi := myReq. Let B be the service block in which configuration AR is reached, and let Ct be the configuration immediately after B reads rReq := ReadReqi . Since at configuration AR we have ReadAcki = myReq, and the writer writes to ReadAcki the value rReq previously read in the same service block, the writer must have read rReq = myReq at configuration Ct . Moreover, the service block enters the stream-initialization branch only if rReq = ̸ ReadAcki at the read-request test. Hence, at configuration Ct , ReadAcki ̸= myReq. From configuration Ct until AR , the writer performs no other write to ReadAcki , and no later service block can occur before AR . Therefore ReadAcki ̸= myReq throughout the interval from Ct until AR . We claim that ReadReqi = myReq throughout the interval from Ct until AR . At configuration Ct , this holds because the writer read rReq = ReadReqi = myReq. The only process that writes to ReadReqi is reader i. Any such write is the first write of some read operation by reader i, and it writes the opposite of the value of ReadAcki read at the beginning of that operation. Since throughout the interval from Ct until AR we have ReadAcki ̸= myReq, every such write to ReadReqi writes the value myReq. Thus ReadReqi cannot change away from myReq before AR . Therefore, at configuration AR we have ReadReqi = ReadAcki = myReq. We now show that this equality persists until R writes ReadReqi := myReq. We first prove that if configuration AR is reached before R executes its write ReadReqi := myReq, then configuration AR is reached after R’s initial read of ReadAcki but before that write. Suppose by contradiction that configuration AR is reached before R’s initial read of ReadAcki . Since configuration AR lies in the execution interval of R, it is reached after R was invoked. Since reader i has no overlapping read operation and R has not yet performed any write to ReadReqi , ReadReqi does not change between AR and R’s initial read. By our discussion above, at configuration AR we have ReadReqi = ReadAcki = myReq. Thus the writer cannot enter the stream-initialization branch for reader i again before R’s initial read, because that branch requires ReadReqi ̸= ReadAcki . Hence R’s initial read would observe ReadAcki = myReq and would choose the opposite bit, contradicting the definition of myReq. Thus configuration AR cannot be reached before R’s initial read of ReadAcki . It follows that, if configuration AR is reached before R executes its write ReadReqi := myReq, then configuration AR is reached after R’s initial read of ReadAcki but before that write. During this part of R, reader i performs no write to ReadReqi . Since reader i has no

Y. Wei and Y. Yavari

overlapping read operation and no other process writes ReadReqi , ReadReqi remains equal to myReq until R writes ReadReqi := myReq. That later write leaves ReadReqi unchanged. Therefore, after AR and before R returns, we always have ReadReqi = ReadAcki = myReq. The writer enters the stream-initialization branch for reader i only when these two bits differ. Hence the writer does not enter that branch again before R returns, and so it does not reset localVali or idxi . ◀ ▶ Lemma 12 (Alternating-bit delivery). No mailbox piece is appended by R before AR . After AR and before R returns, the sequence of mailbox pieces appended by R is always a prefix of the fixed array localVali . If R appends L pieces, then the appended sequence is exactly the whole array localVali . Proof. Before reaching configuration AR , in the same read-request branch, the writer flushes the piece handshake; that is, it reads the current value of PieceAcki and then performs the flush write PieceReadyi := PieceAcki . We first justify that PieceAcki does not change between this read of PieceAcki and the flush write. Let B be the service block in which configuration AR is reached, and let Ct be the configuration immediately after B reads rReq := ReadReqi . We use the following fact established in the proof of the previous lemma: ReadReqi = myReq and ReadAcki ̸= myReq throughout the interval from Ct until AR . Now consider any read operation S by reader i that could write to PieceAcki after configuration Ct and before AR . Since reader i executes no overlapping read operations, either S wrote its request bit before configuration Ct , or S writes its request bit after configuration Ct . In the first case, S has not completed before configuration Ct , since it may later write to PieceAcki after configuration Ct . Since reader i executes no overlapping read operations, no later read operation by reader i can have started, and hence no later read operation can have written to ReadReqi , before configuration Ct . Therefore the value read by B from ReadReqi at configuration Ct is exactly the request bit of S. Thus the request bit of S is myReq. In the second case, S writes its request bit after configuration Ct and before AR . Since ReadReqi = myReq throughout this interval, this write to ReadReqi must write the value myReq. Thus the request bit of S is myReq. Thus, in either case, any read operation S by reader i that could write to PieceAcki after configuration Ct and before AR has request bit myReq. But such a write to PieceAcki can occur only after S passes its first guard, which requires observing ReadAcki = myReq. This is impossible before AR , because ReadAcki = ̸ myReq throughout the interval from Ct until AR . Therefore no read operation by reader i writes to PieceAcki between the flush read and the flush write. Thus, immediately after the flush write, no mailbox piece is ready for reader i, since PieceReadyi = PieceAcki . Reader i appends a mailbox piece only if both guards succeed: it must first observe ReadAcki = myReq, and then observe PieceReadyi ̸= PieceAcki . After R reads ReadAcki at its first step and before AR , the first guard is false by the definition of AR . Hence R cannot append any mailbox piece before AR , including a stale piece from an earlier stream. After the flush write but before the writer deposits the first piece of the current stream, the second guard is false. Here, depositing a piece means that the writer writes the piece to Mailboxi and then flips PieceReadyi . The flush write made PieceReadyi = PieceAcki , and the read operation R cannot change PieceAcki in this interval: from R’s initial read of ReadAcki until AR , R cannot pass the first guard, and after AR but before the first deposit, R cannot

17

18

Space Complexity of Multi-word Single-Writer Registers

pass the second guard. Therefore reader i cannot append a piece for the current stream until the writer has actually deposited one. After AR , by the no-reset lemma, localVali and idxi are not reset before R returns. The writer deposits a piece only when PieceAcki = PieceReadyi and idxi < L. In that case, it first writes Mailboxi := localVali [idxi ], then flips PieceReadyi , and then increments idxi . After the flip and before reader i acknowledges the piece by writing PieceAcki := PieceReadyi , we have PieceAcki ̸= PieceReadyi . This is because the writer flips PieceReadyi while PieceAcki is unchanged, and reader i has not yet performed the acknowledgement write. Therefore the writer cannot deposit another piece and cannot overwrite Mailboxi until that acknowledgement write occurs. Reader i appends a piece only when PieceReadyi ̸= PieceAcki . When it does so, it reads Mailboxi , appends that value, and acknowledges that piece. Therefore every appended piece is exactly the most recently deposited piece of this stream, and no deposited piece of this stream is overwritten before it is consumed. Since the writer increments idxi exactly once per deposited piece, pieces are deposited in strictly increasing index order. Thus the sequence of pieces appended by R is always a prefix of the fixed array localVali . If reader i appends L pieces, then the appended sequence is exactly all of localVali . ◀ ▶ Lemma 13 (Slow-path correctness). If a read returns through the slow path, then it returns the value of the latest write linearized before its slow-path linearization point. Proof. Let R be a slow-path read by reader i, and let AR be its linearization point. By the acknowledgement lemma, configuration AR lies in the execution interval of R. Since R appends mailbox pieces only after observing ReadAcki = myReq, and since R returns through the slow path only after appending L pieces, configuration AR is reached before R returns. Configuration AR is reached in the service block of some write operation W . The service block of W occurs after the commit step of W , so W has already linearized before AR . Because there is a single writer, no later write can commit before AR : at configuration AR , the writer is still executing the service block of W . Hence the latest write linearized before AR is exactly W . By the stream initialization lemma, before AR in the same read-request branch, the writer has set localVali to the value of W . By the no-reset lemma, localVali is not reset before R returns. By the alternating-bit delivery lemma, the L pieces returned by R are exactly the L pieces of that fixed localVali . Therefore R returns exactly the value of W , which is the latest write linearized before AR . ◀

5.7

Linearizability

▶ Theorem 14. The algorithm is linearizable as an implementation of a simulated atomic SW register. Proof. Assign linearization points as defined in Section 5.3. All these points lie inside the corresponding operation intervals. For writes this is immediate. For fast-path reads this is immediate. For slow-path reads, it follows from the acknowledgement lemma and from the fact that the read returns only after observing the acknowledgement and appending L pieces. Because each assigned point lies inside the corresponding operation interval, the induced order also respects the real-time order of non-overlapping operations. By the fast-path correctness lemma, every fast-path read returns the value of the latest write linearized before its fast-path linearization point. By the slow-path correctness lemma, every slow-path read returns the value of the latest write linearized before its slow-path linearization point.

Y. Wei and Y. Yavari

Therefore, in the sequential order induced by these linearization points, every read returns the value of the latest preceding write, or the initial value if no write precedes it. This is exactly the sequential specification of an atomic register. Hence the implementation is linearizable. ◀

5.8

Wait-Freedom and Step Complexity

Each base-register access counts as one step. Thus scanning a global buffer costs L reader steps, and writing to a global buffer costs L writer steps. ▶ Lemma 15 (Writes are bounded). Every Write operation completes in Θ(L + r) writer steps. Proof. A write reads V , writes L pieces into the inactive buffer, writes to V , and then executes one service block for each of the r readers. Writing to the inactive buffer costs Θ(L) steps. Each service block performs only a constant number of base-register accesses. Thus all service blocks together cost Θ(r) steps, and the whole write operation costs Θ(L + r) writer steps. ◀ Fix, for the rest of the wait-freedom argument, a read operation R by reader i, and let myReq be the bit written by R to ReadReqi at its start. A loop iteration of R is called failed if it does not return through the fast path. Equivalently, if the iteration chooses attempt bit aReq, then the final tripwire check observes AttemptAcki = aReq. A failed iteration is called productive if it appends one mailbox piece, and unproductive otherwise. ▶ Lemma 16 (Failed attempts are caused by writer acknowledgements). If an iteration of R chooses attempt bit aReq and fails, then after the reader’s initial read of AttemptAcki in that iteration and before the final tripwire check of that iteration, the writer executes a step AttemptAcki := aReq. Proof. At the beginning of the iteration, the reader reads AttemptAcki and chooses aReq to be the opposite bit. Therefore, immediately after that read, AttemptAcki ̸= aReq. The iteration fails only if the later tripwire check observes AttemptAcki = aReq. Since only the writer writes to AttemptAcki , the writer must have written AttemptAcki := aReq between those two reader steps. ◀ For a failed iteration I of R, we say that a service block B for reader i causes the failure of I if B contains a write AttemptAcki := aReq, where aReq is the attempt bit chosen by I, and this write occurs after I’s initial read of AttemptAcki and before I’s final tripwire check. By the failed-attempt lemma, every failed iteration has at least one service block that causes its failure. ▶ Lemma 17 (Bounding unproductive failed iterations). Let P be the number of productive failed iterations of R, and let U be the number of unproductive failed iterations of R. Then U ≤ P + 1. Proof. We first show that no two consecutive loop iterations of R can both be failed and unproductive. Suppose, for contradiction, that I1 and I2 are consecutive loop iterations of R, and that both are failed and unproductive. By the failed-attempt lemma, there is a service block B1 for reader i that causes the failure of I1 , and there is a service block B2 for reader i that causes the failure of I2 . Since B1 causes the failure of I1 , the write to AttemptAcki in B1

19

20

Space Complexity of Multi-word Single-Writer Registers

occurs during I1 . Since B2 causes the failure of I2 , the write to AttemptAcki in B2 occurs during I2 . The writer is sequential, and the write to AttemptAcki is the last step of a service block for reader i. Therefore B2 begins after the write to AttemptAcki in B1 . Since that write occurs during I1 , the service block B2 begins during I1 or later. In particular, B2 reads ReadReqi after R has already written ReadReqi := myReq. Consider the read-request part of B2 , where the writer reads rReq := ReadReqi and, if rReq ̸= ReadAcki , initializes the stream and writes ReadAcki := rReq. Since this part occurs after R has written ReadReqi := myReq, the writer reads rReq = myReq. If the writer observes ReadAcki ̸= myReq, then B2 initializes the stream for R and writes ReadAcki := myReq before executing its piece-transfer test, namely the test whether PieceAcki = PieceReadyi and idxi < L. If instead the writer observes ReadAcki = myReq, then by the acknowledgement lemma, configuration AR has already been reached. In either case, before B2 executes its piece-transfer test, AR exists and ReadAcki = myReq. Moreover, by the no-reset lemma, after AR and before R returns, the writer does not enter the stream-initialization branch again. Thus, after I2 fails its final tripwire check, namely the check whether AttemptAcki ̸= aReq, it will pass the first slow-path guard ReadAcki = myReq and reach the piece-ready test, namely the test whether PieceReadyi ̸= PieceAcki . We next show that PieceAcki does not change from the beginning of B2 until the pieceready test of I2 . The only process that writes to PieceAcki is reader i, and reader i writes to PieceAcki only after appending a mailbox piece. The service block B2 begins during I1 or later, and its write to AttemptAcki occurs during I2 , before the final tripwire check of I2 . Since I1 and I2 are consecutive loop iterations and both are unproductive, reader i appends no mailbox piece from the beginning of B2 through the piece-ready test of I2 . Therefore PieceAcki does not change during this interval. Let P A denote this constant value of PieceAcki . Now consider the piece-transfer test of B2 . First suppose that, at this test, PieceReadyi ̸= P A. Then a mailbox piece is already ready for reader i, and B2 does not deposit another piece, because the deposit condition requires PieceAcki = PieceReadyi . Since PieceAcki remains equal to P A, and since the writer does not enter the stream-initialization branch again before R returns, no later service block before the piece-ready test of I2 can make this ready piece disappear or overwrite it. So, any later piece-transfer test also sees PieceAcki ̸= PieceReadyi and therefore cannot deposit another piece. Next suppose that, at the piece-transfer test of B2 , PieceReadyi = P A and idxi < L. Then B2 deposits the next piece: it writes the piece to Mailboxi , flips PieceReadyi , and increments idxi . Since PieceAcki remains equal to P A, after the flip we have PieceReadyi = ̸ PieceAcki . As in the previous case, no later service block before the piece-ready test of I2 can enter the stream-initialization branch or deposit another piece, so this ready piece remains ready until I2 reaches its piece-ready test. It remains to consider the case in which, at the piece-transfer test of B2 , PieceReadyi = P A and idxi = L. In this case no mailbox piece is ready, and the writer has already deposited all L pieces of the fixed stream for R. Since no mailbox piece is ready, the last deposited piece has already been acknowledged by reader i, meaning reader i has written PieceAcki := PieceReadyi after reading that piece from Mailboxi . Reader i acknowledges a piece only after appending it. Since reader i has no overlapping read operation, those acknowledgements after AR belong to R. Therefore R has already appended all L pieces of the fixed stream. By the alternating-bit delivery lemma, the sequence appended by R is exactly the whole fixed array localVali . Hence

Y. Wei and Y. Yavari

the loop condition of R is already false, so R cannot execute the later iteration I2 . This contradicts the assumption that I2 is a loop iteration of R. Thus, in every possible case in which I2 can occur, when I2 reaches its piece-ready test we have PieceReadyi ̸= PieceAcki . Since I2 also passes the first guard ReadAcki = myReq, it appends a mailbox piece. This contradicts the assumption that I2 is unproductive. Therefore no two consecutive loop iterations of R can both be failed and unproductive. It follows that among the failed iterations of R, no two unproductive iterations occur consecutively. Hence the unproductive failed iterations can appear only before the first productive failed iteration, after a productive failed iteration, or not at all. Therefore the number of unproductive failed iterations is at most one more than the number of productive failed iterations. Thus U ≤ P + 1. ◀ ▶ Lemma 18 (Bounded number of read iterations). Every Readi operation executes at most 2L + 1 loop iterations. Proof. Each productive failed iteration appends exactly one piece. Since the loop condition is that fewer than L pieces have been appended, there can be at most L productive failed iterations. Let P be the number of productive failed iterations and U the number of unproductive failed iterations. By the preceding lemma, U ≤ P + 1. If the read terminates through the slow path, then it terminates immediately after the Lth productive failed iteration. Thus P = L, and the total number of iterations is P + U ≤ L + (L + 1) = 2L + 1. If the read terminates through the fast path, then it has one final successful iteration. Before that final successful iteration, it has P ≤ L − 1 productive failed iterations. Hence the total number of iterations is at most P + U + 1 ≤ P + (P + 1) + 1 = 2P + 2 ≤ 2L. In either case, the number of loop iterations is at most 2L + 1. ◀ ▶ Theorem 19. Every write completes in Θ(L + r) writer steps, and every read completes in Θ(L2 ) reader steps in the worst case. Therefore, the implementation is wait-free. Proof. By the write-bound lemma, every write operation completes after Θ(L + r) writer steps. For a read operation, each loop iteration performs a constant number of base-register accesses and one scan of a global buffer, costing Θ(L) reader steps. By the bounded-iteration lemma, a read executes at most 2L + 1 loop iterations. Furthermore, a slow-path read executes at least L iterations since it appends at most a single piece in each iteration. Such slow-path executions exist: after the reader announces its request, the scheduler can make the writer execute a service block for reader i during each of L consecutive read iterations, causing each tripwire check to fail while delivering one mailbox piece per iteration. Therefore each read completes in Θ(L2 ) reader steps in the worst case. These bounds depend only on r and L, not on the relative speeds or failures of other processes. Therefore every operation completes in a bounded number of its own steps. The implementation is wait-free. ◀

6

Conclusion

We study the problem of implementing m-valued SW registers from b-valued base registers of the same type and prove matching upper and lower bounds on its space complexity. On the lower-bound side, welshowed m that any obstruction-free implementation with an invisible reader uses at least m−1 base registers, an exponential improvement over the b−1  m trivial information-theoretic Ω log lower bound and the constant factor improvements log b

21

22

Space Complexity of Multi-word Single-Writer Registers

l  m log m due to Chaudhuri and Welch [4]. We extended this to a min m−1 lower , r + b−1 log b bound for all implementations, whether at least one reader is invisible or every reader is visible. On the upper-bound side, we gave await-free implementation of a multi-word atomic  m register from atomic base registers using Θ r + log space. Combining this with existing log b   
log m m Θ m space constructions [4, 11] yields an upper bound of Θ min , r + , which b b log b asymptotically matches  our lower bound. This improves upon the previous best upper bound   log m . of Θ min m , r b log b These bounds are robust in two senses. The lower bound only requires the simulated register to be regular and it only requires obstruction-free progress, whereas the upper bound ensures the simulated register is atomic and guarantees wait-free progress. The two therefore pin down the space complexity for the entire range of settings in between. m log m Chen and Wei’s visible-reader algorithm uses Θ(r log log b ) space and Θ( log b ) steps per read m and write [5], whereas our asymptotically space-optimal algorithm uses Θ(r + log log b ) space, 2

m m log m Θ( log ) read steps, and Θ(r + log log b ) write steps. Whether the optimal Θ(r + log b ) space log2 b m bound can be achieved together with Θ( log log b ) read and write step complexity remains open.

AI Disclosure. We used Claude Opus 4.8 and GPT 5.5 to help polish writing throughout the paper. We also used Gemini 3.1 to test and generate counterexamples to earlier iterations of our algorithm. The authors verified the correctness and originality of all content, including references. References 1 2 3 4 5

6 7 8

9 10 11

Hagit Attiya and Jennifer Welch. Distributed computing: fundamentals, simulations, and advanced topics, volume 19. John Wiley & Sons, 2004. Alon Berger, Idit Keidar, and Alexander Spiegelman. Integrated bounds for disintegrated storage. In Proc. DISC. LIPIcs, 2018. Soma Chaudhuri, Martha J Kosa, and Jennifer L Welch. One-write algorithms for multivalued regular and atomic registers. Acta Informatica, 37(3):161–192, 2000. Soma Chaudhuri and Jennifer L Welch. Bounds on the costs of multivalued register implementations. SIAM Journal on Computing, 23(2):335–354, 1994. Tian Ze Chen and Yuanhao Wei. Step optimal implementations of large single-writer registers. In LIPIcs-Leibniz International Proceedings in Informatics, volume 70. Schloss DagstuhlLeibniz-Zentrum fuer Informatik, 2017. M. Herlihy and J. Wing. Linearizability: A correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst., 12(3):463–492, 1990. Leslie Lamport. On interprocess communication. Distributed computing, 1(2):86–101, 1986. Andreas Larsson, Anders Gidenstam, Phuong Hoai Ha, Marina Papatriantafilou, and Philippas Tsigas. Multiword atomic read/write registers on multiprocessor systems. ACM Journal of Experimental Algorithmics, 13, 2008. G. L. Peterson. Concurrent reading while writing. ACM Trans. Program. Lang. Syst., 5(1):46– 55, 1983. K Vidyasankar. Converting lamport’s regular register to atomic register. Information Processing Letters, 28(6):287–290, 1988. K. Vidyasankar. A very simple construction of 1-writer multireader multivalued atomic variable. Information Processing Letters, 37(6):323–326, 1991. doi:10.1016/0020-0190(91)90149-C.

Related documents

• Meaning without content: on the metasemantics of register#112016
• Two optimal parallel algorithms on the commutation class of a word#643393
• Lexicon Grammaticorum#341170
• Parking functions, Smirnov words, and noncrossing Chow polynomials#972080
• Sparse multi-decoder recursive projection aggregation for Reed-Muller codes#476216