Guerraoui, Rachid
Ruppert, Eric
A paradox of eventual linearizability in shared memory
Proceedings of the 2014 ACM symposium on Principles of distributed computing - PODC '14
Proceedings of the 2014 ACM symposium on Principles of distributed computing - PODC '14
Proceedings of the 2014 ACM symposium on Principles of distributed computing - PODC '14
Proceedings of the 2014 ACM symposium on Principles of distributed computing - PODC '14
2014
2014
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)
ACM Press
Proceedings of the 2014 ACM symposium on Principles of distributed computing - PODC '14
Conference Papers
10.1145/2611462.2611484