Bounded Cost Algorithms for Multivalued Consensus using Binary Consensus Instances

In this paper, we present two bounded cost algorithms that solve multivalued consensus using binary consensus instances. Our first algorithm usesdlog2 nenumber of binary consensus instances where n is the number of processes, while our second algorithm uses at most 2e k binary consensus instances, where e k is the maximum length of the binary representation of all proposed values in the run. Both algorithms are significant improvements over the previous algorithm in [6], where the number of binary consensus instances needed to solve one multivalued consensus is unbounded.