Narrowing power vs efficiency in synchronous set agreement

Achour Mostefaoui 1 Michel Raynal 1 Corentin Travers 1
1 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
Abstract : The $k$-set agreement problem is a generalization of the uniform consensus problem: each process proposes a value, and each non-faulty process has to decide a value such that a decided value is a proposed value, and at most $k$ different values are decided. It has been shown that any algorithm that solves the $k$-set agreement problem in synchronous systems that can suffer up to $t$ crash failures requires $\lfloor \frac{t}{k} \rfloor +1$ rounds in the worst case. It has also been shown that it is possible to design early deciding algorithms where no process decides and halts after $\min\big( \lfloor \frac{f}{k} \rfloor +2, \lfloor \frac{t}{k} \rfloor +1\big)$ rounds, where $f$ is the number of actual crashes in a run ($0\leq f\leq t$). This paper explores a new direction to solve the $k$-set agreement problemin a synchronous system. It considers that the system is enriched with base objects (denoted $[m,\ell]$\_SA objects) that allow solving the $\ell$-set agreement problem in a set of $m$ processes ($m
Type de document :
Rapport
[Research Report] PI 1836, 2007, pp.13
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00139286
Contributeur : Anne Jaigu <>
Soumis le : vendredi 30 mars 2007 - 10:44:08
Dernière modification le : mercredi 16 mai 2018 - 11:23:13
Document(s) archivé(s) le : mercredi 7 avril 2010 - 01:48:08

Fichiers

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

Identifiants

  • HAL Id : inria-00139286, version 1

Citation

Achour Mostefaoui, Michel Raynal, Corentin Travers. Narrowing power vs efficiency in synchronous set agreement. [Research Report] PI 1836, 2007, pp.13. 〈inria-00139286〉

Partager

Métriques

Consultations de la notice

312

Téléchargements de fichiers

144