Narrowing power vs efficiency in synchronous set agreement - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2007

Narrowing power vs efficiency in synchronous set agreement

Résumé

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
Fichier principal
Vignette du fichier
PI-1836.pdf (348.58 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00139286 , version 1 (30-03-2007)

Identifiants

  • HAL Id : inria-00139286 , version 1

Citer

Achour Mostefaoui, Michel Raynal, Corentin Travers. Narrowing power vs efficiency in synchronous set agreement. [Research Report] PI 1836, 2007, pp.13. ⟨inria-00139286⟩
153 Consultations
129 Téléchargements

Partager

Gmail Facebook X LinkedIn More