Skip to Main content Skip to Navigation
New interface
Reports (Research report)

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

Michel Raynal 1 Julien Stainer 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 : This paper investigates the relation linking the s-simultaneous consensus problem and the k-set agreement problem. 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 the k-set agreement problem, 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 Zs,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 Zs,k -based algorithm that solves the (s, k)-SSA problem, and shows that the "shared memory"-oriented part of Zs,k is necessary to solve the (s, k)-SSA problem (this generalizes and refines a previous result that showed that the 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 (s1 , k1 ) and (s2 , k2 ) such that s1 k1 = s2 k2 and (s1 , k1 )-SSA and (s2 , k2 )-SSA are incomparable.
Document type :
Reports (Research report)
Complete list of metadata

Cited literature [23 references]  Display  Hide  Download
Contributor : Julien Stainer Connect in order to contact the contributor
Submitted on : Friday, February 22, 2013 - 6:17:50 PM
Last modification on : Wednesday, October 26, 2022 - 8:16:46 AM
Long-term archiving on: : Sunday, April 2, 2017 - 4:32:25 AM


Files produced by the author(s)


  • HAL Id : hal-00787992, version 2


Michel Raynal, Julien Stainer. Simultaneous Consensus vs Set Agreement a Message-Passing Sensitive Hierarchy of Agreement Problems. [Research Report] PI-2003, 2013. ⟨hal-00787992v2⟩



Record views


Files downloads