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.
