000208044 001__ 208044
000208044 005__ 20190416055546.0
000208044 0247_ $$2doi$$a10.1145/2611462.2611484
000208044 037__ $$aCONF
000208044 245__ $$aA paradox of eventual linearizability in shared memory
000208044 269__ $$a2014
000208044 260__ $$bACM Press$$c2014$$aNew York, New York, USA
000208044 336__ $$aConference Papers
000208044 520__ $$aThis 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)
000208044 700__ $$0240335$$g105326$$aGuerraoui, Rachid
000208044 700__ $$aRuppert, Eric
000208044 7112_ $$d15-18 07 2014$$cParis, France$$athe 2014 ACM symposium
000208044 773__ $$tProceedings of the 2014 ACM symposium on Principles of distributed computing - PODC '14$$q40-49
000208044 8564_ $$uhttps://infoscience.epfl.ch/record/208044/files/paradox_event_shr_mem_p40-guerraoui.pdf$$zPreprint$$s553001$$yPreprint
000208044 909C0 $$xU10407$$0252114$$pDCL
000208044 909CO $$ooai:infoscience.tind.io:208044$$qGLOBAL_SET$$pconf$$pIC
000208044 917Z8 $$x166927
000208044 937__ $$aEPFL-CONF-208044
000208044 973__ $$rREVIEWED$$sPUBLISHED$$aEPFL
000208044 980__ $$aCONF