Wed 26 Jun 2019 08:30 - 08:50 at 224AB - Systems I Chair(s): Xinyu Feng

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

pldi-2019-papers
08:30 - 09:30: PLDI Research Papers - Systems I at 224AB
Chair(s): Xinyu FengNanjing University
pldi-2019-papers08:30 - 08:50
Talk
Chao WangIRIF, Université Paris Diderot, France, Constantin EneaUniversité Paris Diderot, Suha Orhun MutluergilIRIF, France / University Paris Diderot, France / CNRS, France, Gustavo PetriArm Ltd
Media Attached
pldi-2019-papers08:50 - 09:10
Talk
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 Chicago
Media Attached
pldi-2019-papers09:10 - 09:30
Talk
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, USA
Media Attached