Just Say NO to Paxos Overhead: Replacing Consensus with Network Ordering

Distributed applications use replication, implemented by protocols like Paxos, to ensure data availability and transparently mask server failures. This paper presents a new approach to achieving replication in the data center without the performance cost. Our work carefully divides the responsibility between the network layer and replication protocol. The network is responsible for ordering requests but not ensuring reliable delivery – which we formalize as a new ordered unreliable multicast (OUM) model and show can be achieved with near-zero-cost in the data center. This guarantee enables our new replication protocol, Network-Ordered Paxos (NOPaxos), which exploits network ordering to provide strongly consistent replication without coordination. The resulting system not only simultaneously outperforms both latency- and throughput-optimized protocols on their respective metrics, it also provides throughput within 2% and latency within 16 us of an unreplicated system – providing replication without the performance cost.