Enriching the reduction map of sub-consensus tasks

Abstract : Understanding the relative computability power of tasks, in the presence of asynchrony and failures, is a central concern of distributed computing theory. In the wait-free case, where the system consists of n processes and any of them can fail by crashing, substantial attention has been devoted to understanding the relative power of the subconsensus family of tasks, which are too weak to solve consensus for two processes. The first major results showed that set agreement and renaming (except for some particular values of n) cannot be solved wait-free in read/write memory. Then it was proved that renaming is strictly weaker than set agreement (when n is odd). This paper considers a natural family of subconsensus tasks that includes set agreement, renaming and other generalized symmetry breaking (GSB) tasks. It extends previous results, and proves various new results about when there is a reduction and when not, among these tasks. Among other results, the paper shows that there are incomparable subconsensus tasks.
Type de document :
Rapport
[Research Report] PI-1976, 2011, pp.14
Liste complète des métadonnées

Littérature citée [26 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00591526
Contributeur : Ist Rennes <>
Soumis le : lundi 9 mai 2011 - 15:05:52
Dernière modification le : jeudi 15 novembre 2018 - 11:57:36
Document(s) archivé(s) le : vendredi 9 novembre 2012 - 10:56:54

Fichier

PI-1976.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00591526, version 1

Citation

Armando Castañeda, Damien Imbs, Sergio Rajsbaum, Michel Raynal. Enriching the reduction map of sub-consensus tasks. [Research Report] PI-1976, 2011, pp.14. 〈inria-00591526〉

Partager

Métriques

Consultations de la notice

594

Téléchargements de fichiers

135