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)


Published in:
Proceedings of the 2014 ACM symposium on Principles of distributed computing - PODC '14, 40-49
Presented at:
the 2014 ACM symposium, Paris, France, 15-18 07 2014
Year:
2014
Publisher:
New York, New York, USA, ACM Press
Laboratories:




 Record created 2015-05-28, last modified 2018-06-22

Preprint:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)