Fault-Tolerant Techniques for Concurrent Objects

Abstract

Devising wait-free resilient implementations of concurrent objects from fault-prone base objects is a fundamental challenge of computer science. Wait-free means that any process that invokes an operation eventually receives a reply after executing a finite number of its own steps, even if other processes are arbitrarily slow or even failed. Resilience means that the implementation of the concurrent object behaves correctly despite the failure of up to t base objects (t being a threshold parameter a priori defined). The tutorial surveys different techniques to build wait-free resilient implementations of concurrent objects. Three complementary classes of techniques are presented: (1) fault-tolerance “by replication”, (2) fault-tolerance “by diversity”, and (3) fault-tolerance “by oracle”, respectively. The first is the well-known redundancy technique and its applicability depends on the kinds of faults that the objects can suffer. The second consists in combining the base objects with objects of other types (type refers here to a programming language notion: the type has to be powerful enough to allow implementing resilient objects). This technique basically relies on the universality of consensus objects. The third technique relies on the information we can obtain about the operational status of the processes.