Synchronous Byzantine quorum systems

被引：31

作者：

Bazzi, RA ^{[1
]}

机构：

[1] Arizona State Univ, Dept Comp Sci & Engn, Tempe, AZ 85287 USA

来源：

DISTRIBUTED COMPUTING | 2000年 / 13卷 / 01期

关键词：

distributed systems; quorums; fault tolerance; Byzantine failures; load;

D O I：

10.1007/s004460050004

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Quorum systems have been used to implement many coordination problems in distributed systems such as mutual exclusion, data replication, distributed consensus, and commit protocols. Malkhi and Reiter recently proposed quorum systems that can tolerate Byzantine failures; they called these systems Byzantine quorum systems and gave some examples of such quorum systems. In this paper, we propose a new definition of Byzantine quorums that is appropriate for synchronous systems. We show how these quorums can be used for data replication and propose a general construction of synchronous Byzantine quorums using standard quorum systems. We prove tight lower bounds on the load of synchronous Byzantine quorums for various patterns of failures and we present synchronous Byzantine quorums that have optimal loads that match the lower bounds for two failure patterns.

引用

页码：45 / 52

页数：8

共 22 条

[1] AN EFFICIENT AND FAULT-TOLERANT SOLUTION FOR DISTRIBUTED MUTUAL EXCLUSION
AGRAWAL, D
ELABBADI, A
[J]. ACM TRANSACTIONS ON COMPUTER SYSTEMS, 1991, 9 (01): : 1 - 20
[2] Bazzi R. A., 1997, Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing, P259, DOI 10.1145/259380.259454
[3] BAZZI RA, 1996, P 10 INT WORKSH DIST, P251
[4] GARCIAMOLINA H, 1985, J ACM, V32, P481
[5] Gifford D. K., 1979, Proceedings of the Seventh Symposium on Operating Systems Principles, P150, DOI 10.1145/800215.806583
[6] Helal A.A., 1996, REPLICATION TECHNIQU
[7] HERLIHY MP, 1984, THESIS MIT
[8] A THEORY OF COTERIES - MUTUAL EXCLUSION IN DISTRIBUTED SYSTEMS
IBARAKI, T
KAMEDA, T
[J]. IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1993, 4 (07) : 779 - 794
[9] HIERARCHICAL QUORUM CONSENSUS - A NEW ALGORITHM FOR MANAGING REPLICATED DATA
KUMAR, A
[J]. IEEE TRANSACTIONS ON COMPUTERS, 1991, 40 (09) : 996 - 1004
[10] Kumar A., 1993, Proceedings the 13th International Conference on Distributed Computing Systems (Cat. No.93CH3282-1), P178, DOI 10.1109/ICDCS.1993.287710

← 1 2 3 →