lore

Chương 322: Algoritme Tolerant Đối Với Lỗi của Byzantine

8,783 Nhấn vào nội dung để bình luận hoặc báo lỗi.

Thái Chí Viễn tiếp tục giải thích:

“Ví dụ, hiện tại có tổng cộng năm vị tướng, trong đó hai người cho rằng nên tấn công, còn hai người khác lại muốn rút lui.

“Lúc này, vị tướng thứ năm là kẻ phản bội; hắn nói với những tướng muốn tấn công rằng ‘Tôi cũng sẽ tấn công’, và nói với những tướng muốn rút lui rằng ‘Tôi cũng sẽ rút lui’.

“Vì vậy, những tướng muốn tấn công sẽ nghĩ rằng có ba đội quân đồng ý tấn công, tức là chiếm đa số, nên ngày mai họ sẽ tiến hành cuộc tấn công.

“Trong khi đó, những tướng muốn rút lui lại cho rằng ngày mai nên rút lui.

“Kết quả cuối cùng là hai tướng tấn công và hai tướng rút lui, dẫn đến thất bại của trận chiến.

“Đây chính là những vấn đề mà việc ‘phi tập trung quyền lực’ gây ra; vì năm vị tướng này đều ngang hàng nhau, không ai có quyền lực tuyệt đối để chỉ huy, nên trong quá trình thảo luận chiến lược với nhau, những vấn đề như thế này sẽ xảy ra.”

Trịnh Kiệt bỗng nhiên gật đầu: “À, hiểu rồi! Vậy làm thế nào để giải quyết vấn đề này đây? Cũng không thể kiểm tra được chính xác là vị tướng nào đang nói dối, phải không?”

Thái Chí Viễn giải thích: “Thực ra, việc giải quyết vấn đề này rất đơn giản: chỉ cần hỏi đi hỏi lại nhiều lần là được.

“Giả sử tôi là một trong những vị tướng đó, và tướng B nói với tôi rằng anh ấy sẽ cùng tôi tấn công.

“Nếu tôi tin vào lời anh ấy, thì có thể tôi sẽ bị lừa đảo, bởi vì tướng B có thể là kẻ phản bội; anh ta có thể chỉ nói với tôi là tấn công, nhưng lại nói với người khác là rút lui.

“Vì vậy, lúc này tôi nên hỏi tướng C xem: ‘Tướng B đã nói với các ngài là tấn công hay rút lui?’

“Sau đó, tôi tiếp tục hỏi từng vị tướng còn lại, tổng hợp tất cả thông tin mà tướng B đã cung cấp cho họ.

“Những thông tin mà các vị tướng khác cung cấp cho tôi cũng không chắc đã đúng sự thật, bởi vì trong số họ cũng có thể có kẻ phản bội; có thể xảy ra tình huống ‘tướng B nói với họ là tấn công, nhưng họ lại nói với tôi là rút lui’.

“Vì vậy, tôi hỏi từng người một xem ‘tướng B đã nói gì với các ngài’. Nếu có nhiều người trả lời là ‘tấn công’, thì tôi sẽ coi ý kiến của tướng B là ‘tấn công’;

“Sau đó, tôi lại hỏi từng người một xem ‘tướng C đã nói gì với các ngài’. Nếu có nhiều người trả lời là ‘rút lui’, thì tôi sẽ coi ý kiến của tướng C là ‘rút lui’.

“Chỉ bằng cách này, thông qua việc hỏi đi hỏi lại nhiều

“Vậy thì chúng ta có thể đảm bảo rằng mọi người sẽ cùng nhau tấn công hoặc cùng nhau rút lui.”

Trịnh Kiệt hơi bối rối: “Trong trường hợp đáp ứng được điều kiện ‘khả năng chống sai sót của Byzantine’ phải không? Nghĩa là, như anh Thái Chí Viễn đã nói trước đây, số lượng kẻ phản bội phải ít hơn một phần ba?”

Thái Chí Viễn gật đầu: “Đúng vậy.”

“Chúng ta hãy lấy ví dụ với tình huống có 3 vị tướng:

Giả sử trong số 3 vị tướng này, tướng C là kẻ phản bội và cố tình truyền đạt thông tin sai lệch.

Tướng A sẽ đầu tiên ra lệnh ‘tấn công’ cho tướng B và tướng C.

Nhưng sau khi nhận được lệnh, tướng B không thể xác định liệu tướng A có phải là kẻ phản bội hay không, vì vậy ông ấy sẽ hỏi tướng C: ‘Lệnh mà tướng A đưa cho anh là gì?’ Vì tướng C là kẻ phản bội, nên ông ta sẽ cố tình nói rằng: ‘Lệnh mà tướng A đưa cho tôi là rút lui.’

Vì chỉ có 3 vị tướng, nên tướng B không thể phân định được ai là kẻ phản bội giữa tướng A và tướng C; cả hai lệnh ‘tấn công’ và ‘rút lui’ đều có số phiếu ngang nhau, không thể tạo thành đa số để quyết định.

Tương tự, khi thực hiện chiến lược này, tướng B cũng không thể xác định được ai là kẻ phản bội giữa tướng A và tướng C.”

“Đây là trường hợp đơn giản nhất. Nếu số lượng tướng tăng lên, chẳng hạn có 7 vị tướng và trong đó có 2 người là kẻ phản bội, tình hình sẽ trở nên phức tạp hơn nhiều; cần phải áp dụng nhiều phép suy luận liên tiếp mới có thể đưa ra kết luận cuối cùng.”

“Vì vậy tôi mới nói rằng, không cần phải tự mình tính toán, chỉ cần nhớ kết luận là được.

Kết luận là: Khi số lượng kẻ phản bội đạt đến một phần ba hoặc nhiều hơn, vấn đề này sẽ trở nên không thể giải quyết được.

Ngược lại, nếu muốn giải quyết được vấn đề này, cần phải kiểm soát số lượng kẻ phản bội để nó ít hơn một phần ba.”

“Hãy thử áp dụng ví dụ về số lượng người trong các căn phòng xem sao:

– ‘Phòng 4 người’: Có 3 người trả lời câu hỏi; vì vậy chỉ cần có 1 người có ý đồ xấu, vấn đề này sẽ không thể giải quyết được.

– ‘Phòng 8 người’: Có 7 người trả lời câu hỏi; nếu trong phòng có 3 người có ý đồ xấu, vấn đề vẫn không thể giải quyết được.

– ‘Phòng 13 người’: Có 12 người trả lời câu hỏi; nếu trong phòng có 4 người có ý đồ xấu, vấn đề vẫn không thể giải quyết được.”

Trịnh Kiệt bỗng nhiên hiểu ra: “À, ra vậy!

Vì vậy, khi anh Thái Chí Viễn áp dụng công thức này, ngay lập tức anh ấy đã biết rằng ‘phòng 8 người’ thực sự là an toàn nhất; bởi vì chúng ta chỉ c

Tần Dao vẫn chưa hiểu rõ: “Khoan đã, mặc dù tôi vẫn còn khá mơ hồ, nhưng tôi đã ghi nhớ được công thức này rồi.

Câu hỏi của tôi bây giờ là: Vấn đề Byzantine này cụ thể được áp dụng vào quy tắc trò chơi như thế nào?”

Trịnh Kiệt tự nguyện lên tiếng: “Để tôi giải thích nhé!

Ở giai đoạn thứ hai, sau khi vào phòng, thực chất đó là cuộc đối đầu giữa ‘Người trả lời’ và ‘Người đặt câu hỏi’.

Ví dụ, nếu chúng ta mở một phòng chơi 8 người, thì chúng ta sẽ đóng vai ‘Người trả lời’, còn những người chơi khác mới vào phòng sẽ đóng vai ‘Người đặt câu hỏi’.

Mục tiêu của chúng ta, những người trả lời, là phải đạt được sự đồng thuận về một lựa chọn cụ thể, như vậy chúng ta sẽ nhận được phần thưởng bổ sung và giành được thêm thời gian để hoàn thành nhiệm vụ từ phía người đặt câu hỏi.

Ngược lại, mục tiêu của phía người đặt câu hỏi là ngăn chúng ta đạt được sự đồng thuận đó.

Cách đơn giản nhất là những người chơi thông thường trong phe người đặt câu hỏi chỉ cần cố tình chọn những lựa chọn khác với chúng ta là được.

Vì vậy, chúng ta mới cần thiết lập các quy tắc phòng chơi để buộc những người chơi này phải gửi đi lựa chọn đa số.

Chức năng ‘Gửi đề xuất’ thực chất là mô phỏng quá trình tính toán của thuật toán Byzantine Fault Tolerance: mỗi người chơi đều bắt buộc phải gửi đi lựa chọn đa số, nhưng việc gửi này sẽ được thực hiện với những khoảng thời gian cách nhau.

Sau nhiều lần gửi đề xuất như vậy, ngoại trừ những người chơi tự do, tất cả những người trả lời khác sẽ đều chọn cùng một lựa chọn.

Sau đó, quy tắc trò chơi sẽ buộc tất cả những người chơi này phải gửi đi lựa chọn đó, như vậy mục tiêu ‘toàn thể đồng thuận’ sẽ được thực hiện.

Nhưng như anh Cai đã nói, quá trình mô phỏng này chỉ có thể thành công khi có đủ số lượng lựa chọn đa số được gửi đi.

Những người chơi tự do thực chất đóng vai trò như những ‘nút xấu’ hay ‘kẻ phản bội’: họ sẽ liên tục gửi đi những lựa chọn thiểu số, nhằm gây rối cho quá trình tính toán.

Nếu có quá nhiều người chơi tự do như vậy, có thể sẽ xảy ra tình huống sau:

Ban đầu, lựa chọn A được chọn nhiều hơn, nhưng đột nhiên có rất nhiều người chọn lựa B, khiến một số người chơi thay đổi lựa chọn của mình sang B, sau đó lại có thêm một số người chọn A...

Điều này sẽ khiến những đề xuất mà các người chơi gửi đi liên tục thay đổi, không bao giờ đạt được sự đồng thuận. Khi thời hạn gửi đề xuất kết thúc, một số người chơi sẽ chọn A, một số khác sẽ chọn B, và vì vậy không ai có thể đạt

“Nếu bên ‘Người trả lời’ không thể ổn định ép buộc bên ‘Người đặt câu hỏi’ phải tiếp tục tham gia cuộc chơi liên tục, không thể kiếm được lợi nhuận một cách ổn định, thì điều đó giống như việc một cửa hàng bất hợp pháp bị phá dỡ vậy.”

Thái Chí Viễn gật đầu: “Đúng vậy. Vì vậy, chỉ cần xác định rõ các điều kiện để chiến thuật ‘Tolerance of Byzantium’ có thể áp dụng được, sau đó so sánh số lượng người tự do có thể vào từng phòng, chúng ta sẽ biết được chiến lược nào là phù hợp nhất để tham gia các phòng đó.”

“Trong ‘phòng 8 người’, chỉ cho phép 3 người tự do tham gia. Vấn đề sẽ trở nên phức tạp khi có 3 kẻ phản bội xuất hiện. Vì vậy, chúng ta chỉ cần đảm bảo rằng trong phòng có ít nhất 1 người tự do của phe mình chiếm một vị trí là sẽ an toàn.”

“Tất nhiên, người tự do này phải là người có ý tốt, tức là anh ta sẽ chủ động thực hiện chiến lược ‘gửi ra nhiều gợi ý nhất có thể’.”

“Trong ‘phòng 13 người’, chỉ cho phép 6 người tự do tham gia. Vấn đề sẽ trở nên phức tạp khi có 4 kẻ phản bội xuất hiện. Vì vậy, Vương Vệ Đông phải đảm bảo rằng số lượng người tự do có ý xấu tham gia ‘phòng 13 người’ phải ít hơn 4 người.”

“Vì vậy, họ cần nhiều người tự do có ý tốt hơn để chiếm các vị trí quan trọng.”

“Nếu họ không nhận ra điểm này, chúng ta cũng có thể chọn cách tấn công trước. Nhưng vì Vương Vệ Đông đã nhận ra vấn đề và đã áp dụng chiến lược phòng thủ, việc tấn công mạnh mẽ lúc này sẽ không còn mang lại nhiều ý nghĩa nữa.”

“Vì vậy, tôi đã thay đổi cách suy nghĩ của mình, đó là tận dụng ‘hình phạt trái với ý muốn’ của trò chơi này, đưa ra những vấn đề có thể khiến Vương Vệ Đông mất mặt trong cộng đồng, từ đó buộc anh ta phải hủy bỏ các quy tắc của phòng chơi.”

Xin hãy vote cho tôi nhé!

1/1 0%