Abstract:Conflict-free replicated data types (CRDT) are replicated data types that encapsulate the mechanisms for resolving concurrent conflicts. They guarantee strong eventual consistency among replicas in distributed systems, which requires replicas that have executed the same set of updates be in the same state. However, CRDT protocols are subtle and it is difficult to ensure their correctness. This study leverages model checking to verify the correctness of CRDT protocols. Specifically, a reusable framework is proposed for modelling and verifying CRDT protocols. The framework consists of four layers, i.e., the communication layer, the interface layer, the protocol layer, and the specification layer. The communication layer models the communication among replicas and implements a variety of communication networks. The interface layer provides a uniform interface for existing CRDT protocols, including both the operation-based protocols and the state-based ones. In the protocol layer, users can choose the appropriate underlying communication network required by a specific protocol. The specification layer specifies strong eventual consistency and the eventual visibility property (i.e., all updates are eventually delivered by all replicas) that every CRDT protocol should satisfy. This framework is implemented using a formal specification language called TLA+. It is also demonstrated that how to model CRDT protocols in this framework and how to verify their correctness via the model checking tool called TLC, taking Add-Wins Set as an example.