  Strictly serializable (linearizable) services appear to execute transactions
(operations) sequentially, in an order consistent with real time. This
restricts a transaction's (operation's) possible return values and in turn,
simplifies application programming. In exchange, strictly serializable
(linearizable) services perform worse than those with weaker consistency. But
switching to such services can break applications.
  This work introduces two new consistency models to ease this trade-off:
regular sequential serializability (RSS) and regular sequential consistency
(RSC). They are just as strong for applications: we prove any application
invariant that holds when using a strictly serializable (linearizable) service
also holds when using an RSS (RSC) service. Yet they relax the constraints on
services -- they allow new, better-performing designs. To demonstrate this, we
design, implement, and evaluate variants of two systems, Spanner and Gryff,
relaxing their consistency to RSS and RSC, respectively. The new variants
achieve better read-only transaction and read tail latency than their
counterparts.
