The LAW theorem: Local Reads and Linearizable Asynchronous Replication

Summary: Proves that crash-tolerant, linearizable asynchronous read/write registers cannot provide local reads, exposing a fundamental consistency–asynchrony tradeoff. Introduces almost-local reads (ALRs), preserving linearizability and asynchrony with near-local cost, substantially boosting Raft throughput. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 14112
Venue: VLDB
Year: 2025
Pagerank: 5.3766157e-05
Overall Rank: 8,726 | 40.14%
DOI: 10.14778/3746405.3746411

Incoming Non-self Citations Over Time

Authors

1. Antonios Katsarakis (Huawei)
2. Emmanouil Giortamis (Technical University of Munich)
3. Vasilis Gavrielatos (Huawei)
4. Pramod Bhatotia (Technical University of Munich)
5. Aleksandar Dragojevic (OpenAI)
6. Boris Grot (University of Edinburgh)
7. Vijay Nagarajan (University of Utah)
8. Panagiota Fatourou (Hellas; University of Crete)

BibTeX Citation

@article{katsarakis_vldb25,
        title = {{The LAW theorem: Local Reads and Linearizable Asynchronous Replication}},
        author = {Katsarakis, Antonios and Giortamis, Emmanouil and Gavrielatos, Vasilis and Bhatotia, Pramod and Dragojevic, Aleksandar and Grot, Boris and Nagarajan, Vijay and Fatourou, Panagiota},
        journal = {PVLDB},
        series = {{VLDB} '25},
        volume = {18},
        number = {9},
        pages = {2831--2845},
        doi = {10.14778/3746405.3746411},
        url = {https://doi.org/10.14778/3746405.3746411},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,467	LeaseGuard: Raft Leases Done Right	2026	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 18 of 18 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
47	PNUTS: Yahoo!'s Hosted Data Serving Platform	2008	VLDB	0.00044503718
57	Calvin: Fast Distributed Transactions for Partitioned Database Systems	2012	SIGMOD	0.00040139242
144	Megastore: Providing Scalable, Highly Available Storage for Interactive Services	2011	CIDR	0.00029554682
208	CockroachDB: The Resilient Geo-Distributed SQL Database	2020	SIGMOD	0.00024968157
271	TiDB: A Raft-based HTAP Database	2020	VLDB	0.00022703024
400	Impossibility of Distributed Consensus with One Faulty Process	1983	PODS	0.00019173482
607	F1: A Distributed SQL Database That Scales	2013	VLDB	0.00015800238
867	Coordination Avoidance in Database Systems	2015	VLDB	0.00013511197
1,247	Don't be lazy, be consistent: Postgres-R, A new way to implement Database Replication	2000	VLDB	0.00011500006
1,593	F1 – The Fault-Tolerant Distributed RDBMS Supporting Google's Ad Business	2012	SIGMOD	0.00010252961
1,961	Scalable Atomic Visibility with RAMP Transactions	2014	SIGMOD	9.4000927e-05
2,843	Rose: Compressed, log-structured replication	2008	VLDB	8.0617003e-05
3,666	Harmonia: Near-Linear Scalability for Replicated Storage with In-Network Conflict Detection	2020	VLDB	7.2142119e-05
4,523	Tunable Consistency in MongoDB	2019	VLDB	6.6463056e-05
4,996	TAOBench: An End-to-End Benchmark for Social Network Workloads	2022	VLDB	6.4081254e-05
8,089	LEGOStore: A Linearizable Geo-Distributed Store Combining Replication and Erasure Coding	2022	VLDB	5.4894353e-05
8,239	In-Network Leaderless Replication for Distributed Data Stores	2022	VLDB	5.4595803e-05
9,731	A Byzantine Fault Tolerant Storage for Permissioned Blockchain	2021	SIGMOD	5.2280514e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,383	LSM-Raft: Optimizing Raft for LSM-tree Store	2026	SIGMOD
2	4,829	Strong consistency is not hard to get: Two-Phase Locking and Two-Phase Commit on Thousands of Cores	2019	VLDB
3	13,098	A Tight Upper Bound on the Benefits of Replication and Consistency Control Protocols	1991	PODS
4	4,274	Causal Consistency and Latency Optimality: Friend or Foe?	2018	VLDB
5	6,151	Replication and Consistency: Being Lazy Helps Sometimes	1997	PODS
6	1,152	Fast Algorithms for Maintaining Replica Consistency in Lazy Master Replicated Databases	1999	VLDB
7	6,296	Dissecting the Performance of Strongly-Consistent Replication Protocols	2019	SIGMOD
8	8,239	In-Network Leaderless Replication for Distributed Data Stores	2022	VLDB
9	5,910	Replication, Consistency, and Practicality: Are These Mutually Exclusive?	1998	SIGMOD
10	10,870	Asymmetric Linearizable Local Reads	2025	VLDB