George Zakhour
Thumbnail Image
Last Name
Zakhour
First name
George
Email
george.zakhour@unisg.ch
ORCID

Filters

1
1
Reset filters

Settings
Now showing 1 - 1 of 1
  • Publication
    Type-Checking CRDT Convergence
    ( 2023-06-06)
    George Zakhour orcid-logo
    ;
    Pascal Weisenburger orcid-logo
    ;
    Guido Salvaneschi
    Conflict-Free Replicated Data Types (CRDTs) are a recent approach for keeping replicated data consistent while guaranteeing the absence of conflicts among replicas. For correct operation, CRDTs rely on a merge function that is commutative, associative and idempotent. Ensuring that such algebraic properties are satisfied by implementations, however, is left to the programmer, resulting in a process that is complex and error-prone. While techniques based on testing, automatic verification of a model, and mechanized or handwritten proofs are available, we lack an approach that is able to verify such properties on concrete CRDT implementations. In this paper, we present Propel, a programming language with a type system that captures the algebraic properties required by a correct CRDT implementation. The Propel type system deduces such properties by case analysis and induction: sum types guide the case analysis and algebraic properties in function types enable induction for free. Propel’s key feature is its capacity to reason about algebraic properties (a) in terms of rewrite rules and (b) to derive the equality or inequality of expressions from the properties. We provide an implementation of Propel as a Scala embedding, we implement several CRDTs, verify them with Propel and compare the verification process with four state-of-the-art verification tools. Our evaluation shows that Propel is able to automatically deduce the properties that are relevant for common CRDT implementations found in open-source libraries even in cases in which competitors timeout.
    Type: conference paper
    Journal: Proceedings of the ACM on Programming Languages
    Volume: 7
    Issue: PLDI
    URL: https://programming-group.com/assets/pdf/papers/2023_Type-Checking-CRDT-Convergence.pdf
    DOI: 10.1145/3591276
    URI: https://www.alexandria.unisg.ch/handle/20.500.14171/117437
    Scopus© Citations 4