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

Yuanhao Wei, Yousof Yavari

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…