A paradox of eventual linearizability in shared memory

This paper compares, for the rst time, the computational power of linearizable objects with that of eventually linearizable ones. We present the following paradox. We show that, unsurprisingly, no set of eventually linearizable objects can (1) implement any non-trivial linearizable object, nor (2) boost the consensus power of simple objects like linearizable registers. We also show, perhaps surprisingly, that any implementation of an eventually linearizable complex object like a fetch&increment counter (from linearizable base objects), can itself be viewed as a fully linearizable implementation of the same fetch&increment counter (using the exact same set of base objects)


Publié dans:
Proceedings of the 2014 ACM symposium on Principles of distributed computing - PODC '14, 40-49
Présenté à:
the 2014 ACM symposium, Paris, France, 15-18 07 2014
Année
2014
Publisher:
New York, New York, USA, ACM Press
Laboratoires:




 Notice créée le 2015-05-28, modifiée le 2019-04-16

Preprint:
Télécharger le document
PDF

Évaluer ce document:

Rate this document:
1
2
3
 
(Pas encore évalué)