Although the idea of exploiting commutativity for 1 RTT replication generally works well within a
datacenter, it doesn’t work as well in wide-area networking environments. High network delays make
it more difficult to exploit commutativity since they increase the window of time during which
operations can conflict with each other. Those conflicting operations must take the standard 2-RTT
slow path.
We mitigated this problem with a technique called Timestamp-Ordered Queueing (TOQ). With the
observation that conflicts occur primarily because different replicas process operations at
different times, we modified EPaxos to use synchronized clocks to ensure that all quorum replicas
process a given operation at the same time. This reduces conflict rates by as much as 50% without
introducing any additional latency.
