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

The k-simultaneous consensus problem

Abstract : 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.
Document type :
Reports (Research report)
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download
Contributor : Anne Jaigu Connect in order to contact the contributor
Submitted on : Monday, January 19, 2009 - 12:52:32 PM
Last modification on : Tuesday, November 29, 2022 - 12:06:07 PM
Long-term archiving on: : Tuesday, June 8, 2010 - 8:42:37 PM


Files produced by the author(s)


  • HAL Id : inria-00354248, version 1


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



Record views


Files downloads