Skip to Main content Skip to Navigation
Conference papers

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

Abstract : 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.
Complete list of metadata

https://hal.inria.fr/hal-00920725
Contributor : Julien Stainer <>
Submitted on : Thursday, December 19, 2013 - 9:54:38 AM
Last modification on : Friday, January 8, 2021 - 3:40:02 AM

Links full text

Identifiers

Citation

Michel Raynal, Julien Stainer. Simultaneous Consensus vs Set Agreement: A Message-Passing-Sensitive Hierarchy of Agreement Problems. SIROCCO, Jul 2013, Ischia, Italy. pp.298-309, ⟨10.1007/978-3-319-03578-9_25⟩. ⟨hal-00920725⟩

Share

Metrics

Record views

1370