Team Members: Majd Nasra, Kenny Oseleononmen
Original Authors: Sarah Tollman, Seo Jin Park, and John Ousterhout
Abstract
This report replicates the findings of the paper “EPaxos Revisited” by Sarah Tollman, Seo Jin Park, and John Ousterhout. The original paper critically examines the performance of the EPaxos consensus protocol. Our reproduction aims to verify their claims, focusing on performance metrics under varying conflict conditions and the practical applicability of EPaxos in geo-replicated environments.
Introduction
Paxos is a consensus algorithm for fault tolerance in distributed systems. The paper “EPaxos Revisited” reevaluates the performance of the Egalitarian Paxos (EPaxos) protocol, originally designed to minimize latency in geo-replicated systems by leveraging operation commutativity. The authors reveal that EPaxos exhibits significantly worse tail latency under high-conflict scenarios than previously reported, challenging its practical applicability. They also propose Timestamp-Ordered Queuing (TOQ) to reduce conflicts and improve latency. This report aims to replicate their performance reevaluation using a comprehensive benchmarking framework.
Selected Claim and Motivation
We chose to replicate Figure 7 from “EPaxos Revisited” due to its comprehensive comparison of execution latency between EPaxos and Multi-Paxos across different workloads. This figure illustrates the trade-offs in mean and 99th percentile latency, revealing that EPaxos’s claimed latency benefits do not hold under high-conflict scenarios.
Methodology
Evaluation Configurations
The original and new evaluation configurations are summarized in the following table:
| Metric | Original Evaluation | New Evaluation |
|---|---|---|
| Latency Metric | Commit (median) | Execution (mean) |
| Interfering Keys | “Hot Key” | Zipfian distribution |
| Operation Type | All writes | Reads + Writes |
| Access Patterns | 3 “Hot Key” Fractions | Grid with 99 configurations |
| Loads | ~4-5% max throughput | ~80% max throughput |
| Operation Schedule | Back-To-Back | Poisson + Cap |
| Configuration | LAN | WAN |
The methodology involved evaluating both execution and commit latency of EPaxos under various workloads to understand its performance characteristics comprehensively. By including measurements under a Zipfian access pattern and across a grid of Zipfian skew and read-write ratio choices, the researchers aimed to capture the full range of conflict behaviors likely to be encountered in real-world applications. The experiments were conducted at 80% of the maximum throughput to simulate realistic load conditions, providing insights into how EPaxos performs under different workload characteristics and conflict rates. This approach ensured a detailed and nuanced evaluation of EPaxos, highlighting its strengths and limitations in various scenarios. We used the same exact methodology.
Experimental Setup
Our replication used Google Cloud servers across various regions, with n1-standard-8 machine types running Ubuntu 18.04.5 LTS. We implemented the enhanced benchmarking framework and used Pulumi to spin up the VMs in the same locations. The experiments were run over a grid of 9 different Zipfian skew values and 10 read-write ratio choices, maintaining throughput at 80% of the maximum for consistency.
Our Multi-Paxos reproduction of the code fails by not resulting in any responses from the three servers we made, except for very low skew and low write percentage. We will include the relative plots (Figure 7 replication). However, our EPaxos reproduction using the new harness resulted in responses from the servers, but this data will only be useful when compared to the Multi-Paxos data.
From our results above, we notice that the P99 latency in the OR EPaxos is worse than MPaxos as the Zipfian skew increases. This gives us a small hint about the relative latencies the graph will have with more skew and higher write percentages. Unfortunately, we weren’t able to get Multi-Paxos to fully be responsive in those cases.
Discussion
Replicating the experiments highlighted the sensitivity of EPaxos’s performance to conflict rates and network conditions. We believe the results will reinforce the importance of considering conflict and dependency management in consensus protocol design, however due to the irresponsiveness of the servers to MPaxos, we weren’t able to compare and contrast.
Conclusion
We expect our reproduction to validate the key findings of “EPaxos Revisited,” demonstrating that EPaxos’s latency benefits are limited under high-conflict scenarios. The insights gained from this replication can guide more informed decisions in the design and deployment of distributed systems.
References
- Sarah Tollman, Seo Jin Park, and John Ousterhout. “EPaxos Revisited.” In Proceedings of the 2021 USENIX Annual Technical Conference (ATC ’21).
- The implementation of our code is available in the following GitHub repository: https://github.com/Kenny1G/epaxos_revisited_replicated.git
Reproducing Network Research 