Brief Announcement: How Fast Reads Affect Multi-Valued Register Simulations Conference Paper uri icon

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

published proceedings

  • PROCEEDINGS OF THE 2019 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING (PODC '19)

author list (cited authors)

  • Chaudhuri, S., Frank, R., & Welch, J. L.

citation count

  • 0

complete list of authors

  • Chaudhuri, Soma||Frank, Reginald||Welch, Jennifer L

publication date

  • January 2019