Bài toán các vị tướng Byzantine (Byzantine Generals) là một bài toán trong khoa học máy tính về đường truyền tin cậy, bộ xử lý lỗi trong một hệ phân tán.
Nội dung của bài toán này như sau:
Có N tướng cầm các cánh quân khác nha. Có M tướng phản bội, cố gắng ngăn cản các tướng khác làm theo thỏa thuận:
– 4 tướng muốn tấn công – 4 tướng muốn rút quân – 1 tướng phản bội nói với nhóm thứ nhất là muốn tấn công, nói với nhóm thứ 2 là muốn rút quân
Các tướng trung thành làm thế nào để đạt được thỏa thuận?
Một trong những cách giải quyết Byzantine Generals:
Nếu có M tướng phản bội, phải có ít nhất 2M+1 tướng trung thành. Như vậy tổng cộng sẽ có M+1 vòng trao đổi thông điệp. Tổng cộng cần có O(MN2) thông điệp trao đổi, việc này rất tốn kém.
This article uses material from the Wikipedia Tiếng Việt article Bài toán các vị tướng Byzantine, which is released under the Creative Commons Attribution-ShareAlike 3.0 license ("CC BY-SA 3.0"); additional terms may apply (view authors). Nội dung được phát hành theo CC BY-SA 4.0, ngoại trừ khi có ghi chú khác. Images, videos and audio are available under their respective licenses.
®Wikipedia is a registered trademark of the Wiki Foundation, Inc. Wiki Tiếng Việt (DUHOCTRUNGQUOC.VN) is an independent company and has no affiliation with Wiki Foundation.