Back to papers
The LAW theorem: Local Reads and Linearizable Asynchronous Replication
Summary: Proves the LAW impossibility: in crash‑tolerant asynchronous systems (one crash), linearizable reads can't be purely local. Presents almost-local reads (ALRs) and two lightweight schemes that give near-local latency while preserving linearizability under asynchrony; negligible loss on ZAB/Hermes, >2.5× on Raft.
(summarized by gpt-5-mini on Feb 09 2026)
- Paper ID
- 13924
- Venue
- VLDB
- Year
- 2025
- Pagerank
- 4.4937074e-05
- Overall Rank
- 8,521 | 40.73%
- DOI
-
10.14778/3746405.3746411
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 1 of 1 citing papers.
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 |
| 53 |
PNUTS: Yahoo!'s Hosted Data Serving Platform |
2008 |
VLDB |
0.00066144767 |
| 122 |
Calvin: Fast Distributed Transactions for Partitioned Database Systems |
2012 |
SIGMOD |
0.00045316749 |
| 189 |
Megastore: Providing Scalable, Highly Available Storage for Interactive Services |
2011 |
CIDR |
0.00035925334 |
| 377 |
Impossibility of Distributed Consensus with One Faulty Process |
1983 |
PODS |
0.00025059979 |
| 390 |
CockroachDB: The Resilient Geo-Distributed SQL Database |
2020 |
SIGMOD |
0.00024607299 |
| 488 |
TiDB: A Raft-based HTAP Database |
2020 |
VLDB |
0.000220409 |
| 890 |
F1 – The Fault-Tolerant Distributed RDBMS Supporting Google's Ad Business |
2012 |
SIGMOD |
0.00015570935 |
| 906 |
F1: A Distributed SQL Database That Scales |
2013 |
VLDB |
0.00015448884 |
| 1,028 |
Coordination Avoidance in Database Systems |
2015 |
VLDB |
0.00014584518 |
| 1,428 |
Don't be lazy, be consistent: Postgres-R, A new way to implement Database Replication |
2000 |
VLDB |
0.00012040675 |
| 2,273 |
Scalable Atomic Visibility with RAMP Transactions |
2014 |
SIGMOD |
9.1329997e-05 |
| 2,558 |
Rose: Compressed, log-structured replication |
2008 |
VLDB |
8.5455497e-05 |
| 3,739 |
Harmonia: Near-Linear Scalability for Replicated Storage with In-Network Conflict Detection |
2020 |
VLDB |
6.8031881e-05 |
| 4,347 |
Tunable Consistency in MongoDB |
2019 |
VLDB |
6.269146e-05 |
| 5,463 |
TAOBench: An End-to-End Benchmark for Social Network Workloads |
2022 |
VLDB |
5.4938614e-05 |
| 8,091 |
LEGOStore: A Linearizable Geo-Distributed Store Combining Replication and Erasure Coding |
2022 |
VLDB |
4.5885892e-05 |
| 8,243 |
In-Network Leaderless Replication for Distributed Data Stores |
2022 |
VLDB |
4.5518393e-05 |
| 9,597 |
A Byzantine Fault Tolerant Storage for Permissioned Blockchain |
2021 |
SIGMOD |
4.3191755e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 10,092 |
LSM-Raft: Optimizing Raft for LSM-tree Store |
2026 |
SIGMOD |
4.1945683e-05 |
| 5,512 |
Strong consistency is not hard to get: Two-Phase Locking and Two-Phase Commit on Thousands of Cores |
2019 |
VLDB |
5.4665318e-05 |
| 12,903 |
A Tight Upper Bound on the Benefits of Replication and Consistency Control Protocols |
1991 |
PODS |
4.1945683e-05 |
| 4,601 |
Causal Consistency and Latency Optimality: Friend or Foe? |
2018 |
VLDB |
6.0572606e-05 |
| 5,524 |
Replication and Consistency: Being Lazy Helps Sometimes |
1997 |
PODS |
5.4601032e-05 |
| 796 |
Fast Algorithms for Maintaining Replica Consistency in Lazy Master Replicated Databases |
1999 |
VLDB |
0.00016595815 |
| 6,358 |
Dissecting the Performance of Strongly-Consistent Replication Protocols |
2019 |
SIGMOD |
5.0969837e-05 |
| 8,243 |
In-Network Leaderless Replication for Distributed Data Stores |
2022 |
VLDB |
4.5518393e-05 |
| 5,400 |
Replication, Consistency, and Practicality: Are These Mutually Exclusive? |
1998 |
SIGMOD |
5.5290116e-05 |
| 10,613 |
Asymmetric Linearizable Local Reads |
2025 |
VLDB |
4.1945683e-05 |