Back to Search Start Over

Simultaneous Consensus vs Set Agreement: A Message-Passing-Sensitive Hierarchy of Agreement Problems

Authors :
Michel Raynal
Julien Stainer
As Scalable As Possible: foundations of large scale dynamic distributed systems (ASAP)
Inria Rennes – Bretagne Atlantique
Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-SYSTÈMES LARGE ÉCHELLE (IRISA-D1)
Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA)
Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes)
Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes)
Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA)
Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)
Institut Universitaire de France (IUF)
Ministère de l'Education nationale, de l’Enseignement supérieur et de la Recherche (M.E.N.E.S.R.)
ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011)
SYSTÈMES LARGE ÉCHELLE (IRISA-D1)
Université de Rennes 1 (UR1)
Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes)
Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1)
Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA)
Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Inria Rennes – Bretagne Atlantique
Institut National de Recherche en Informatique et en Automatique (Inria)
Source :
Structural Information and Communication Complexity ISBN: 9783319035772, SIROCCO, SIROCCO, Jul 2013, Ischia, Italy. pp.298-309, ⟨10.1007/978-3-319-03578-9_25⟩
Publication Year :
2013
Publisher :
Springer International Publishing, 2013.

Abstract

International audience; This paper investigates the relation linking the s-simultaneous consensus problem and the k-set agreement problem in wait-free message-passing systems. To this end, it first defines the (s,k)-SSA problem which captures jointly both problems: each process proposes a value, executes s simultaneous instances of a k-set agreement algorithm, and has to decide a value so that no more than sk different values are decided. The paper introduces then a new failure detector class denoted Z s,k , which is made up of two components, one focused on the "shared memory object" that allows the processes to cooperate, and the other focused on the liveness of (s,k)-SSA algorithms. A novelty of this failure detector lies in the fact that the definition of its two components are intimately related. Then, the paper presents a Z s,k -based algorithm that solves the (s,k)-SSA problem, and shows that the "shared memory"-oriented part of Z s,k is necessary to solve the (s,k)-SSA problem (this generalizes and refines a previous result that showed that the generalized quorum failure detector Σ k is necessary to solve k-set agreement). Finally, the paper investigates the structure of the family of (s,k)-SSA problems and introduces generalized (asymmetric) simultaneous set agreement problems in which the parameter k can differ in each underlying k-set agreement instance. Among other points, it shows that, for s,k > 1, (a) the (sk,1)-SSA problem is strictly stronger that the (s,k)-SSA problem which is itself strictly stronger than the (1,ks)-SSA problem, and (b) there are pairs (s 1,k 1) and (s 2,k 2) such that s 1 k 1 = s 2 k 2 and (s 1,k 1)-SSA and (s 2,k 2)-SSA are incomparable.; Cet article étudie les relations liant le problème du consensus s-simultané et celui de l'accord k-ensembliste.

Details

ISBN :
978-3-319-03577-2
ISBNs :
9783319035772
Database :
OpenAIRE
Journal :
Structural Information and Communication Complexity ISBN: 9783319035772, SIROCCO, SIROCCO, Jul 2013, Ischia, Italy. pp.298-309, ⟨10.1007/978-3-319-03578-9_25⟩
Accession number :
edsair.doi.dedup.....0159c01e08ef8d124e5e2d65c1812f1c
Full Text :
https://doi.org/10.1007/978-3-319-03578-9_25