Strongly Terminating Early-Stopping ıt k-Set Agreement in Synchronous Systems with General Omission Failures

Abstract : The k-set agreement problem is a generalization of the consensus problem: considering a system made up of n processes where each process proposes a value, each non-faulty process has to decide a value such that a decided value is a proposed value, and no more than k different values are decided. It has recently be shown that, t in the crash failure model, min( f + 2, k + 1) is a lower bound on the number k of rounds for the non-faulty processes to decide (where t is an upper bound on the number of process crashes, and f , 0 ≤ f ≤ t, the actual number of crashes). This paper considers the k-set agreement problem in synchronous systems where up to t < n/2 processes can experience general omission failures (i.e., a process can crash or omit sending or receiving messages). It first introduces a new property, called strong termination. This property is on the processes that decide. It is satisfied if, not only every non-faulty process, but any process that neither crashes nor commits receive omission failure decides. The paper then presents a k-set agreement protocol that enjoys the following features. First, it is strongly terminating (to our knowledge, it is the first agreement protocol to satisfy this property, whatever the failure model considered). Then, it is early deciding and stopping in the sense that a process that either is non-faulty or commits only send omission failures decides and halts by round t min( f + 2, k + 1). To our knowledge, this is the first early deciding k-set agreek ment protocol for the general omission failure model. Moreover, the protocol proAn extended abstract of a preliminary version of this paper has appeared in the proceedings of SIROCCO 2006 [31].
Type de document :
Article dans une revue
Theory Comput. Syst., Springer, 2010, 47 (1), pp.259-287
Liste complète des métadonnées

Littérature citée [34 références]  Voir  Masquer  Télécharger
Contributeur : Corentin Travers <>
Soumis le : lundi 19 mai 2014 - 15:23:49
Dernière modification le : vendredi 16 novembre 2018 - 01:23:15
Document(s) archivé(s) le : lundi 10 avril 2017 - 23:42:35


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-00992773, version 1


Philippe Raipin Parvédy, Michel Raynal, Corentin Travers. Strongly Terminating Early-Stopping ıt k-Set Agreement in Synchronous Systems with General Omission Failures. Theory Comput. Syst., Springer, 2010, 47 (1), pp.259-287. 〈hal-00992773〉



Consultations de la notice


Téléchargements de fichiers