The inherent price of indulgence Export

@inproceedings{citeulike:4059099, abstract = {This paper presents a tight lower bound on the time complexity of indulgent consensus algorithms, i.e., consensus algorithms that use unreliable failure detectors. We state and prove our tight lower bound in the unifying framework of round-by-round fault detectors.We show that any \⋄ P -based t -resilient consensus algorithm requires at least t + 2 rounds for a global decision even in runs that are synchronous. We then prove the bound to be tight by exhibiting a new \⋄ P -based t -resilient consensus algorithm that reaches a global decision at round t + 2 in every synchronous run. Our new algorithm is in this sense significantly faster than the most efficient indulgent algorithm we knew of (which requires 2 t + 2 rounds).We contrast our lower bound with the well-known t + 1 round tight lower bound on consensus for the synchronous model, pointing out the price of indulgence.}, address = {New York, NY, USA}, author = {Dutta, Partha and Guerraoui, Rachid}, booktitle = {PODC '02: Proceedings of the twenty-first annual symposium on Principles of distributed computing}, citeulike-article-id = {4059099}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=571825.571838}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/571825.571838}, doi = {10.1145/571825.571838}, isbn = {1-58113-485-1}, keywords = {2005, asynchronous, indulgent, model, price}, location = {Monterey, California}, pages = {88--97}, posted-at = {2009-02-16 15:31:57}, priority = {2}, publisher = {ACM}, title = {The inherent price of indulgence}, url = {http://dx.doi.org/10.1145/571825.571838}, year = {2002} }

TY - CONF ID - citeulike:4059099 L3 - citeulike-article-id:4059099 N2 - This paper presents a tight lower bound on the time complexity of indulgent consensus algorithms, i.e., consensus algorithms that use unreliable failure detectors. We state and prove our tight lower bound in the unifying framework of round-by-round fault detectors.We show that any ⋄ P -based t -resilient consensus algorithm requires at least t + 2 rounds for a global decision even in runs that are synchronous. We then prove the bound to be tight by exhibiting a new ⋄ P -based t -resilient consensus algorithm that reaches a global decision at round t + 2 in every synchronous run. Our new algorithm is in this sense significantly faster than the most efficient indulgent algorithm we knew of (which requires 2 t + 2 rounds).We contrast our lower bound with the well-known t + 1 round tight lower bound on consensus for the synchronous model, pointing out the price of indulgence. CY - Monterey, California SN - 1-58113-485-1 AD - New York, NY, USA EP - 97 TI - The inherent price of indulgence PB - ACM T2 - PODC '02: Proceedings of the twenty-first annual symposium on Principles of distributed computing SP - 88 KW - 2005 KW - asynchronous KW - indulgent KW - model KW - price AU - Dutta, Partha AU - Guerraoui, Rachid PY - 2002/// UR - http://dx.doi.org/10.1145/571825.571838 ER -