Skip to Main content Skip to Navigation
Reports

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
IRISA-D1 - SYSTÈMES LARGE ÉCHELLE, Inria Rennes – Bretagne Atlantique
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.
Complete list of metadata

Cited literature [23 references]  Display  Hide  Download

https://hal.inria.fr/hal-00787992
Contributor : Julien Stainer Connect in order to contact the contributor
Submitted on : Friday, February 22, 2013 - 6:17:50 PM
Last modification on : Tuesday, June 15, 2021 - 4:25:50 PM
Long-term archiving on: : Sunday, April 2, 2017 - 4:32:25 AM

File

Looking-for-weakest-FD-for-xy-...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00787992, version 2

Citation

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

Share

Metrics

Record views

1278

Files downloads

494