Contract-based return-value commutativity: safely exploiting contract-based commutativity for faster serializable transactions

A key challenge of designing distributed software systems is maintaining data consistency. We can define data consistency and data isolation guarantees --e.g. serializability-- in terms of schedules of atomic reads and writes, but this excludes schedules that would be semantically consistent. Others use manually provided information on "non-conflicting operations" to define guarantees that work for more applications allowing more parallel schedules. To be safe, an engineer might avoid marking operations as non-conflicting, with detrimental effects to efficiency. To be fast, they might mark more non-conflicting operations than is strictly safe.

Our goal is to help engineers by automatically deriving commutative operations (using their respective contracts) such that more parallel schedules with global consistency are possible. We define a new general consistency and isolation guarantee named "Return-Value Serializability" to check consistency claims automatically, and we present distributed event processing algorithms that make use of the same "Contract-based Commutativity" information. We validated both the definitions and the algorithms using model-checking with TLA+. Previous work provided evidence that local coordination avoidance such as applied here has a significant positive effect on the performance of distributed transaction systems.

Client-centric return-value commutativity promises to hit a sweet spot in design trade-offs for business applications, such as payment systems, that must scale-out while their operations are not embarrassingly parallel and consistency guarantees are of the highest priority. It can also provide design feedback, indicating that some operations will simply not scale together even before a line of code has been written.