Step-optimal implementations of large single-writer registers
Tian Ze Chen, Yuanhao Wei · Theoretical Computer Science · 2020
We present two wait-free algorithms for simulating an ℓ-bit single-writer register from k-bit single-writer registers, for any k≥1. Our first algorithm has Θ(ℓ/k) step complexity for both and and uses Θ(4ℓ−k) registers. Our second algorithm has Θ(ℓ/k+(logn)/k) step complexity for both and , where n is the number of readers, but uses only Θ(nℓ/k) registers. By using the first algorithm when ℓ≤(logn)/2 and the second algorithm when ℓ>(logn)/2, we get a combined implementation with Θ(ℓ/k) step complexity using Θ(nℓ/k) registers which works for any 1≤k<ℓ. We also prove that any implementation with O(ℓ/k) step complexity for requires Ω(ℓ/k) step complexity for . Reading ℓ bits requires at least ⌈ℓ/k⌉ reads of k-bit registers, so our lower bound shows that our combined implementation is step-optimal.