Fair Synchronization in the Presence of Process Crashes and its Weakest Failure Detector

International audienceA non-blocking implementation of a concurrentobject is an implementation that does not prevent concurrentaccesses to the internal representation of the object, whileguaranteeing the deadlock-freedom progress condition withoutusing locks. Considering a failure free context, G. Taubenfeldhas introduced (DISC 2013) a simple modular approach,captured under a new problem called the fair synchronizationproblem, to transform a non-blocking implementation intoa starvation-free implementation satisfying a strong fairnessrequirement. This paper extends this approach in severaldirections. It first generalizes the fair synchronization problemto read/write asynchronous systems where any number ofprocesses may crash. Then, it introduces a new failure detectorand uses it to solve the fair synchronization problem whenprocesses may crash. This failure detector, denoted QP (QuasiPerfect), is very close to, but strictly weaker than, the perfectfailure detector. Last but not least, the paper shows that theproposed failure detector QP is optimal in the sense that theinformation on failures it provides to the processes can beextracted from any algorithm solving the fair synchronizationproblem in the presence of any number of process crashfailures