The k-simultaneous consensus problem

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