The k-simultaneous consensus problem

Yehuda Afek (1) , Eli Gafni (2) , Sergio Rajsbaum (3) , Michel Raynal (4) , Corentin Travers (5)

1 TAU-CS - School of Computer Science
2 UCLA - Computer Science Department [Los Angeles]
3 Instituto de Matematicas [México]
4 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
5 Department of Computer Science [Haifa]

This paper introduces and investigates the k-simultaneous consensus problem: each process participates at the same time in k independent consensus instances until it decides in any one of them. Two results are presented. The first shows that the k-simultaneous consensus problem and the k-set agreement problem are wait-free equivalent in read/write shared memory systems. The second shows that the multivalued version and the binary version of the k-simultaneous consensus problem are wait-free equivalent. These equivalences are independent of the number of processes. An immediate consequence of these results is that the k-set agreement problem and the k-simultaneous binary consensus problem are equivalent. This not only provides a new characterization of the k-set agreement problem but also provides a meaning to the notion of k-set binary agreement.

Mots clés: Asynchronous shared memory systems; Binary vs multivalued agreement; Consensus; Distributed computability; Process crash; Set agreement; Wait-free construction

Domaines: Calcul parallèle, distribué et partagé [cs.DC]

Yehuda Afek, Eli Gafni, Sergio Rajsbaum, Michel Raynal, Corentin Travers. The k-simultaneous consensus problem. [Research Report] PI 1920, 2009, pp.17. ⟨inria-00354248⟩