We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
The k-simultaneous consensus problem.
- Authors
Afek, Yehuda; Gafni, Eli; Rajsbaum, Sergio; Raynal, Michel; Travers, Corentin
- Abstract
This paper introduces and investigates the k-simultaneous consensus task: each process participates at the same time in k independent consensus instances until it decides in any one of them. It is shown that the k-simultaneous consensus task is equivalent to the k-set agreement task in the wait-free read/write shared memory model, and furthermore k-simultaneous consensus possesses properties that k-set does not. In particular we show that the multivalued version and the binary version of the k-simultaneous consensus task are wait-free equivalent. These equivalences are independent of the number of processes. Interestingly, this provides us with a new characterization of the k-set agreement task that is based on the fundamental binary consensus problem.
- Subjects
CONSENSUS (Social sciences); TASKS; MEMORY; COMPUTER storage devices; COMPUTER peripherals
- Publication
Distributed Computing, 2010, Vol 22, Issue 3, p185
- ISSN
0178-2770
- Publication type
Article
- DOI
10.1007/s00446-009-0090-8