A direct lower bound for k-set consensus

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A direct lower bound for k-set consensus

Full text

Pdf (110 KB)

Source

Annual ACM Symposium on Principles of Distributed Computing archive
Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing table of contents

Puerto Vallarta, Mexico

Page: 314

Year of Publication: 1998

ISBN:0-89791-977-7

Author

Hagit Attiya

Department of Computer Science, The Technion

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGOPS: ACM Special Interest Group on Operating Systems

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 10, Citation Count: 3

Additional Information:

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/277697.277770 What is a DOI?

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	H. Attiya. A direct proof of the asynchronous lower bound for k-set consensus. TR CS0930, Computer Science Dept., Technion, April 1998.
	2	John Adrian Bondy, Graph Theory With Applications, Elsevier Science Ltd, 1976
	3	Elizabeth Borowsky , Eli Gafni, Generalized FLP impossibility result for t-resilient asynchronous computations, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.91-100, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167119]
	4	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]
	5	Maurice Herlihy , Nir Shavit, The asynchronous computability theorem for t-resilient tasks, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.111-120, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167125]
	6	Michael Saks , Fotios Zaharoglou, Wait-free k-set agreement is impossible: the topology of public knowledge, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.101-110, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167122]

CITED BY 3

	Roberto De Prisco , Dahlia Malkhi , Michael K. Reiter, On k-set consensus problems in asynchronous systems, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.257-265, May 04-06, 1999, Atlanta, Georgia, United States
	Roberto de Prisco , Dahlia Malkhi , Michael Reiter, On k-Set Consensus Problems in Asynchronous Systems, IEEE Transactions on Parallel and Distributed Systems, v.12 n.1, p.7-21, January 2001
	Piotr Zielinski, Anti-Ω: the weakest failure detector for set agreement, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada

INDEX TERMS

Primary Classification:
C. Computer Systems Organization

General Terms:
Design, Performance, Reliability, Theory

Collaborative Colleagues:

Hagit Attiya: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player