%0 Journal Article %1 yehudaksimultaneous %A Afek, Yehuda %A Gafni, Eli %A Rajsbaum, Sergio %A Raynal, Michel %A Travers, Corentin %D 2010 %J Distributed Computing %K consensus k-setagreement k-simultaneous %P -- %T The k-simultaneous consensus problem %U http://dx.doi.org/10.1007/s00446-009-0090-8 %X 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.

@article{yehudaksimultaneous, 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.}, added-at = {2009-12-08T15:19:05.000+0100}, author = {Afek, Yehuda and Gafni, Eli and Rajsbaum, Sergio and Raynal, Michel and Travers, Corentin}, biburl = {https://www.bibsonomy.org/bibtex/263ac3807733969e3e8cc096db42dafe3/signof}, description = {SpringerLink - Journal Article}, interhash = {9b073463796c42c9d49a3faf37e230b3}, intrahash = {63ac3807733969e3e8cc096db42dafe3}, journal = {Distributed Computing}, keywords = {consensus k-setagreement k-simultaneous}, pages = {--}, timestamp = {2009-12-08T15:19:05.000+0100}, title = {The k-simultaneous consensus problem}, url = {http://dx.doi.org/10.1007/s00446-009-0090-8}, year = 2010 }