%0 Generic %1 citeulike:71463 %A Charron-Bost, Bernadette %D 2004 %K agreement computing distributed tasks %T Reductions in Distributed Computing Part II: k-Threshold Agreement Tasks %U http://arxiv.org/abs/cs.DC/0412116 %X We extend the results of Part I by considering a new class of agreement tasks, the so-called k-Threshold Agreement tasks (previously introduced by Charron-Bost and Le Fessant). These tasks naturally interpolate between Atomic Commitment and Consensus. Moreover, they constitute a valuable tool to derive irreducibility results between Consensus tasks only. In particular, they allow us to show that (A) for a fixed set of processes, the higher the resiliency degree is, the harder the Consensus task is, and (B) for a fixed resiliency degree, the smaller the set of processes is, the harder the Consensus task is. The proofs of these results lead us to consider new oracle-based reductions, involving a weaker variant of the C-reduction introduced in Part I. We also discuss the relationship between our results and previous ones relating f-resiliency and wait-freedom.

@misc{citeulike:71463, abstract = {We extend the results of Part I by considering a new class of agreement tasks, the so-called k-Threshold Agreement tasks (previously introduced by Charron-Bost and Le Fessant). These tasks naturally interpolate between Atomic Commitment and Consensus. Moreover, they constitute a valuable tool to derive irreducibility results between Consensus tasks only. In particular, they allow us to show that (A) for a fixed set of processes, the higher the resiliency degree is, the harder the Consensus task is, and (B) for a fixed resiliency degree, the smaller the set of processes is, the harder the Consensus task is. The proofs of these results lead us to consider new oracle-based reductions, involving a weaker variant of the C-reduction introduced in Part I. We also discuss the relationship between our results and previous ones relating f-resiliency and wait-freedom.}, added-at = {2007-08-18T13:22:24.000+0200}, author = {Charron-Bost, Bernadette}, biburl = {https://www.bibsonomy.org/bibtex/2b68bcfab1264e17d9992676673dc19d2/a_olympia}, citeulike-article-id = {71463}, description = {citeulike}, eprint = {cs.DC/0412116}, interhash = {3b75ea888b1683508124cc8ea82bd9c0}, intrahash = {b68bcfab1264e17d9992676673dc19d2}, keywords = {agreement computing distributed tasks}, month = {December}, timestamp = {2007-08-18T13:22:57.000+0200}, title = {Reductions in Distributed Computing Part II: k-Threshold Agreement Tasks}, url = {http://arxiv.org/abs/cs.DC/0412116}, year = 2004 }