Consistency Analysis of Replication-Based Probabilistic Key-Value Stores
This work addresses the problem of optimizing performance and consistency for users of distributed systems, though it is incremental as it builds on existing probabilistic frameworks.
The paper tackled the latency-consistency trade-off in distributed key-value stores by deriving a closed-form expression for inconsistency probability analytically, enabling fine-tuning of guarantees that was previously intractable with Monte Carlo simulations.
Partial quorum systems are widely used in distributed key-value stores due to their latency benefits at the expense of providing weaker consistency guarantees. The probabilistically bounded staleness framework (PBS) studied the latency-consistency trade-off of Dynamo-style partial quorum systems through Monte Carlo event-based simulations. In this paper, we study the latency-consistency trade-off for such systems analytically and derive a closed-form expression for the inconsistency probability. Our approach allows fine-tuning of latency and consistency guarantees in key-value stores, which is intractable using Monte Carlo event-based simulations.