DISC'26 paper proves optimal space for multi-word registers

Yuanhao Wei and Yousof Yavari's new paper, accepted at DISC'26, tackles a classic distributed systems problem: how many small single-writer registers are needed to simulate one large register that can be read by multiple processes. The authors deliver matching upper and lower bounds, effectively settling the space complexity for this fundamental primitive. Their results are strikingly strong—the lower bounds hold even for the weakest consistency model (regular registers) and for obstruction-free implementations, meaning they apply to lock-free and wait-free designs as well. The first lower bound, for the invisible-reader case, requires at least ceil((m-1)/(b-1)) base registers, an exponential improvement over the previous best known bound.

The paper also covers the general case with both visible and invisible readers, proving a lower bound of ceil(min((m-1)/(b-1), r + log m/log b)) registers, where r is the number of readers. To show this is tight, they construct a wait-free algorithm that simulates a multi-word atomic register using Θ(r + log m/log b) space. This improves the previous best upper bound of Θ(min(m/b, r·log m/log b)). For distributed systems, these results give practitioners a precise understanding of the memory overhead required for register simulation, and the new algorithm is directly usable in shared-memory systems, concurrent data structures, and replicated state models.