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

Carole Delporte-Gallet 1, 2 Hugues Fauconnier 1, 2 Michel Raynal 3, 4
2 GANG - Networks, Graphs and Algorithms
LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications, Inria Paris-Rocquencourt
4 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
Abstract : A non-blocking implementation of a concurrent object is an implementation that does not prevent concurrent accesses to the internal representation of the object, while guaranteeing the deadlock-freedom progress condition without using locks. Considering a failure free context, G. Taubenfeld has introduced (DISC 2013) a simple modular approach, captured under a new problem called the fair synchronization problem, to transform a non-blocking implementation into a starvation-free implementation satisfying a strong fairness requirement. This paper extends this approach in several directions. It first generalizes the fair synchronization problem to read/write asynchronous systems where any number of processes may crash. Then, it introduces a new failure detector and uses it to solve the fair synchronization problem when processes may crash. This failure detector, denoted QP (Quasi Perfect), is very close to, but strictly weaker than, the perfect failure detector. Last but not least, the paper shows that the proposed failure detector QP is optimal in the sense that the information on failures it provides to the processes can be extracted from any algorithm solving the fair synchronization problem in the presence of any number of process crash failures.
Type de document :
Communication dans un congrès
33h Symposium on Reliable Distributed Systems (SRDS), Oct 2014, Nara, Japan. pp.161-170, 2014, 〈10.1109/SRDS.2014.18 〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01100780
Contributeur : Carole Delporte-Gallet <>
Soumis le : mercredi 7 janvier 2015 - 09:56:06
Dernière modification le : vendredi 25 mai 2018 - 12:02:05

Identifiants

Citation

Carole Delporte-Gallet, Hugues Fauconnier, Michel Raynal. Fair Synchronization in the Presence of Process Crashes and its Weakest Failure Detector. 33h Symposium on Reliable Distributed Systems (SRDS), Oct 2014, Nara, Japan. pp.161-170, 2014, 〈10.1109/SRDS.2014.18 〉. 〈hal-01100780〉

Partager

Métriques

Consultations de la notice

901