000207929 001__ 207929
000207929 005__ 20190317000153.0
000207929 037__ $$aREP_WORK 000207929 245__$$aSafety-Liveness Exclusion in Distributed Computing
000207929 269__ $$a2015 000207929 260__$$bACM Press$$c2015$$aNew York, New York, USA
000207929 336__ $$aReports 000207929 520__$$aThe history of distributed computing is full of trade-offs between safety and liveness. For instance, one of the most celebrated results in the field, namely the impossibility of consensus in an asynchronous system basically says that we cannot devise an algorithm that deterministically ensures consensus agreement and validity (i.e., safety) on the one hand, and consensus wait-freedom (i.e., liveness) on the other hand. The motivation of this work is to study the extent to which safety and liveness properties inherently exclude each other. More specifically, we ask, given any safety property S, whether we can determine the strongest (resp. weakest) liveness property that can (resp. cannot) be achieved with S. We show that, maybe surprisingly, the answers to these safety-liveness exclusion questions are in general negative. This has several ramifications in various distributed computing contexts. In the context of consensus for example, this means that it is impossible to determine the strongest (resp. the weakest) liveness property that can (resp. cannot) be ensured with linearizability. However, we present a way to circumvent these impossibilities and answer positively the safety-liveness question by considering a restricted form of liveness. We consider a definition that gathers generalized forms of obstruction-freedom and lock-freedom while enabling to determine the strongest (resp. weakest) liveness property that can (resp. cannot) be implemented in the context of consensus and transactional memory.
000207929 6531_ $$aConcurrency 000207929 6531_$$aSafety
000207929 6531_ $$aLiveness 000207929 6531_$$aImpossibility Results
000207929 6531_ $$aConsensus 000207929 6531_$$aTransactional Memory
000207929 700__ $$0245645$$g200037$$aBushkov, Victor 000207929 700__$$aGuerraoui, Rachid$$g105326$$0240335
000207929 8564_ $$uhttps://infoscience.epfl.ch/record/207929/files/exclusionMain_1.pdf$$zPostprint$$s181159$$yPostprint
000207929 909C0 $$xU10407$$0252114$$pDCL 000207929 909CO$$ooai:infoscience.tind.io:207929$$qGLOBAL_SET$$pIC$$preport 000207929 917Z8$$x200037
000207929 917Z8 $$x200037 000207929 917Z8$$x200037
000207929 917Z8 $$x200037 000207929 917Z8$$x200037
000207929 937__ $$aEPFL-REPORT-207929 000207929 973__$$aEPFL
000207929 980__ aREPORT