Skip to Main content Skip to Navigation
Reports

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.
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal.inria.fr/inria-00354248
Contributor : Anne Jaigu <>
Submitted on : Monday, January 19, 2009 - 12:52:32 PM
Last modification on : Friday, July 10, 2020 - 4:11:28 PM
Long-term archiving on: : Tuesday, June 8, 2010 - 8:42:37 PM

Files

PI-1920.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00354248, version 1

Citation

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

Share

Metrics

Record views

544

Files downloads

580