This paper introduces Natto, a geo-distributed database system that supports transaction prioritization. Instead of having each shard process transactions in their arrival order, Natto leverages network measurements to estimate the transaction arrival time at each shard, and assigns a timestamp to the transaction based on its arrival time to the furthest shard. These timestamps establish a global ordering of transactions, and introduces opportunities to selectively abort pending low-priority transactions that conflict with a high-priority transaction, or even preempt transactions that are already partially prepared. Our experiments on both Microsoft Azure and a local cluster show that Natto's tail latency for high-priority transactions are significantly lower than the tail latencies of Carousel and TAPIR, which are the current state-of-the-art in geo-distributed transaction processing systems.

This paper introduces Domino, a low-latency state machine replication protocol for wide-area networks. Domino uses network measurements to predict the expected arrival time of a client request to each of its replicas, and assigns a future timestamp to the request indicating when the last replica from the supermajority quorum should have received the request. With accurate arrival time predictions and in the absence of failures, Domino can always commit a request in a single network roundtrip using a Fast Paxos-like protocol by ordering the requests based on their timestamps.

The trend towards global applications and services has created an increasing demand for transaction processing on globally-distributed data. Many database systems, such as Spanner and CockroachDB, support distributed transactions but require a large number of wide-area network roundtrips to commit each transaction and ensure the transaction's state is durably replicated across multiple datacenters. This can significantly increase transaction completion time, resulting in developers replacing database-level transactions with their own error-prone application-level solutions.