Wait-freedom with advice

Carole Delporte-Gallet 1 Hugues Fauconnier 1 Petr Kouznetsov 2 Eli Gafni 3
1 GANG - Networks, Graphs and Algorithms
LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications, Inria Paris-Rocquencourt
Abstract : We motivate and propose a new way of thinking about failure detectors which allows us to define what it means to solve a distributed task wait-free using a failure detector. In our model, the system is composed of computation processes that obtain inputs and are supposed to produce outputs and synchronization processes that are subject to failures and can query a failure detector. Under the condition that correct (never failing) synchronization processes take sufficiently many steps, they provide the computation processes with enough advice to solve the given task wait-free: every computation process outputs in a finite number of its own steps, regardless of the behavior of other computation processes. Every task can thus be characterized by the weakest failure detector that allows for solving it, and we show that every such failure detector captures a form of set agreement. We then obtain a complete classification of tasks, including ones that evaded comprehensible characterization so far, such as renaming or weak symmetry breaking.
Type de document :
Article dans une revue
Distributed Computing, Springer Verlag, 2015, 28 (1), pp.3-19. 〈10.1007/s00446-014-0231-6〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01251549
Contributeur : Carole Delporte-Gallet <>
Soumis le : mercredi 6 janvier 2016 - 13:38:18
Dernière modification le : vendredi 25 mai 2018 - 12:02:05

Identifiants

Collections

Citation

Carole Delporte-Gallet, Hugues Fauconnier, Petr Kouznetsov, Eli Gafni. Wait-freedom with advice. Distributed Computing, Springer Verlag, 2015, 28 (1), pp.3-19. 〈10.1007/s00446-014-0231-6〉. 〈hal-01251549〉

Partager

Métriques

Consultations de la notice

144