Hệ thống quorum Byzantine đồng bộ

Distributed Computing - Tập 13 - Trang 45-52 - 2000
Rida A. Bazzi1
1Department of Computer Science and Engineering, Arizona State University, Tempe, AZ 85287-5406, USA (e-mail: [email protected]), , US

Tóm tắt

Các hệ thống quorum đã được sử dụng để triển khai nhiều vấn đề phối hợp trong các hệ thống phân tán, chẳng hạn như loại trừ lẫn nhau, sao chép dữ liệu, đồng thuận phân tán và các giao thức cam kết. Malkhi và Reiter gần đây đã đề xuất các hệ thống quorum có khả năng chịu đựng các lỗi Byzantine; họ gọi những hệ thống này là hệ thống quorum Byzantine và cung cấp một số ví dụ về các hệ thống quorum như vậy. Trong bài báo này, chúng tôi đề xuất một định nghĩa mới về các quorum Byzantine phù hợp với các hệ thống đồng bộ. Chúng tôi chỉ ra cách mà các quorum này có thể được sử dụng cho việc sao chép dữ liệu và đề xuất một cấu trúc tổng quát của các quorum Byzantine đồng bộ sử dụng các hệ thống quorum chuẩn. Chúng tôi chứng minh những giới hạn tối thiểu chặt chẽ về tải của các quorum Byzantine đồng bộ cho nhiều mẫu hình lỗi khác nhau và chúng tôi trình bày các quorum Byzantine đồng bộ có tải tối ưu phù hợp với các giới hạn tối thiểu cho hai mẫu hình lỗi.

Từ khóa

#Hệ thống quorum #lỗi Byzantine #sao chép dữ liệu #đồng thuận phân tán #tải tối ưu