2026-07-27T00:38:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11604 2024-03-06T10:48:25Z ddc:004 open_access

A Categorical Account of Replicated Data Types Gadducci, Fabio Melgratti, Hernán Roldán, Christian Sammartino, Matteo Replicated data type Specification Functorial characterisation Replicated Data Types (RDTs) have been introduced as a suitable abstraction for dealing with weakly consistent data stores, which may (temporarily) expose multiple, inconsistent views of their state. In the literature, RDTs are commonly specified in terms of two relations: visibility, which accounts for the different views that a store may have, and arbitration, which states the logical order imposed on the operations executed over the store. Different flavours, e.g., operational, axiomatic and functional, have recently been proposed for the specification of RDTs. In this work, we propose an algebraic characterisation of RDT specifications. We define categories of visibility relations and arbitrations, show the existence of relevant limits and colimits, and characterize RDT specifications as functors between such categories that preserve these additional structures. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Fabio Gadducci and Hernán Melgratti and Christian Roldán and Matteo Sammartino 2019 Is Part Of LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2019.42 urn:nbn:de:0030-drops-116042 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.42 eng https://creativecommons.org/licenses/by/3.0/legalcode