Invocation-Order Concurrent Linearizability Utilizing Chain Replication With Apportioned Queries

Abstract

Linearizability is a widely used consistency model that provides predictable, easy-to-reason-about behavior for distributed systems by guaranteeing that operations follow a total order which respects real-time ordering. One limitation of linearizability is its assumption that clients only sequentially issue operations. If two operations have ordering requirements, then clients must sequentially issue them to ensure that they are executed in the desired order. This limits parallelism and puts the burden on the application developer to handle ordering requirements. Invocation-Order Concurrent Linearizability (IOCL) is a consistency model that assumes clients can issue concurrent operations and ensures that invocation order is preserved, utilizing parallelism. This thesis presents an implementation of IOCL across multiple shards on top of Chain Replication with Apportioned Queries (CRAQ), a linearizable replication protocol that offers lower wide-area read latency than consensus-based protocols like Paxos. IOCL-CRAQ was benchmarked to reduce end-to-end latency by as much as 72.8% relative to CRAQ in wide-area settings. IOCL-CRAQ is well-suited for latency-sensitive operations with ordering requirements, offering substantially lower end-to-end latency than CRAQ at the cost of reduced throughput.