Quorums over codes

Abstract

We consider the design and analysis of quorum systems over erasure coded warm data (with low frequency of writes and accesses in general) to guarantee sequential consistency under a fail-stop model while supporting atomic read-modify-write operations by multiple clients. We propose a definition of asymmetric quorum systems that suit the framework of coded data by explicitly exploiting the structural properties of code and instantiate it over distinct families of coding strategies: maximum distance separable (MDS) codes and codes with locality, and we indicate a mechanism for synchronizing stale nodes using differential updates, which again exploits the code structures. The proposed quorum system’s behavior is analyzed theoretically, exploring several aspects: viability of quorums under node unavailability; contention of resources between read and write operations; and quorum load. We complement these theoretical exploration with simulation based experiments to quantify the behavior of the proposed mechanism. The overall study demonstrates the feasibility and practicality of quorums over codes under practicable assumptions for achieving a stringent form of consistency, specifically, sequential consistency, while the stored data is being mutated by potentially multiple processes that might read and then modify the existing data. We achieve this in-place, without having to resort to store multiple versions of the data.