[VLDB'25] The LAW Theorem: Local Reads and Linearizable Asynchronous Replication

The LAW theorem establishes a fundamental limit in distributed systems: no crash-tolerant protocol can provide fully local, linearizable reads under asynchrony. This work introduces Almost-Local Reads (ALRs)—a lightweight mechanism that achieves near-local read performance while preserving linearizability and fault tolerance. By enhancing protocols like Raft, ZAB, and Hermes, ALRs deliver substantial throughput gains and scalability with minimal latency overhead. The paper bridges theory and practice, redefining the boundaries of consistency, performance, and time assumptions in replicated datastores.

1. The LAW Theorem Local Reads and Linearizable Asynchronous Replication VLDB '25 | EuroSys '25 - Best Poster Nominee 🏆 Research Track — Distributed Transactions II A. Katsarakis* † , E. Gioratmis* ♣ , V. Gavrielatos † , P. Bhatotia ♣ , A. Dragojevic ♦ , B. Grot ♠ , V. Nagarajan ♠ , P. Fatourou ♥ † Huawei Research, ♣ TU Munich, ♦ OpenAI, ♠ University of Edinburgh, ♥ University of Crete and FORTH, *Equal contribution

2. Such as KV Stores, Caches, Coordination services offer i n-memory with read/write API Backbone of online services and DBMSes Characterized by Numerous concurrent requests Read-intensive workloads Need for data reliability run on fault-prone HW with unpredictable delays Distributed datastores 2 Distributed Datastore W hat should the ideal datastore look like?

3. Should offer Crash-tolerance : via replicated data High performance : especially for reads Strong consistency under asynchrony safe — even when timeouts do n o t hold Crash-tolerant Replication Protocols Tolerate crashes without blocking by determining actions to execute reads and writes Ideal protocol features Local Reads reads complete on a single replica — no inter-replica exchanges Linearizability reads/writes appear to occur instantaneously—as if a single copy Asynchrony correct in real-world deployments , even with unpredictable delays Ideal Reliable Datastore: Performant, Consistent, & Asynchronous 3 Do state-of-the-art protocols offer the 3 desired features? … … … … Crash-tolerant Replication Protocol Local reads from replicas Remote reads

4. Crash-tolerant Protocols: state-of-the-art offers 2 of 3! 4 RA protocols: e.g. Raft, Paxos, ABD   - R emote (costly) reads + A synchronous + Linearizable LS protocols: e.g. Hermes, CRAQ  + L ocal reads  - S ynchronous + Linearizable RC protocols: e.g. ZAB + Local reads + Asynchronous - R elaxed C onsistency Existing protocols up to 2 of 3! H int s to a fundamental trade-off…

5. Unveiling the L 2 AW Theorem: The impossibility Inspired by this observed trade-off, we formally define and prove the L 2 AW Impossibility Theorem . I ntuition In an asynchronous system, a replica cannot reliably distinguish between a crashed replica and a merely slow one. For linearizability, a read must reflect the latest writes, which needs coordination. Local reads bypass this, risking stale data. Differences with CAP theorem - L 2 AW [crash-tolerance] vs. CAP [net. partition-tolerance] + In L 2 AW performance is a first-class citizen. - CAP: choose between consistency and availability when a network partition occurs. - L 2 AW: is stricter, not even a single local read with linearizability and asynchrony, even before any crashes occur. The LAW Theorem Any L inearizable A synchronous read/write register implementation that tolerates a crash ( W ithout blocking reads or writes), has no L ocal reads ! Does that mean we cannot improve state-of-the-art? More in our Paper/Poster

6. The “Key Question”: Can we do better? If local reads are impossible under asynchrony & linearizability… Can we improve read performance without compromis ing safety ? Insight The LAW trade-off affects latency but not necessarily throughput of reads. Asynchronous linearizable reads need not be as costly as in RA protocols where each and every read costs (network and) compute on remote replicas. But how to make reads much cheaper without sacrificing asynchrony + linearizability?

7. Almost Local Reads (ALRs) a novel batch-based abstraction with a twist that games this impossibility Key Idea One lightweight remote sync operation to complete a batch of otherwise locally executed reads . The cost of sync is independent of the batch size and contents! Outcome Inevitably (sync) latency to reach other replicas. But low throughput cost — computation & network cost close to local (no messages/processing per read). Enter Almost-local Reads (ALRs): The breakthrough Unlike typical batching, ALR batches = low constant cost to remote replicas ! The only remote op. + low constant cost

8. ALRs: Adding the Missing Piece 8 RA protocols: e.g. Raft, Paxos, ABD   - R emote (costly) reads + A synchronous + Linearizable ALRs: boost Throughput of RA protocols > By enabling low-cost reads from all replicas, drastically boost performance & scalability. RC protocols: e.g. ZAB + Local reads + Asynchronous - R elaxed C onsistency ALRs: Linearizability for RC protocols > By upgrading their consistency from sequential to linearizable without sacrificing throughput. LS protocols: e.g. Hermes, CRAQ  + L ocal reads  - S ynchronous + Linearizable ALRs: safe under Asynchrony LS protocols > By removing their dependency on time-based leases and synchronous assumptions. ALRs add the missing piece to protocols in all three corners of design space ! But how?

9. How ALRs Work: Eager & Lazy Schemes Eager-ALRs (for LS Protocols e.g., Hermes) Key characteristic : typically rely on a replica configuration protected by a lease, ensur ing that a replica holding a lease will observe a write before it complete s . In this protocol family we eliminate time-based leases by: Form ALR batch + eagerly execute local reads ; optimistically buffer results – assume replica still in configuration Issue sync : to validate same configuration (i.e., contains replica) If (same config) return buffered values; replica saw all updates until sync else typical_recovery (); Lazy-ALRs (for RC/RA Protocols e.g., ZAB, Raft) Key characteristic : here most protocols follow the state machine replication , --> all writes are serialized and are applied in the same order to all replicas . We upgrade consistency or boost throughput of SMR-based protocols by: Form ALR batch + Issue Sync : a ‘fake’ write that does not alter state but executes the write algorithm. Wait until sync is about to be “applied locally” at this point all writes preceding the ALR batch are seen by replica. Lazily execute local reads of the ALR batch as they will now be linearizable.

10. Latency & Throughput Optimizations of ALRs ALRs leverage opportunistic batching to not affect latency! Never wait for a specific batch size, forms batches from currently queued reads. L atency not affected on light load + max throughput when needed (heavy load). Timely writes as zero-cost syncs to maximize throughput! After forming an (eager or lazy) ALR-batch i f a replica is about to issue a write, that ( timely ) write serves as a sync proxy for the ALR batch. In such common scenario , an ALR s needs no explicit sync; hence they incurs zero extra network or computation cost on remote replicas. Awesome but how do ALRs perform in practice?

11. ALRs in Practice: Evaluation Highlights Evaluated ALR-enhanced variants of state-of-the-art protocols: Hermes-ALR (LS), ZAB-ALR (RC), Raft-ALR (RA). Fair ness : fastest baselines that already heavily exploit traditional batching for performance. Hermes-ALR: low-cost Asynchrony for LS protocol Tolerates asynchrony with min. throughput cost (5% @ 95% reads). Gap shrinks further with more writes — due to zero-cost syncs. ZAB-ALR: Stronger consistency, same performance Upgrades ZAB to linearizability, negligible throughput cost (2% @ 95% reads). Zero-cost syncs, deliver same performance as soon as 10% writes. Raft-ALR: Unlocks efficient multi-replica reads Significantly higher throughput almost 2x at 5% writes. Scales throughput with more replicas, unlike vanilla Raft. Fantastic! Let’s summarize … + 2x perf + Linearizable + Asynchronous

12. Summary State-of-the-art crash-tolerant protocols: 2 out of 3! 1. Linearizability 2. Asynchrony 3. Local Reads We proved the L 2 AW impossibility Linearizable & Asynchronous crash-tolerant protocols have no Local reads! Introduced ( eager & lazy ) Almost Local Reads ( ALRs ) to game it Improve protocols in any of 3 design space corners ALRs exploit opportunistic batching & zero-cost syncs to keep low latency and maximize throughput Raft-ALR (RA): much higher throughput and improved scalability Hermes- (LS) & ZAB-ALR (RC): about as high throughput + linearizability under asynchrony Thank you! Questions? More at law- theorem.com

13. Backup Slides 13

14. How ALRs Work: Eager & Lazy Schemes Eager-ALRs (for LS Protocols e.g., Hermes) Key characteristic : typically rely on a configuration protected by a lease, ensur ing that a replica holding a lease will observe all writes (before they complete). Read locally optimistically, then perform a sync to validate the consistency of the configuration . Ensures linearizability by confirming the replica received all completed writes up until the sync and hence after the local read. Eliminates reliance on time-based leases synchrony Lazy-ALRs (for RC/RA Protocols e.g., ZAB, Raft) Key characteristic : most protocols follow the state machine replication model, --> all writes are serialized and applied in the same order to all replicas . Issue a lightweight ‘fake’ write (sync) that does not alter state but executes the write algorithm. Once the sync is “applied locally”, it ensures that all prior writes are seen, ensuring that subsequent local reads are linearizable. Key benefits: Upgrades consistency for RC protocols or boosts throughput by enabling cost-efficient reads from all replicas in RA protocols.

15. How ALRs Work: Eager & Lazy Schemes Eager-ALRs (for LS Protocols e.g., Hermes) Key characteristic : typically rely on a configuration protected by a lease, ensur ing that a replica holding a lease will observe all writes (before they complete). Read locally optimistically, then perform a sync to validate the consistency of the configuration . Ensures linearizability by confirming the replica received all completed writes up until the sync and hence after the local read. Eliminates reliance on time-based leases synchrony Lazy-ALRs (for RC/RA Protocols e.g., ZAB, Raft) Key characteristic : most protocols follow the state machine replication model, --> all writes are serialized and applied in the same order to all replicas . Issue a lightweight ‘fake’ write (sync) that does not alter state but executes the write algorithm. Once the sync is “applied locally”, it ensures that all prior writes are seen, ensuring that subsequent local reads are linearizable. Key benefits: Upgrades consistency for RC protocols or boosts throughput by enabling cost-efficient reads from all replicas in RA protocols.

16. ALRs: Adding the Missing Piece 16 RC protocols: e.g. ZAB + Local reads + Asynchronous - R elaxed C onsistency LS protocols: e.g. Hermes, CRAQ  + L ocal reads  - S ynchronous + Linearizable RA protocols: e.g. Raft, Paxos, ABD   - R emote (costly) reads + A synchronous + Linearizable ALRs: boost Throughput of RA protocols > By enabling low-cost reads from all replicas, drastically boost performance & scalability. ALRs: safe under Asynchrony LS protocols > By removing their dependency on time-based leases and synchronous assumptions. ALRs: Linearizability for RC protocols > By upgrading their consistency from sequential to linearizable without sacrificing throughput. ALRs add the missing piece to protocols falling into all three corners of design space Almost-Local Reads