on the robustness of (semi) fast quorum-based implementations of atomic shared memory
Atomic (linearizable) read/write memory is a fundamental abstractions in distributed computing. Following a seminal implementation of atomic memory of Attiya et al. [6], a folklore belief developed that in messaging-passing atomic memory implementations "reads must write." However, work by Dutta et al. [4] established that if the number of readers R is constrained with respect to the number of replicas S and the maximum number of crash-failures t so that R V is constrained by V Quorum systems are well-known mathematical tools that provide means for achieving coordination between processors in distributed systems. Given that the approach of Attiya et al. [6] is readily generalized from majorities to quorums (e.g., [5, 2]), and that the algorithms in [4] and [3] rely on intersections in specific sets of responding servers, one may ask: Can we characterize the conditions enabling fast implementations in a general quorumbased framework? This is what we establish in this work.
quorums atomicity fault-tolerance read/write registers