Brief Announcement: How Fast Reads Affect Multi-Valued Register Simulations
Conference Paper
Overview
Research
Identity
Additional Document Info
Other
View All
Overview
abstract
2019 Authors. We consider the problem of simulating a k-valued register in a wait-free manner using binary registers as building blocks, where k 2. We show that for any simulation using atomic binary base registers to simulate a safe k-valued register in which the read algorithm takes the optimal number of steps (log2 k), the write algorithm must take at least log2 k steps in the worst case. A fortiori, the same lower bound applies when the simulated register should be regular. Previously known algorithms show that both these lower bounds are tight. We also show that in order to simulate an atomic k-valued register for two readers, the optimal number of steps for the read algorithm must be strictly larger than log2 k.
name of conference
Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing