Linearizable Quorum Reads in Paxos


Aleksey Charapko, University at Buffalo, SUNY; Microsoft, Redmond, WA; Ailidani Ailijiang, Microsoft, Redmond, WA; Murat Demirbas, University at Buffalo, SUNY; Microsoft, Redmond, WA


Many distributed systems/databases rely on Paxos for providing linearizable reads. Linearizable reads in Paxos are achieved either through running a full read round with followers, or via reading from a stable leader which holds leases on followers. We introduce a third method for performing linearizable reads by eschewing the leader and only reading from a quorum of followers. For guaranteeing linearizability, a bare quorum read is insufficient and it needs to be amended with a rinse phase to account for pending update operations. We present our Paxos Quorum Read (PQR) protocol that implements this. Our evaluations show that PQR significantly improves throughput compared to the other methods. The evaluations also show that PQR achieves comparable latency to the read from stable Paxos leader optimization.

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

@inproceedings {234735,
author = {Aleksey Charapko and Ailidani Ailijiang and Murat Demirbas},
title = {Linearizable Quorum Reads in Paxos},
booktitle = {11th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage 19)},
year = {2019},
address = {Renton, WA},
url = {},
publisher = {USENIX Association},
month = jul