What is the L2AW theorem ?
Ideally crash-tolerant replication protocols, which are at the heart of read-intensive reliable datastores, must offer: 1) local reads (for performance), 2) linearizability (i.e., strong consistency), and 3) ensure safety under asynchrony.
However, existing crash-tolerant replication protocols provide up to two of the three above features:
1. RC protocols
May provide Asynchronous and Local Reads but can return stale values thus relax consistency.
1. LS protocols
Come with Linearizable and Local reads but cannot tolerate Asynchrony.
2. RA protocols
Ensure Linearizability under Asynchrony but have costly reads involving multiple replicas.
This hints a fundamental tradeoff between consistency, asynchrony, and performance in crash-tolerant
protocols.
Inspired by the above we introduce and prove the L2AW impossibility which asserts that: any
Linearizable Asynchronous read/write register protocol that tolerates a crash (Without
blocking reads or writes), has no Local reads.
Almost Local Reads (ALRs)
Guided by the L2AW impossibility, we introduce the idea of almost-local reads (ALRs), which can be implemented in a crash-tolerant and linearizable manner under asynchrony. ALRs inevitably have higher latency than local (single-node) reads, but they are very lightweight, with computation and network costs close to local reads.
When applied to the protocols in all three corners of the
design space (i.e., RA, RC, LS), ALRs add the missing piece:
1) they improve the throughput for RA protocols
2) ensure linearizability for RC protocols and
3) allow LS protocols to safely operate under asynchrony.
Eurosys '25 - best poster nominee 🏆
Related Projects
HERMES: a
high-performance single-key fault-tolerant and strongly consistent replication protocol.
ZEUS:
locality-aware distributed (multi-key) transactions with high performance and reliability.
License
The code and accompanied materials are freely distributed to the public under the Apache 2.0 License.