®®®® SIIA Público

Título del libro:
Título del capítulo: What Cannot Be Implemented on Weak Memory?

Autores UNAM:
ARMANDO CASTAÑEDA ROJANO;
Autores externos:

Idioma:

Año de publicación:
2024
Palabras clave:

Concurrent objects; Distributed objects; General methodologies; Impossibility; Impossibility results; Memory modeling; Property; Release-acquire; Total store order; Weak memory models


Resumen:

We present a general methodology for establishing the impossibility of implementing certain concurrent objects on different (weak) memory models. The key idea behind our approach lies in characterizing memory models by their mergeability properties, identifying restrictions under which independent memory traces can be merged into a single valid memory trace. In turn, we show that the mergeability properties of the underlying memory model entail similar mergeability requirements on the specifications of objects that can be implemented on that memory model. We demonstrate the applicability of our approach to establish the impossibility of implementing standard distributed objects with different restrictions on memory traces on three memory models: strictly consistent memory, total store order, and release-acquire. These impossibility results allow us to identify tight and almost tight bounds for some objects, as well as new separation results between weak memory models, and between well-studied objects based on their implementability on weak memory models. © Armando Castañeda, Gregory Chockler, Brijesh Dongol, and Ori Lahav.


Entidades citadas de la UNAM: