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
- 13925
- Venue
- VLDB
- Year
- 2025
- Pagerank
- 5.4598872e-05
- Overall Rank
- 8,609 | 40.17%
- 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 |
| 46 |
PNUTS: Yahoo!'s Hosted Data Serving Platform |
2008 |
VLDB |
0.0004507937 |
| 57 |
Calvin: Fast Distributed Transactions for Partitioned Database Systems |
2012 |
SIGMOD |
0.00040347584 |
| 142 |
Megastore: Providing Scalable, Highly Available Storage for Interactive Services |
2011 |
CIDR |
0.00029935122 |
| 219 |
CockroachDB: The Resilient Geo-Distributed SQL Database |
2020 |
SIGMOD |
0.00024561689 |
| 301 |
TiDB: A Raft-based HTAP Database |
2020 |
VLDB |
0.00022033345 |
| 391 |
Impossibility of Distributed Consensus with One Faulty Process |
1983 |
PODS |
0.00019465133 |
| 618 |
F1: A Distributed SQL Database That Scales |
2013 |
VLDB |
0.00015831882 |
| 866 |
Coordination Avoidance in Database Systems |
2015 |
VLDB |
0.00013563685 |
| 1,233 |
Don't be lazy, be consistent: Postgres-R, A new way to implement Database Replication |
2000 |
VLDB |
0.00011656801 |
| 1,560 |
F1 – The Fault-Tolerant Distributed RDBMS Supporting Google's Ad Business |
2012 |
SIGMOD |
0.00010405267 |
| 1,943 |
Scalable Atomic Visibility with RAMP Transactions |
2014 |
SIGMOD |
9.5199832e-05 |
| 2,809 |
Rose: Compressed, log-structured replication |
2008 |
VLDB |
8.154373e-05 |
| 3,594 |
Harmonia: Near-Linear Scalability for Replicated Storage with In-Network Conflict Detection |
2020 |
VLDB |
7.3371595e-05 |
| 4,456 |
Tunable Consistency in MongoDB |
2019 |
VLDB |
6.7490937e-05 |
| 4,947 |
TAOBench: An End-to-End Benchmark for Social Network Workloads |
2022 |
VLDB |
6.4972552e-05 |
| 7,952 |
LEGOStore: A Linearizable Geo-Distributed Store Combining Replication and Erasure Coding |
2022 |
VLDB |
5.5744541e-05 |
| 8,105 |
In-Network Leaderless Replication for Distributed Data Stores |
2022 |
VLDB |
5.5441367e-05 |
| 9,586 |
A Byzantine Fault Tolerant Storage for Permissioned Blockchain |
2021 |
SIGMOD |
5.3090219e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 4,953 |
Strong consistency is not hard to get: Two-Phase Locking and Two-Phase Commit on Thousands of Cores |
2019 |
VLDB |
6.4958709e-05 |
| 10,092 |
LSM-Raft: Optimizing Raft for LSM-tree Store |
2026 |
SIGMOD |
5.1725247e-05 |
| 12,913 |
A Tight Upper Bound on the Benefits of Replication and Consistency Control Protocols |
1991 |
PODS |
5.1725247e-05 |
| 4,217 |
Causal Consistency and Latency Optimality: Friend or Foe? |
2018 |
VLDB |
6.8885386e-05 |
| 6,078 |
Replication and Consistency: Being Lazy Helps Sometimes |
1997 |
PODS |
6.0474672e-05 |
| 1,137 |
Fast Algorithms for Maintaining Replica Consistency in Lazy Master Replicated Databases |
1999 |
VLDB |
0.00012105424 |
| 6,209 |
Dissecting the Performance of Strongly-Consistent Replication Protocols |
2019 |
SIGMOD |
6.014154e-05 |
| 8,105 |
In-Network Leaderless Replication for Distributed Data Stores |
2022 |
VLDB |
5.5441367e-05 |
| 5,826 |
Replication, Consistency, and Practicality: Are These Mutually Exclusive? |
1998 |
SIGMOD |
6.1351137e-05 |
| 10,621 |
Asymmetric Linearizable Local Reads |
2025 |
VLDB |
5.1725247e-05 |