Egalitarian Paxos

We introduce Egalitarian Paxos, a new distributed con-sensus algorithm that achieves three goals: (1) optimal commit latency in the wide-area when tolerating one and two failures, under realistic conditions; (2) uniform load balancing across all replicas (thus achieving high through-put); and (3) graceful performance degradation and unin-terrupted availability when replicas are slow or crash. 1 Problem Statement Distributed computing today places two main demands on replication protocols: (1) high throughput for replica-tion inside a computing cluster and (2) low latency for replication across data centers. Today’s clusters use fault-tolerant, highly available coordination engines such as Chubby [2], Boxwood [6], or ZooKeeper [5] for activi