Multi-Dispatch Regular Sequential Serializability

Abstract

In this work, we introduce multi-dispatch, a perspective on consistency aimed at capturing correctness conditions in the face of asynchronous client interaction. In doing so, we will introduce examples of how protocols providing classical strong consistency can fail in asynchronous use cases, leading to unexpected behavior. Guided by these examples, we describe the design of RepQueue-RSS, a system that guarantees Helt et al.’s regular sequential serializability augmented with multi-dispatch. As a point of comparison, we describe an API shim for client applications using Spanner-RSS that achieves the same consistency. We find that RepQueue-RSS provides lower end-to-end latency for clients, especially under high levels of concurrency. A proof of correctness for RepQueue-RSS is also provided.