Safety, Liveness and Parallelism in Concurrent Computing

The correctness of a shared object, which can be accessed by several processes concurrently, is specified through two different kinds of properties - safety and liveness. When implementing a shared object it is important to specify its correctness in a such way that it should be feasible under given assumptions. In this work we study the question of implementability of shared objects that satisfy certain safety and liveness properties under certain assumptions. In particular, we study implementability of liveness properties of transactional memory (TM) shared objects with strict serializability, a strong safety property. TM allows a programmer to encapsulate pieces of sequential code within transactions that run concurrently and it ensures that transactions run in some consistent manner by committing or aborting them. First, we give a formal definition of a liveness property in the TM context. Then, we proceed to show that certain classes of liveness properties of TM can not be implemented with strict serializability in a system in which processes are prone to failures. We also show that, in general, we cannot find a weakest non-implementable (resp. strongest implementable) liveness of TM when we require some common safety property like strict serializability. Moreover, we generalize this result to other shared object types and give a characterization of safety properties for which we can find weakest non-implementable (resp. strongest implementable) liveness. In addition to correctness properties we study the limitations of parallelism which affects performance and scalability of implementations. Specifically, we show that we cannot implement a TM which guarantees disjoint-access parallelism, which say that transactions do not need to synchronize unless they access the same application objects, while guaranteeing very weak safety and the weakest non-blocking liveness.

The Weakest Failure Detectors to Boost Obstruction-Freedom

Rachid Guerraoui, Michal Kapalka

It is considered good practice in concurrent computing to devise shared object implementations that ensure a minimal obstruction-free progress property and delegate the task of boosting liveness to independent generic oracles called contention managers. This paper determines necessary and sufficient conditions to implement wait-free and non-blocking contention managers, i.e., contention managers that ensure wait-freedom (resp. non-blockingness) of any associated obstruction-free object implementation. The necessary conditions hold even when universal objects (like compare-and-swap) or random oracles are available in the implementation of the contention manager. On the other hand, the sufficient conditions assume only basic read/write objects, i.e., registers. We show that failure detector ⋄P is the weakest to convert any obstruction-free algorithm into a wait-free one, and Ω*, a new failure detector which we introduce in this paper, and which is strictly weaker than ⋄P but strictly stronger than Ω, is the weakest to convert any obstruction-free algorithm into a non-blocking one. We also address the issue of minimizing the overhead imposed by contention management in low contention scenarios. We propose two intermittent failure detectors I_Ω* and I_⋄P that are in a precise sense equivalent to, respectively, Ω* and ⋄P, but allow for reducing the cost of failure detection in eventually synchronous systems when there is little contention. We present two contention managers: a non-blocking one and a wait-free one, that use, respectively, I_Ω* and I_⋄P. When there is no contention, the first induces very little overhead whereas the second induces some non-trivial overhead. We show that wait-free contention managers, unlike their non-blocking counterparts, impose an inherent non-trivial overhead even in contention-free executions.

2007

Safety-Liveness Exclusion in Distributed Computing

Victor Bushkov, Rachid Guerraoui

The 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.

ACM Press2015

Safety-Liveness Exclusion in Distributed Computing

Victor Bushkov, Rachid Guerraoui

ACM2015