The load and availability of Byzantine quorum systems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The load and availability of Byzantine quorum systems

Full text

Pdf (858 KB)

Source

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

Santa Barbara, California, United States

Pages: 249 - 257

Year of Publication: 1997

ISBN:0-89791-952-1

Authors

Dahlia Malkhi	AT&T Labs - Research, Florham Park, NJ
Michael Reiter	AT&T Labs - Research, Florham Park, NJ
Avishai Wool	Bell Laboratories, Lucent Technologies, Murray Hill, NJ

Sponsors

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 18, Citation Count: 6

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/259380.259450 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.

	ACC+83	M. Aizenman, J. T. Chayes, L. Chayes, J. Friihlich, and L. Russo. On a sharp transition from area law to perimeter law in a system of random surfaces. Comm. Mathematical Physics, 92:19-69, 1983.
	AE91	Divyakant Agrawal , Amr El Abbadi, An efficient and fault-tolerant solution for distributed mutual exclusion, ACM Transactions on Computer Systems (TOCS), v.9 n.1, p.1-20, Feb. 1991 [doi>10.1145/103727.103728]
	Baz96	Rida A. Bazzi, Planar Quorums, Proceedings of the 10th International Workshop on Distributed Algorithms, p.251-268, October 09-11, 1996
	BG86	Daniel Barbara , Hector Garcia-Molina, The vulnerability of vote assignments, ACM Transactions on Computer Systems (TOCS), v.4 n.3, p.187-213, Aug. 1986 [doi>10.1145/6420.6421]
	BG87	D. Barbara , H. Garcia-Molina, The reliability of voting mechanisms, IEEE Transactions on Computers, v.36 n.10, p.1197-1208, Oct. 1987 [doi>10.1109/TC.1987.1676860]
	BP75	R.E. Barlow and F. Prozchan. Statistical Theory o! Reliabilitit and Life Testing. Holt, Rinehart and Winston, Inc., 197'5.
	CAA92	S. Y. Cheung , M. H. Ammar , M. Ahamad, The Grid Protocol: A High Performance Scheme for Maintaining Replicated Data, IEEE Transactions on Knowledge and Data Engineering, v.4 n.6, p.582-592, December 1992 [doi>10.1109/69.180609]
	Con	N. Condorcet. Rssal sur i'application de l'analyse k la probabilit~ des decisions renduea ik la pluralite des voix. Paris, 1785.
	ET89	A. El Abbadi , S. Toueg, Maintaining availability in partitioned replicated databases, ACM Transactions on Database Systems (TODS), v.14 n.2, p.264-290, June 1989 [doi>10.1145/63500.63501]
	GB85	Hector Garcia-Molina , Daniel Barbara, How to assign votes in a distributed system, Journal of the ACM (JACM), v.32 n.4, p.841-860, Oct. 1985 [doi>10.1145/4221.4223]
	Gif79	David K. Gifford, Weighted voting for replicated data, Proceedings of the seventh ACM symposium on Operating systems principles, p.150-162, December 10-12, 1979, Pacific Grove, California, United States [doi>10.1145/800215.806583]
	Gri89	G.H. GrimmeSt. Percolation. Springer-Verlag, 1989.
	Hal86	M. Hall. Combinatorial Theory. John Wiley & Sons, 2nd edition, 1986.
	Her86	Maurice Herlihy, A quorum-consensus replication method for abstract data types, ACM Transactions on Computer Systems (TOCS), v.4 n.1, p.32-53, Feb. 1986 [doi>10.1145/6306.6308]
	KC91	Akhil Kumar , Shun Yan Cheung, A high availability N hierarchical grid algorithm for replicated data, Information Processing Letters, v.40 n.6, p.311-316, Dec. 30, 1991 [doi>10.1016/0020-0190(91)90199-R]
	Kes80	H. Kesten. The critical probability of bond percolation on the square lattice equals ~. Comm. Mathematical Physics, 71:41-59, 1980.
	Kes82	H. Kezten. Percolation Theory for Mathematicians. Birkh&user, Boston, 1982.
	KRS93	A. Kumar, M. Rabinovich, and R. K. Sinha. A performnnce study of general grid structures for replicated data. In Proc. l$th Inter. Con/. Dist. Camp. Sits., pages 178-185, 1993.
	Kum91	Akhil Kumar, Hierarchical Quorum Consensus: A New Algorithm for Managing Replicated Data, IEEE Transactions on Computers, v.40 n.9, p.996-1004, September 1991 [doi>10.1109/12.83661]
	LR93	Patrick Lincoln , John M. Rushby, The Formal Verification of an Algorithm for Interactive Consistency under a Hybrid Fault Model, Proceedings of the 5th International Conference on Computer Aided Verification, p.292-304, June 28-July 01, 1993
	LR94	P. Lincoln and J. Rushby. Formal verification of an interactive consistency algorithm for the Draper FTP architecture under a hybrid fault model In Proc. 9th IEEE Conference on Computer Assurance (COM- PASS 'gj), pages 107-120, June 1994.
	Mae85	Mamoru Maekawa, A N algorithm for mutual exclusion in decentralized systems, ACM Transactions on Computer Systems (TOCS), v.3 n.2, p.145-159, May 1985 [doi>10.1145/214438.214445]
	Men86	M.V. Menshikov. Coincidence of critical points in percolation problems. So~iet Mathematscs Doldadit, 33:856-859, 1986.
	MP92	~. Marcus and D. Peleg. Construction methods for quorum systems. Technical Report CS92-33, The Weizmann Institute of Science, Rehovot, Israel, 1992.
	MR97	Dahlia Malkhi , Michael Reiter, Byzantine quorum systems, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.569-578, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258650]
	Nei92	Mitchell L. Neilsen, Quorum structures in distributed systems, Kansas State University, Manhattan, KS, 1992
	NM92	M. L. Nielsen , M. Mizuno, Coterie Join Algorithm, IEEE Transactions on Parallel and Distributed Systems, v.3 n.5, p.582-590, September 1992 [doi>10.1109/71.159041]
	NW94	M. Naor and A. Wool. The load, capacity and availability of quorum systems. In Proc. 35th IEEE $itmp. Foundations o/ Camp. $ci. (FOC$), pages 214-225, 1994. To appear in SiAM J. Computing.
	PW95	David Peleg , Avishai Wool, The availability of quorum systems, Information and Computation, v.123 n.2, p.210-223, Dec. 1995 [doi>10.1006/inco.1995.1169]
	PW97a	David Peleg , Avishai Wool, The availability of crumbling wall quorum systems, Discrete Applied Mathematics, v.74 n.1, p.69-83, April 4, 1997 [doi>10.1016/S0166-218X(96)00016-9]
	PW97b	D. Peleg and A. Wool. Crumbling walls: A class of practical and efficient quorum systems. Distributed Computing, 10(2):87-98, 1997.
	RB94	Michael K. Reiter , Kenneth P. Birman, How to securely replicate services, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.3, p.986-1009, May 1994 [doi>10.1145/177492.177745]
	RST92	Sampath Rangarajan , Sanjeev Setia , Satish K. Tripathi, A Fault-Tolerant Algorithm for Replicated Data Management, Proceedings of the Eighth International Conference on Data Engineering, p.230-237, February 03-07, 1992
	Tho79	Robert H. Thomas, A Majority consensus approach to concurrency control for multiple copy databases, ACM Transactions on Database Systems (TODS), v.4 n.2, p.180-209, June 1979 [doi>10.1145/320071.320076]
	WB92	C. Wu and G. G. Belford. The triangular lattice protocol: A highly fault tolerant protocol for replicBted data. In Proc. l lth IBBE Syrup. on Reliable Dist. Sys., pages 66-73, 1992.
	Woo96	A. Wool. Quorum Sy, tem, for Di,tributed Control Protocols. PhD thesis, Department of Applied Mathematic6 and Computer Science, The Weigmann Institute of Science, Rehovot, hr&el, 1996.

CITED BY 6

	Rida A. Bazzi, Synchronous Byzantine quorum systems, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.259-266, August 21-24, 1997, Santa Barbara, California, United States
	Ing-Ray Chen , Ding-Chau Wang , Chih-Ping Chu, Analyzing User-Perceived Dependability and Performance Characteristics of Voting Algorithms for Managing Replicated Data, Distributed and Parallel Databases, v.14 n.3, p.199-219, November 2003
	Dahlia Malkhi , Michael K. Reiter, An Architecture for Survivable Coordination in Large Distributed Systems, IEEE Transactions on Knowledge and Data Engineering, v.12 n.2, p.187-202, March 2000
	Rida A. Bazzi, Synchronous Byzantine quorum systems, Distributed Computing, v.13 n.1, p.45-52, January 2000
	Dahlia Malkhi , Michael Reiter, Byzantine quorum systems, Distributed Computing, v.11 n.4, p.203-213, October 1998
	Rida A. Bazzi, Access cost for asynchronous Byzantine quorum systems, Distributed Computing, v.14 n.1, p.41-48, January 2001