%0 Journal Article %1 Zhang20091005 %A Zhang, Jialin %A Chen, Wei %D 2009 %J Information Processing Letters %K Multivalued consensus %N 17 %P 1005 - 1009 %R DOI: 10.1016/j.ipl.2009.06.004 %T Bounded cost algorithms for multivalued consensus using binary consensus instances %U http://www.sciencedirect.com/science/article/B6V0F-4WH2M4W-1/2/f26026642a3aa562d882c45d3f74f284 %V 109 %X In this paper, we present two bounded cost algorithms that solve multivalued consensus using binary consensus instances. Our first algorithm uses left ceilinglog2nright ceiling number of binary consensus instances where n is the number of processes, while our second algorithm uses at most binary consensus instances, where 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 A. Mostefaoui, M. Raynal, F. Tronel, From binary consensus to multivalued consensus in asynchronous message-passing systems, Information Processing Letters 73 (5-6) (2000) 207-212, where the number of binary consensus instances needed to solve one multivalued consensus is unbounded.

@article{Zhang20091005, abstract = {In this paper, we present two bounded cost algorithms that solve multivalued consensus using binary consensus instances. Our first algorithm uses [left ceiling]log2n[right ceiling] number of binary consensus instances where n is the number of processes, while our second algorithm uses at most binary consensus instances, where 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 [A. Mostefaoui, M. Raynal, F. Tronel, From binary consensus to multivalued consensus in asynchronous message-passing systems, Information Processing Letters 73 (5-6) (2000) 207-212], where the number of binary consensus instances needed to solve one multivalued consensus is unbounded.}, added-at = {2009-12-07T17:18:24.000+0100}, author = {Zhang, Jialin and Chen, Wei}, biburl = {https://www.bibsonomy.org/bibtex/2e7b02e434fce8dc397fe0fb8d123cd8a/signof}, description = {ScienceDirect - Information Processing Letters : Bounded cost algorithms for multivalued consensus using binary consensus instances}, doi = {DOI: 10.1016/j.ipl.2009.06.004}, interhash = {49ec06695f3304e478032df986cfbaba}, intrahash = {e7b02e434fce8dc397fe0fb8d123cd8a}, issn = {0020-0190}, journal = {Information Processing Letters}, keywords = {Multivalued consensus}, number = 17, pages = {1005 - 1009}, timestamp = {2009-12-07T17:18:43.000+0100}, title = {Bounded cost algorithms for multivalued consensus using binary consensus instances}, url = {http://www.sciencedirect.com/science/article/B6V0F-4WH2M4W-1/2/f26026642a3aa562d882c45d3f74f284}, volume = 109, year = 2009 }