  This experience report presents the results of an extensive performance
evaluation conducted using four open-source implementations of Paxos deployed
in Amazon's EC2. Paxos is a fundamental algorithm for building fault-tolerant
services, at the core of state-machine replication. Implementations of Paxos
are currently used in many prototypes and production systems in both academia
and industry. Although all protocols surveyed in the paper implement Paxos,
they are optimized in a number of different ways, resulting in very different
behavior, as we show in the paper. We have considered a variety of
configurations and failure-free and faulty executions. In addition to reporting
our findings, we propose and assess additional optimizations to existing
implementations.
