logo móvil
Contáctanos

Los tipos de datos relajados como condiciones de consistencia

Autores: Talmage, Edward; Welch, Jennifer L.

Idioma: Inglés

Editor: MDPI

Año: 2018

Descargar PDF

Acceso abierto

Artículo científico
2018

Los tipos de datos relajados como condiciones de consistencia


Categoría

Ingeniería y Tecnología

Subcategoría

Ingeniería de Software

Palabras clave

Baja el rendimiento
Estructuras de datos compartidas
Debilitar las condiciones de consistencia
Relajar las especificaciones secuenciales
Tipos de datos
Comportamientos
Equivalencia
Linearizabilidad
Atomicidad
Relajamientos
Condición de consistencia
Comportamientos concurrentes
Objeto
Garantías
Posibilidades
Literatura
Condiciones conocidas
Comparables
Más fuertes.

Licencia

CC BY-SA – Atribución – Compartir Igual

Consultas: 40

Citaciones: Sin citaciones


Descripción
En la búsqueda de estructuras de datos compartidas de alto rendimiento, debilitar las condiciones de consistencia y relajar las especificaciones secuenciales de los tipos de datos son dos de las herramientas principales disponibles en la literatura actual. En este documento, mostramos que estos dos enfoques son, en muchos casos, diferentes formas de especificar los mismos conjuntos de comportamientos concurrentes permitidos de un objeto de datos compartido dado. Esta equivalencia nos permite utilizar la descripción que sea más clara, más simple o más fácil de lograr garantías equivalentes. Específicamente, para tres relajaciones comunes de tipos de datos, definimos condiciones de consistencia de manera que la combinación de la nueva condición de consistencia y un tipo no relajado permita los mismos comportamientos que la Linealizabilidad y la versión relajada del tipo de datos. Por otro lado, para la condición de consistencia -Atomicidad, definimos una nueva relajación de tipo de datos de manera que los comportamientos permitidos por la versión relajada de un tipo de datos, combinados con la Linealizabilidad, sean los mismos que los permitidos por -Atomicidad y el tipo original. Como ejemplo de las posibilidades abiertas por nuestra nueva equivalencia, utilizamos técnicas estándar de la literatura sobre condiciones de consistencia para demostrar que las tres relajaciones de tipos de datos que consideramos no son comparables entre sí ni a varias condiciones similares conocidas. Finalmente, mostramos una clase particular de tipos de datos donde una de nuestras condiciones de consistencia recién definidas es comparable y más fuerte que una de las condiciones de consistencia conocidas que consideramos.

Otros recursos que podrían interesarte

Temas Virtualpro