  Traditional approaches to replication require client requests to be ordered
before making them durable by copying them to replicas. As a result, clients
must wait for two round-trip times (RTTs) before updates complete. In this
paper, we show that this entanglement of ordering and durability is unnecessary
for strong consistency. Consistent Unordered Replication Protocol (CURP) allows
clients to replicate requests that have not yet been ordered, as long as they
are commutative. This strategy allows most operations to complete in 1 RTT (the
same as an unreplicated system). We implemented CURP in the Redis and RAMCloud
storage systems. In RAMCloud, CURP improved write latency by ~2x (13.8 us ->
7.3 us) and write throughput by 4x. Compared to unreplicated RAMCloud, CURP's
latency overhead for 3-way replication is just 0.4 us (6.9 us vs 7.3 us). CURP
transformed a non-durable Redis cache into a consistent and durable storage
system with only a small performance overhead.
