On the semantics and implementation of replicated data types

Replicated data types (RDTs) concern the specification and implementation of data structures handled by replicated data stores, i.e., distributed data stores that maintain copies of the same data item on multiple devices. A distinctive feature of RDTs is that the behaviour of an operation depends on...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Gadducci, F., Melgratti, H., Roldán, C.
Formato:	JOUR
Materias:	Implementation correctness Replicated data types Specification Mapping Semantics Visibility Distributed data stores Function mapping Multiple devices Replicated data Simulation relation Total order Underspecification Specifications
Acceso en línea:	http://hdl.handle.net/20.500.12110/paper_01676423_v167_n_p91_Gadducci
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	todo:paper_01676423_v167_n_p91_Gadducci
record_format	dspace
spelling	todo:paper_01676423_v167_n_p91_Gadducci2023-10-03T15:05:01Z On the semantics and implementation of replicated data types Gadducci, F. Melgratti, H. Roldán, C. Implementation correctness Replicated data types Specification Mapping Semantics Visibility Distributed data stores Function mapping Implementation correctness Multiple devices Replicated data Simulation relation Total order Underspecification Specifications Replicated data types (RDTs) concern the specification and implementation of data structures handled by replicated data stores, i.e., distributed data stores that maintain copies of the same data item on multiple devices. A distinctive feature of RDTs is that the behaviour of an operation depends on the state of the replica over which it performs, and hence, its result may differ from replica to replica. Abstractly, RDTs are specified in terms of two relations, visibility and arbitration. The former establishes whether an operation observes the effects of the execution of another operation, the latter is a total order on operations used to resolve conflicts between operations executed concurrently over different replicas. Traditionally, an operation of an RDT is specified as a function mapping a visibility and an arbitration into the expected result of the operation. This paper recasts such standard approaches into a denotational framework in which a data type is a function mapping visibility into admissible arbitrations. This characterisation provides a more abstract view of RDTs that (i) highlights some implicit assumptions shared in operational approaches to specification; (ii) accommodates underspecification and refinement; (iii) enables a direct characterisation of the correct implementations of an RDT in terms of a simulation relation between the states of a concrete implementation and of the abstract one determined by the specification. © 2018 JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_01676423_v167_n_p91_Gadducci
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-134
collection	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic	Implementation correctness Replicated data types Specification Mapping Semantics Visibility Distributed data stores Function mapping Implementation correctness Multiple devices Replicated data Simulation relation Total order Underspecification Specifications
spellingShingle	Implementation correctness Replicated data types Specification Mapping Semantics Visibility Distributed data stores Function mapping Implementation correctness Multiple devices Replicated data Simulation relation Total order Underspecification Specifications Gadducci, F. Melgratti, H. Roldán, C. On the semantics and implementation of replicated data types
topic_facet	Implementation correctness Replicated data types Specification Mapping Semantics Visibility Distributed data stores Function mapping Implementation correctness Multiple devices Replicated data Simulation relation Total order Underspecification Specifications
description	Replicated data types (RDTs) concern the specification and implementation of data structures handled by replicated data stores, i.e., distributed data stores that maintain copies of the same data item on multiple devices. A distinctive feature of RDTs is that the behaviour of an operation depends on the state of the replica over which it performs, and hence, its result may differ from replica to replica. Abstractly, RDTs are specified in terms of two relations, visibility and arbitration. The former establishes whether an operation observes the effects of the execution of another operation, the latter is a total order on operations used to resolve conflicts between operations executed concurrently over different replicas. Traditionally, an operation of an RDT is specified as a function mapping a visibility and an arbitration into the expected result of the operation. This paper recasts such standard approaches into a denotational framework in which a data type is a function mapping visibility into admissible arbitrations. This characterisation provides a more abstract view of RDTs that (i) highlights some implicit assumptions shared in operational approaches to specification; (ii) accommodates underspecification and refinement; (iii) enables a direct characterisation of the correct implementations of an RDT in terms of a simulation relation between the states of a concrete implementation and of the abstract one determined by the specification. © 2018
format	JOUR
author	Gadducci, F. Melgratti, H. Roldán, C.
author_facet	Gadducci, F. Melgratti, H. Roldán, C.
author_sort	Gadducci, F.
title	On the semantics and implementation of replicated data types
title_short	On the semantics and implementation of replicated data types
title_full	On the semantics and implementation of replicated data types
title_fullStr	On the semantics and implementation of replicated data types
title_full_unstemmed	On the semantics and implementation of replicated data types
title_sort	on the semantics and implementation of replicated data types
url	http://hdl.handle.net/20.500.12110/paper_01676423_v167_n_p91_Gadducci
work_keys_str_mv	AT gadduccif onthesemanticsandimplementationofreplicateddatatypes AT melgrattih onthesemanticsandimplementationofreplicateddatatypes AT roldanc onthesemanticsandimplementationofreplicateddatatypes
_version_	1807324120605523968

On the semantics and implementation of replicated data types

Ejemplares similares