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)
2014
New York, New York, USA
40
49
REVIEWED
EPFL
Event name | Event place | Event date |
Paris, France | 15-18 07 2014 | |