License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2019.42
URN: urn:nbn:de:0030-drops-116042
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11604/
Go to the corresponding LIPIcs Volume Portal

Gadducci, Fabio ; Melgratti, Hernán ; Roldán, Christian ; Sammartino, Matteo

A Categorical Account of Replicated Data Types

pdf-format:
LIPIcs-FSTTCS-2019-42.pdf (0.6 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{gadducci_et_al:LIPIcs:2019:11604,
  author =	{Fabio Gadducci and Hern{\'a}n Melgratti and Christian Rold{\'a}n and Matteo Sammartino},
  title =	{{A Categorical Account of Replicated Data Types}},
  booktitle =	{39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
  pages =	{42:1--42:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-131-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{150},
  editor =	{Arkadev Chattopadhyay and Paul Gastin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2019/11604},
  URN =		{urn:nbn:de:0030-drops-116042},
  doi =		{10.4230/LIPIcs.FSTTCS.2019.42},
  annote =	{Keywords: Replicated data type, Specification, Functorial characterisation}
}

Keywords: Replicated data type, Specification, Functorial characterisation
Collection: 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
Issue Date: 2019
Date of publication: 04.12.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI