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: h9265ed2ffb6c00ab
Venue: VLDB
Year: 2025
Pagerank: 5.2361195e-05
Overall Rank: 8,918 | 40.23%
DOI: 10.14778/3746405.3746411
PDF: Download (CC BY-NC-ND 4.0)

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,726	LeaseGuard: Raft Leases Done Right	2026	SIGMOD	4.9605343e-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.00043937456
54	Calvin: Fast Distributed Transactions for Partitioned Database Systems	2012	SIGMOD	0.00040489652
139	Megastore: Providing Scalable, Highly Available Storage for Interactive Services	2011	CIDR	0.00029386971
186	CockroachDB: The Resilient Geo-Distributed SQL Database	2020	SIGMOD	0.00026001543
232	TiDB: A Raft-based HTAP Database	2020	VLDB	0.00023776373
394	Impossibility of Distributed Consensus with One Faulty Process	1983	PODS	0.00019141584
617	F1: A Distributed SQL Database That Scales	2013	VLDB	0.00015511217
807	Coordination Avoidance in Database Systems	2015	VLDB	0.00013734149
1,264	Don't be lazy, be consistent: Postgres-R, A new way to implement Database Replication	2000	VLDB	0.00011265551
1,576	F1 – The Fault-Tolerant Distributed RDBMS Supporting Google's Ad Business	2012	SIGMOD	0.00010156207
1,952	Scalable Atomic Visibility with RAMP Transactions	2014	SIGMOD	9.2989778e-05
2,905	Rose: Compressed, log-structured replication	2008	VLDB	7.871271e-05
3,748	Harmonia: Near-Linear Scalability for Replicated Storage with In-Network Conflict Detection	2020	VLDB	7.0350137e-05
4,599	Tunable Consistency in MongoDB	2019	VLDB	6.4971174e-05
4,783	TAOBench: An End-to-End Benchmark for Social Network Workloads	2022	VLDB	6.4055647e-05
8,282	LEGOStore: A Linearizable Geo-Distributed Store Combining Replication and Erasure Coding	2022	VLDB	5.345991e-05
8,429	In-Network Leaderless Replication for Distributed Data Stores	2022	VLDB	5.3169161e-05
9,944	A Byzantine Fault Tolerant Storage for Permissioned Blockchain	2021	SIGMOD	5.0914372e-05

Semantically Similar Papers

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