Upper and Lower Bounds on the Space Complexity of Multi-word Single-Writer Registers
Details
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 implementation that has an invisible reader requires at least ⌈ m−1 b−1 ⌉ base registers. A reader is considered 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 a ⌈min( m−1 b−1 , r + log m log b )⌉ space lower bound, where r is the number of readers. To show that this lower bound is asymptotically tight, we develop a wait-free algorithm for simulating a multi-word atomic register from atomic base registers using Θ(r + log m log b ) space. Combining this algorithm with known invisible-reader constructions gives a Θ(min( m b , r + log m log b )) space upper bound. This improves upon the previously known space upper bound of Θ(min( m b , r log m log b )).
