Distributed systems often replicate data at multiple locations to achieve availability and performance despite network partitions. These systems accept updates at any replica and propagate them asynchronously to every other replica. Conflict-Free Replicated Data Types (CRDTs) provide a principled approach to the problem of ensuring that replicas are eventually consistent despite the asynchronous delivery of updates.
We address the problem of specifying and verifying CRDTs, introducing a new correctness criterion called Replication-Aware Linearizability. This criterion is inspired by linearizability, the de-facto correctness criterion for (shared-memory) concurrent data structures. We argue that this criterion is both simple to understand, and it fits most known implementations of CRDTs. We provide a proof methodology to show that a CRDT satisfies replication-aware linearizability that we apply on a wide range of implementations. Finally, we show that our criterion can be leveraged to reason modularly about the composition of CRDTs.
Wed 26 Jun
|08:30 - 08:50|
Chao WangIRIF, Université Paris Diderot, France, Constantin EneaUniversité Paris Diderot, Suha Orhun MutluergilIRIF, France / University Paris Diderot, France / CNRS, France, Gustavo PetriArm LtdMedia Attached
|08:50 - 09:10|
Guangpu LiUniversity of Chicago, USA, Haopeng LiuUniversity of Chicago, Xianglan ChenUniversity of Science and Technology of China, China, Haryadi S. GunawiUniversity of Chicago, USA, Shan LuUniversity of ChicagoMedia Attached
|09:10 - 09:30|
Nikos VasilakisUniversity of Pennsylvania, USA, Ben KarelUniversity of Pennsylvania, USA, Yash PalkhiwalaUniversity of Pennsylvania, USA, John SonchackUniversity of Pennsylvania, USA, André DeHonUniversity of Pennsylvania, USA, Jonathan M. SmithUniversity of Pennsylvania, USAMedia Attached