EPaxos Revisited
summary
Re-evaluation reproduces EPaxos’s low median commit latency but shows 99th-percentile latency often worse than Multi‑Paxos — sometimes more than 4× worse — and conflict rates varying from 0–35% across 99 access patterns measured at ~80% throughput using a zipfian key distribution. A clock-based technique called Timestamp Ordered Queuing (TOQ) delays processing to align deliveries, cutting conflicts 50–100% (quorum sync) and reducing mean latency up to 7.5% while full-sync eliminates conflicts at prohibitive best‑case latency cost; execution delay is bounded to ~3 WAN RTTs.
AI-written summary · about
chapters (16)
- 0:00Intro
- 0:24Overview
- 2:00Traditional Consensus (e.g. Multi-Paxos)
- 2:35Egalitarian Paxos (EPaxos)
- 3:31Dependencies & Conflicts
- 4:24EPaxos Commit: Different From MPaxos
- 5:09Execution
- 5:39New EPaxos Benchmarking Strategy
- 7:26EPaxos Evaluation
- 8:31Reducing Conflicts
- 8:50TOQ Intuition
- 9:32Timestamp-Ordered Queueing (TOQ)
- 9:56Fully Consistent TOQ Increases Latency
- 10:20TOQ Sync Groups: Conflict vs. Latency Trade-off
- 10:41TOQ Results
- 11:42Conclusion
related talks
17mNear Optimal Latency Versus Cost Tradeoffs in Geo Distributed Storage
22mLiberating Distributed Consensus
16mSwiftPaxos: Fast Geo-Replicated State Machines
20mHigh Throughput Replication with Integrated Membership Management
19mPineapple: Unifying Multi-Paxos and Atomic Shared Registers
28mRock around the clock (synchronization
01h 14mThe hitchhiker's guide to distributed transactions
48mDistributed Consensus Algorithms