Byzantine Generals’ Problem

[QC]

Mục lục

Vấn đề của các vị tướng Byzantine

Một tình huống mà thông tin liên lạc đòi hỏi sự đồng thuận về một chiến lược duy nhất từ ​​tất cả các thành viên trong một nhóm hoặc bên không thể được tin cậy hoặc xác minh.

Bài toán của các vị tướng Byzantine là một thí nghiệm tư duy nhằm giải quyết một câu hỏi quan trọng của khoa học máy tính: liệu có thể hình thành sự đồng thuận trong một mạng máy tính bao gồm các nút độc lập, phân bố theo địa lý không?

Vấn đề được đề xuất vào năm 1982 bởi các nhà nghiên cứu từ Viện Nghiên cứu Quốc tế SRI.

Sự việc diễn ra như sau: có một số tướng lĩnh Byzantine đang bao vây một thành phố. Họ chỉ có thể giao tiếp thông qua việc gửi sứ giả cho nhau. Các tướng lĩnh phải thống nhất một kế hoạch hành động chung: tấn công thành phố hay rút lui. Tuy nhiên, một số tướng lãnh phản bội, tích cực hoạt động chống lại việc hình thành sự đồng thuận; số lượng và danh tính của họ vẫn chưa được biết.

Câu hỏi được đặt ra bởi vấn đề là thuật toán ra quyết định mà các vị tướng nên sử dụng để đưa ra một kế hoạch chung – bất kể sự can thiệp của những kẻ phản bội – và liệu một thuật toán như vậy có tồn tại hay không.

Theo phân tích của chính các nhà nghiên cứu, một hệ thống như vậy thực sự khả thi, nhưng số lượng tướng lĩnh trung thành phải vượt quá 2/3. Ví dụ, trong một tình huống có ba vị tướng, một trong số đó là kẻ phản bội, những người trung thành không bao giờ có thể đảm bảo rằng họ sẽ đạt được sự nhất trí.

Vấn đề này rất liên quan đến tiền điện tử vì về bản chất, chúng là các hệ thống máy tính phân tán: chúng bao gồm các nút xử lý giao dịch độc lập với nhau và bất kỳ cơ quan trung ương nào và chỉ có thể giao tiếp từ xa. Họ là những “vị tướng” cần đạt được sự đồng thuận về những giao dịch đã diễn ra và khi nào.

Các nút có khả năng cung cấp dữ liệu bị lỗi về các giao dịch do lựa chọn hoặc do ngẫu nhiên và thông tin của chúng phải được sắp xếp. Bitcoin (BTC) và các loại tiền điện tử khác giải quyết vấn đề này thông qua các giải pháp kỹ thuật như thuật toán bằng chứng công việc và bằng chứng cổ phần.

Xem Khả năng chịu lỗi Byzantine (BFT).

Byzantine Generals’ Problem

A situation where communication that requires consensus on a single strategy from all members within a group or party cannot be trusted or verified.

The Byzantine Generals’ Problem is a thought experiment that deals with a key question of computer science: is it possible to form a consensus in a computer network composed of independent, geographically distributed nodes?

The problem was proposed in 1982 by researchers from the SRI International Research Institute.

It goes as follows: there are a number of Byzantine generals besieging a city. They can only communicate via sending messengers to each other. The generals must agree on a common plan of action: whether to attack the city or retreat. However, some of the generals are traitorous and actively working against the forming of a consensus; their number and identities are unknown.

The question posed by the problem is what decision-making algorithm the generals should use to devise a common plan — regardless of the traitors’ interference — and whether such an algorithm exists at all.

According to the researchers’ own analysis, such a system is indeed feasible, but the number of loyal generals must strictly exceed two-thirds. For example, in a situation with three generals, one of which is traitorous, the loyal ones can never guarantee that they will be able to reach a consensus.

This problem is highly relevant for cryptocurrencies as they are, in essence, distributed computer systems: they are composed of transaction-processing nodes that are independent of each other and any central authority and can only communicate remotely. They are the “generals” that need to reach a consensus about which transactions have taken place and when.

Nodes have the potential to supply faulty data about transactions either by choice or by accident, and their information must be sorted out. Bitcoin (BTC) and other cryptocurrencies solve this problem via technical solutions such as the proof-of-work and proof-of-stake algorithms.

See Byzantine Fault Tolerance (BFT).

Tìm kiếm thêm nhiều thông tin hữu ích khác trên VNEconomics

Generic selectors
Exact matches only
Search in title
Search in content
Post Type Selectors
Generic selectors
Exact matches only
Search in title
Search in content
Post Type Selectors

Kết nối với VNEconomics

Danh mục đầu tư của VNEs

Danh mục sản phẩm

- Quảng cáo -

Những nội dung hữu ích ngành Blockchain & Tiền mã hóa
Recent Posts