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

Distributed systems adopt weak consistency to ensure high availability and low latency, but state convergence is hard to guarantee due to conflicts. Experts carefully design replicated data types (RDTs) that resemble sequential data types and embed conflict resolution mechanisms that ensure convergence. Designing RDTs is challenging as their correctness depends on subtleties such as the ordering of concurrent operations. Currently, researchers manually verify RDTs, either by paper proofs or using proof assistants. Unfortunately, paper proofs are subject to reasoning flaws and mechanized proofs verify a formalization instead of a real-world implementation. Furthermore, writing mechanized proofs is reserved to verification experts and is extremely time-consuming. To simplify the design, implementation, and verification of RDTs, we propose VeriFx, a specialized programming language for RDTs with \emph{automated} proof capabilities. VeriFx lets programmers implement RDTs atop functional collections and express correctness properties that are verified automatically. Verified RDTs can be transpiled to mainstream languages (currently Scala and JavaScript). VeriFx provides libraries for implementing and verifying Conflict-free Replicated Data Types (CRDTs) and Operational Transformation (OT) functions. These libraries implement the general execution model of those approaches and define their correctness properties. We use the libraries to implement and verify an extensive portfolio of 51 CRDTs, 16 of which are used in industrial databases, and reproduce a study on the correctness of OT functions.

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