EPaxos*: A Simplified and Corrected Variant of Egalitarian Paxos for Distributed Consensus
By
otrack
Crusty in the right places. Worth the chew.
Summary
This academic paper presents EPaxos*, a simplified and corrected variant of Egalitarian Paxos, a leaderless distributed consensus protocol. The authors address the complexity and bugs in the original Egalitarian Paxos by developing a simpler failure-recovery algorithm with rigorous correctness proofs. The protocol generalizes Egalitarian Paxos to cover optimal failure thresholds while maintaining the key benefits of leaderless operation, including non-zero throughput with up to f crashes and fast command execution in 2 message delays under certain conditions.
Key quotes
· 5 pulledEgalitarian Paxos introduced an alternative, leaderless approach, that allows replicas to order commands collaboratively.
Not relying on a single leader allows the protocol to maintain non-zero throughput with up to f crashes of any processes out of a total of n = 2f+1.
Egalitarian Paxos has served as a foundation for many other replication protocols. But unfortunately, the protocol is very complex, ambiguously specified and suffers from nontrivial bugs.
In this paper, we present EPaxos* -- a simpler and correct variant of Egalitarian Paxos.
Our key technical contribution is a simpler failure-recovery algorithm, which we have rigorously proved correct.
You might also wanna read
Agent Memory Is Distributed State Management, Not Magic
The article argues that "agent memory" in AI systems is fundamentally just distributed state management rebranded. It draws parallels betwee
Modified Raft Consensus Protocol Enables Progress with Minority Node Participation
This article describes a modified version of the Raft consensus protocol that allows progress to be made even when fewer than a majority of
Building a Rust Multi-Paxos Engine with AI: Lessons from 130K Lines of Code
A developer shares their experience building a 130K-line Rust-based multi-Paxos consensus engine using AI coding agents over ~3 months. The
Explaining the Raft Consensus Algorithm Using "Mean Girls" Analogies
This article uses the movie "Mean Girls" as an analogy to explain the Raft Consensus Algorithm, a distributed systems protocol for ensuring
Mesh-LLM: Distributed LLM Inference System Using llama.cpp Across Multiple Machines
Mesh-LLM is a reference implementation that enables distributed inference of large language models across multiple machines by compiling lla
github.com·2mo ago
BEAM and OTP: Why Erlang's 1986 Concurrency Model Keeps Being Rediscovered
The article explores why the BEAM virtual machine and OTP (Open Telecom Platform) architecture, originally developed for Erlang in 1986, con
variantsystems.io·3mo ago