The k-simultaneous consensus problem |
| |
Authors: | Yehuda Afek Eli Gafni Sergio Rajsbaum Michel Raynal Corentin Travers |
| |
Affiliation: | 1. Computer Science Department, Tel-Aviv University, 69978, Tel-Aviv, Israel 2. Department of Computer Science, UCLA, Los Angeles, CA, 90095, USA 3. Instituto de Matemáticas, UNAM, 04510, Mexico, Mexico 4. Université de Rennes 1, IRISA, Campus de Beaulieu, 35042, Rennes, France 5. Department of Computer Science, Technion, 32000, Haifa, Israel
|
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|