Lower bounds for randomized consensus under a weak adversary

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Lower bounds for randomized consensus under a weak adversary

Full text

Pdf (367 KB)

Source

Annual ACM Symposium on Principles of Distributed Computing archive
Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing table of contents

Toronto, Canada

SESSION: R8 table of contents

Pages 315-324

Year of Publication: 2008

ISBN:978-1-59593-989-0

Authors

Hagit Attiya	Technion, Haifa, Israel
Keren Censor	Technion, Haifa, Israel

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems
ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 11, Downloads (12 Months): 76, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1400751.1400793 What is a DOI?

ABSTRACT

This paper studies the inherent trade-off between termination probability and total step complexity of randomized consensus algorithms. It shows that for every integer k, the probability that an f-resilient randomized consensus algorithm of n processes does not terminate with agreement within k(n-f) steps is at least 1/c^k, for some constant c.

The lower bound holds for asynchronous systems, where processes communicate either by message passing or through shared memory, under a very weak adversary that determines the schedule in advance, without observing the algorithm's actions. This complements algorithms of Kapron et al. (SODA 2008), for message-passing systems, and of Aumann et al. (PODC 1997, Distributed Computing 2005), for shared-memory systems.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	James Aspnes, Lower bounds for distributed coin-flipping and randomized consensus, Journal of the ACM (JACM), v.45 n.3, p.415-450, May 1998 [doi>10.1145/278298.278304]
	2	James Aspnes, Randomized protocols for asynchronous consensus, Distributed Computing, v.16 n.2-3, p.165-175, September 2003 [doi>10.1007/s00446-002-0081-5]
	3	Hagit Attiya , Amotz Bar-Noy , Danny Dolev , David Peleg , Rüdiger Reischuk, Renaming in an asynchronous environment, Journal of the ACM (JACM), v.37 n.3, p.524-548, July 1990 [doi>10.1145/79147.79158]
	4	Hagit Attiya , Keren Censor, Tight bounds for asynchronous randomized consensus, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250814]
	5	Jennifer L. Welch , Hagit Attiya, Distributed computing: fundamentals, simulations and advanced topics, McGraw-Hill, Inc., Hightstown, NJ, 1998
	6	Yonatan Aumann, Efficient asynchronous consensus with the weak adversary scheduler, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.209-218, August 21-24, 1997, Santa Barbara, California, United States [doi>10.1145/259380.259441]
	7	Yonatan Aumann , Michael A. Bender, Efficient low-contention asynchronous consensus with the value-oblivious adversary scheduler, Distributed Computing, v.17 n.3, p.191-207, March 2005 [doi>10.1007/s00446-004-0113-4]
	8	Yonatan Aumann , Avivit Kapah-Levy, Cooperative sharing and asynchronous consensus using single-reader single-writer registers, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.61-70, January 17-19, 1999, Baltimore, Maryland, United States
	9	Ziv Bar-Joseph , Michael Ben-Or, A tight lower bound for randomized synchronous consensus, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.193-199, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277697.277733]
	10	Michael Ben-Or , Elan Pavlov , Vinod Vaikuntanathan, Byzantine agreement in the full-information model in O(log n) rounds, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132543]
	11	Miguel Castro , Barbara Liskov, Practical byzantine fault tolerance and proactive recovery, ACM Transactions on Computer Systems (TOCS), v.20 n.4, p.398-461, November 2002 [doi>10.1145/571637.571640]
	12	Tushar Deepak Chandra, Polylog randomized wait-free consensus, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.166-175, May 23-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/248052.248083]
	13	Soma Chaudhuri, More choices allow more faults: set consensus problems in totally asynchronous systems, Information and Computation, v.105 n.1, p.132-158, July 1993 [doi>10.1006/inco.1993.1043]
	14	L. Cheung. Randomized wait-free consensus using an atomicity assumption. In Proceedings of the 9th International Conference on Principles of Distributed Systems (OPODIS), pages 47--60, 2005.
	15	Benny Chor , Amos Israeli , Ming Li, On processor coordination using asynchronous hardware, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.86-97, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41848]
	16	Benny Chor , Michael Merritt , David B. Shmoys, Simple constant-time consensus protocols in realistic failure models, Journal of the ACM (JACM), v.36 n.3, p.591-614, July 1989 [doi>10.1145/65950.65956]
	17	D. Dolev and H. R. Strong. Authenticated algorithms for byzantine agreement. SIAM J. Comput., 12(4):656--666, 1983.
	18	M. J. Fischer and N. A. Lynch. A lower bound for the time to assure interactive consistency. Inf. Process. Lett., 14(4):183--186, 1982.
	19	Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
	20	Shafi Goldwasser , Elan Pavlov , Vinod Vaikuntanathan, Fault-Tolerant Distributed Computing in Full-Information Networks, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.15-26, October 21-24, 2006 [doi>10.1109/FOCS.2006.30]
	21	Maurice Herlihy, Wait-free synchronization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.1, p.124-149, Jan. 1991 [doi>10.1145/114005.102808]
	22	Bruce Kapron , David Kempe , Valerie King , Jared Saia , Vishal Sanwalani, Fast asynchronous byzantine agreement and leader election with full information, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.1038-1047, January 20-22, 2008, San Francisco, California
	23	A. Karlin and A. C.-C. Yao. Probabilistic lower bounds for byzantine agreement and clock synchronization. Unpublished manuscript.
	24	Valerie King , Jared Saia , Vishal Sanwalani , Erik Vee, Scalable leader election, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.990-999, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109667]
	25	Ramakrishna Kotla , Lorenzo Alvisi , Mike Dahlin , Allen Clement , Edmund Wong, Zyzzyva: speculative byzantine fault tolerance, Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles, October 14-17, 2007, Stevenson, Washington, USA
	26	M. C. Loui and H. H. Abu-Amara. Memory requirements for agreement among unreliable asynchronous processes. Advances in Computing Research, pages 163--183, 1987.
	27	Yoram Moses , Sergio Rajsbaum, A Layered Analysis of Consensus, SIAM Journal on Computing, v.31 n.4, p.989-1021, 2002 [doi>10.1137/S0097539799364006]