Brief announcement: On the robustness of (semi)fast quorum-based implementations of atomic shared memory
Chryssis Georgiou, Nicolas Nicolaou, Alexander A. Shvartsman · 2008
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 < S t − 2, then single communication round-trip reads are possible. Such an implementation given in [4] is called fast. Subsequently, Georgiou et al. [3] relaxed the constraint in [4], and proposed semifast implementations with unbounded number of readers, where under realistic conditions most reads need only a single communication round-trip to complete. Their approach groups collections of readers into virtual nodes. Semifast behavior of their algorithm is preserved as long as the number of virtual nodes V is constrained by V < S t − 2. 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. 1. COMPUTATIONAL MODEL An atomic SWMR implementation is fast if all read and write operations complete in a single communication round-trip in any execution. A semifast implementation [3] allows one complete slow read operation for each write, and all the rest read/write operations must be fast. Lastly an implementation is non-robust if it has a single point of failure. A quorum system Q is a collection of sets Qi such that, ∀Qi, Qj ∈ Q : Qi ∩Qj 6= ∅. A quorum Qi ∈ Q is faulty if it contains a crashed process. We assume that at least one quorum in Q is non-faulty in any execution of the algorithm.