Paper review: Probabilistically Bounded Staleness for Practical Partial Quorums
![Image](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi72Cds1gxtCjUcsqdqTjm0284d_8d252SpdbqzfcV0CbtVjt1uBcEtpMPXuW3P6PKrws-HjYfX5h_Bk4tyAVq0eru5eCIu6zXjCCVdyFP2KmIqWgqPS4h8btXEiMhWMgOM_44IpQnJfjE/s400/PBS2.png)
There is a fundamental trade-off between operation latency and data consistency in distributed database replication. The PBS paper (VLDB'12) examines this trade-off for partial quorum replicated data stores. Quorum systems We can categorize quorum systems into strict versus partial quorums. Strict quorum systems ensure strong consistency by ensuring that read & write replica sets overlap: $R + W > N$. Here N is the total number of replicas in the quorum, R is the number of replicas that need to reply to a read query, and W is the number of replicas that need to reply to a write query. Employing partial quorums can lower latency by requiring fewer replicas to respond, but R and W need not overlap: $R+W \leq N$. Such partial quorums offer eventual consistency . Here is a visual representation of an expanding quorum system. The coordinator forwards a write requests to all N replicas, and wait for W acknowledgements for responding back to the client for completion of