Using Paxos to Build a Scalable, Consistent, and Highly Available Datastore

Summary: Spinnaker combines range partitioning, three-way replication, and transactional get/put with selectable strong or timeline-consistent reads. Paxos preserves read/write availability under arbitrary failure sequences short of losing a majority, with near-eventual-consistency performance. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 10445
Venue: VLDB
Year: 2011
Pagerank: 0.0001140641
Overall Rank: 1,267 | 91.31%
DOI: 10.14778/1938545.1938547

Incoming Non-self Citations Over Time

Authors

1. Jun Rao (LinkedIn)
2. Eugene J. Shekita (IBM)
3. Sandeep Tata (IBM)

BibTeX Citation

@article{rao_vldb11,
        title = {{Using Paxos to Build a Scalable, Consistent, and Highly Available Datastore}},
        author = {Rao, Jun and Shekita, Eugene J. and Tata, Sandeep},
        journal = {PVLDB},
        series = {{VLDB} '11},
        volume = {4},
        number = {4},
        pages = {243--254},
        doi = {10.14778/1938545.1938547},
        url = {https://doi.org/10.14778/1938545.1938547},
        year = {2011}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
57	Calvin: Fast Distributed Transactions for Partitioned Database Systems	2012	SIGMOD	0.00040139242
1,171	Photon: Fault-tolerant and Scalable Joining of Continuous Data Streams	2013	SIGMOD	0.00011826434
1,637	On the Design and Scalability of Distributed Shared-Data Databases	2015	SIGMOD	0.0001015538
2,477	Azure Data Lake Store: A Hyperscale Distributed File Service for Big Data Analytics	2017	SIGMOD	8.5239378e-05
5,065	Serializability, not Serial: Concurrency Control and Availability in Multi-Datacenter Datastores	2012	VLDB	6.3775656e-05
5,775	Walnut: A Unified Cloud Object Store	2012	SIGMOD	6.0923066e-05
6,509	Scalable Transactions across Heterogeneous NoSQL Key-Value Data Stores	2013	VLDB	5.8572742e-05
8,239	In-Network Leaderless Replication for Distributed Data Stores	2022	VLDB	5.4595803e-05
9,589	A Framework for Supporting DBMS-like Indexes in the Cloud	2011	VLDB	5.2521633e-05
10,388	P4KVS: A Role-Replica Separation Offloading Method to Achieve In-Network Consistency for KV Stores Based on P4 Switches	2026	SIGMOD	5.093636e-05
11,279	Cloud Actor-Oriented Database Transactions in Orleans	2024	VLDB	5.093636e-05
12,290	DAX: A Widely Distributed Multi-tenant Storage Service for DBMS Hosting	2013	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
7	Implementation Techniques For Main Memory Database Systems	1984	SIGMOD	0.00083340894
47	PNUTS: Yahoo!'s Hosted Data Serving Platform	2008	VLDB	0.00044503718
480	Nonblocking Commit Protocols	1981	SIGMOD	0.00017789222
1,023	Extreme Scale with Full SQL Language Support in Microsoft SQL Azure	2010	SIGMOD	0.00012591922
1,247	Don't be lazy, be consistent: Postgres-R, A new way to implement Database Replication	2000	VLDB	0.00011500006
1,406	Middleware-based Database Replication: The Gaps Between Theory and Practice	2008	SIGMOD	0.00010866135
1,800	A Scalable Data Platform for a Large Number of Small Applications	2009	CIDR	9.7290813e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,666	Harmonia: Near-Linear Scalability for Replicated Storage with In-Network Conflict Detection	2020	VLDB
2	4,852	Scaling Replicated State Machines with Compartmentalization	2021	VLDB
3	5,207	Unifying Consensus and Atomic Commitment for Effective Cloud Data Management	2019	VLDB
4	10,874	HoliPaxos: Towards More Predictable Performance in State Machine Replication	2025	VLDB
5	1,749	PaxosStore: High-availability Storage Made Practical in WeChat	2017	VLDB
6	3,419	DPaxos: Managing Data Closer to Users for Low-Latency and Mobile Applications	2018	SIGMOD
7	6,296	Dissecting the Performance of Strongly-Consistent Replication Protocols	2019	SIGMOD
8	4,741	PigPaxos: Devouring the Communication Bottlenecks in Distributed Consensus	2021	SIGMOD
9	5,065	Serializability, not Serial: Concurrency Control and Availability in Multi-Datacenter Datastores	2012	VLDB
10	2,497	Low-Latency Multi-Datacenter Databases using Replicated Commit	2013	VLDB