Wed 19 Jul 2023 14:00 - 14:15 at Amazon Auditorium (Gates G20) - ECOOP 2: Replication Chair(s): Eric Jul

Conflict-free Replicated Datatypes (CRDTs) are a class of distributed data structures that are highly-available and weakly consistent. The CRDT taxonomy is further divided into two subclasses: state-based and operation-based (op-based). Recent prior work showed how to use separation logic to verify convergence and functional correctness of op-based CRDTs while (a) verifying implementations (as opposed to high-level protocols), (b) giving high level specifications that abstract from low-level implementation details, and (c) providing specifications that are modular (i.e. allow client code to use the CRDT like an abstract data type). We extend this separation logic approach to verification of CRDTs to handle state-based CRDTS, while respecting the desiderata (a)–(c). The key idea is to track the state of a CRDT as a function of the set of operations that produced that state. Using the observation that state-based CRDTs are automatically causally-consistent, we obtain CRDT specifications that are agnostic to whether a CRDT is state- or op-based. We have tested our approach by verifying StateLib, a library for building state-based CRDTs. Using StateLib, we have further verified convergence and functional correctness of multiple example CRDTs from the literature. Our proofs are written in the Aneris distributed separation logic and are mechanized in Coq.

Wed 19 Jul

Displayed time zone: Pacific Time (US & Canada) change

13:30 - 15:00
ECOOP 2: ReplicationResearch Papers at Amazon Auditorium (Gates G20)
Chair(s): Eric Jul University of Oslo
13:30
15m
Talk
Behavioural Types for Local-First Software
Research Papers
Roland Kuhn Actyx AG, Hernan Melgratti University of Buenos Aires, Argentina, Emilio Tuosto Gran Sasso Science Institute, L'Aquila, Italy
DOI
13:45
15m
Talk
Algebraic Replicated Data Types: Programming Secure Local-First Software
Research Papers
Christian Kuessner Technische Universität Darmstadt, Ragnar Mogk Technische Universität Darmstadt, Anna-Katharina Wickert TU Darmstadt, Germany, Mira Mezini TU Darmstadt
DOI Pre-print
14:00
15m
Talk
Modular Verification of State-Based CRDTs in Separation Logic
Research Papers
Abel Nieto Aarhus University, Arnaud Daby-Seesaram ENS Paris Saclay, Léon Gondelman Aarhus University, Amin Timany Aarhus University, Lars Birkedal Aarhus University
DOI
14:15
15m
Talk
VeriFx: Correct Replicated Data Types for the Masses
Research Papers
Kevin De Porre Vrije Universiteit Brussel, Carla Ferreira NOVA University Lisbon, Elisa Gonzalez Boix Vrije Universiteit Brussel
DOI
14:30
15m
Talk
Nested Pure Operation-Based CRDTs
Research Papers
Jim Bauwens Vrije Universiteit Brussel, Elisa Gonzalez Boix Vrije Universiteit Brussel
DOI
14:45
15m
Talk
LoRe: A Programming Model for Verifiably Safe Local-First Software
Research Papers
Julian Haas Technische Universität Darmstadt, Ragnar Mogk Technische Universität Darmstadt, Elena Yanakieva University of Kaiserslautern-Landau, Annette Bieniusa Kaiserslautern, Mira Mezini TU Darmstadt
DOI Pre-print