Chương 313: Thuật Toán Chịu Lỗi Byzantine

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

“Ví như, hiện có năm vị tướng quân, trong đó hai vị cho rằng nên tiến công, còn hai vị khác lại chủ trương rút lui.

Lúc này, vị tướng quân thứ năm là kẻ phản bội. Hắn nói với tướng quân muốn tiến công rằng ‘ta cũng sẽ tiến công’, rồi lại nói với tướng quân muốn rút lui rằng ‘ta cũng sẽ rút lui’.

Thế là, các tướng quân muốn tiến công tin rằng, hiện có ba đạo quân đồng ý tiến công, đã quá bán, vậy nên ngày mai ắt phải tiến công.

Còn các tướng quân muốn rút lui thì vẫn giữ ý định rút lui.

Kết cục cuối cùng, hai tướng quân tiến công, hai tướng quân rút lui, dẫn đến chiến bại thảm hại.

Đây chính là vấn đề nảy sinh từ ‘phi tập trung hóa’. Bởi lẽ, năm vị tướng quân này đều ngang cấp, không có một người chỉ huy nào sở hữu quyền lực tuyệt đối, nên trong quá trình bàn bạc sách lược, vấn đề như vậy ắt sẽ phát sinh.”

Trịnh Kiệt chợt gật đầu: “Thì ra là vậy! Vậy cách này giải quyết thế nào? Cũng chẳng thể xác minh được tướng quân nào đang nói dối?”

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

Giả sử ta là một trong số các tướng quân A, và tướng quân B nói với ta rằng hắn sẽ cùng ta tiến công.

Nếu ta tin lời, rất có thể sẽ bị lừa, bởi tướng quân B có thể là kẻ phản bội, hắn có thể chỉ nói với ta là tiến công, nhưng lại nói với người khác là rút lui.

Vậy nên, lúc này ta nên hỏi lại tướng quân C, ta hỏi hắn: ‘Tướng quân B nói với ngươi là tiến công hay rút lui?’

Sau đó, ta sẽ lần lượt hỏi tất cả các tướng quân khác, tổng hợp lại mọi thông tin mà tướng quân B đã nói với họ.

Những thông tin mà các tướng quân khác nói với ta về ‘thông tin của tướng quân B’ cũng chưa chắc đã thật, bởi trong số các tướng quân khác cũng có thể có kẻ phản bội. Có thể xảy ra trường hợp ‘tướng quân B nói với họ là tiến công, nhưng họ lại nói với ta rằng tướng quân B đã nói rút lui’.

Vậy nên, ta lần lượt hỏi từng người ‘tướng quân B đã nói gì với các ngươi’, nếu ‘tiến công’ chiếm đa số, thì ta sẽ ghi nhận ý kiến của tướng quân B là ‘tiến công’;

Sau đó, ta lại lần lượt hỏi từng người ‘tướng quân C đã nói gì với các ngươi’, nếu ‘rút lui’ chiếm đa số, thì ta sẽ ghi nhận ý kiến của tướng quân C là ‘rút lui’.

Cứ như vậy, ta thông qua phương thức lặp đi lặp lại, không ngừng loại bỏ các đáp án thiểu số, cuối cùng sẽ có được kết luận chính xác hơn, đó là ‘đáp án của đa số’.

Trong trường hợp thỏa mãn ‘chịu lỗi Byzantine’, chúng ta buộc tất cả các tướng quân phải tuân thủ bộ sách lược này, và phải kiên quyết chấp hành kết luận cuối cùng.

Khi đó, chúng ta có thể đảm bảo mọi người cùng tiến công hoặc cùng rút lui.”

Trịnh Kiệt có chút bối rối: “Trong trường hợp thỏa mãn ‘chịu lỗi Byzantine’? Tức là như Thái huynh đã nói trước đó, 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 3 tướng quân:

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

Tướng quân A sẽ trước tiên nói ‘tiến công’ với tướng quân B và C.

Nhưng tướng quân B sau khi nhận lệnh không thể xác nhận tướng quân A có phải là kẻ phản bội hay không, nên hắn phải hỏi tướng quân C, ‘lệnh mà tướng quân A đưa cho ngươi là gì’, và tướng quân C là kẻ phản bội, nên sẽ cố ý nói ‘lệnh mà tướng quân A đưa cho ta là rút lui’.

Vì chỉ có ba tướng quân, nên tướng quân B không thể phán đoán được tướng quân A và tướng quân C rốt cuộc ai là kẻ phản bội, bởi vì lệnh ‘tiến công’ và ‘rút lui’ mỗi bên một phiếu, không thể hình thành đa số.

Tương tự, khi tướng quân B thực hiện sách lược này, cũng không thể phán đoán được tướng quân A và tướng quân C ai là kẻ phản bội.

Đây là trường hợp đơn giản nhất. Nếu số lượng tướng quân tăng lên, ví dụ như có 7 tướng quân cùng lúc, trong đó có 2 kẻ phản bội, tình hình sẽ trở nên phức tạp hơn rất nhiều, cần phải lặp đi lặp lại nhiều lần mới có thể đi đến kết luận cuối cùng.

Vì vậy ta mới nói, vấn đề này không cần tự mình suy luận, chỉ cần ghi 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ẽ không thể giải quyết được.

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

Áp dụng vào số lượng người trong ba căn phòng, sẽ thấy rõ ngay.

‘Phòng 4 Người’, 3 người trả lời, vậy nên chỉ cần có 1 Tự Do Nhân ác ý, vấn đề này sẽ không thể giải quyết.

‘Phòng 8 Người’, 7 người trả lời, trong trường hợp có 3 Tự Do Nhân ác ý trong phòng, sẽ không thể giải quyết.

‘Phòng 13 Người’, 12 người trả lời, trong trường hợp có 4 Tự Do Nhân ác ý trong phòng, sẽ không thể giải quyết.”

Trịnh Kiệt chợt vỡ lẽ: “Thì ra là vậy!

Vậy nên Thái huynh đã dùng công thức này để suy luận, lập tức biết được ‘Phòng 8 Người’ thực ra là an toàn nhất, bởi vì chúng ta chỉ cần cử 1 Tự Do Nhân phe mình vào chiếm chỗ, vấn đề này nhất định sẽ giải quyết được.”

Tần Dao vẫn chưa hiểu: “Khoan đã, tuy ta vẫn chưa hiểu rõ lắm, nhưng công thức này ta đã nhớ rồi.

Vấn đề của ta 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 xung phong nói: “Để ta giải thích!

Ở giai đoạn thứ hai, sau khi vào phòng, thực chất là cuộc đấu trí giữa ‘Đáp Tích Nhân’ và ‘Xuất Đề Nhân’.

Ví dụ, chúng ta lập ‘hắc điếm’ trong ‘Phòng 8 Người’, tức là chúng ta sẽ đóng vai ‘Đáp Tích Nhân’, còn những người chơi từ các Cộng Đồng khác vào sau sẽ đóng vai ‘Xuất Đề Nhân’.

Mục tiêu của phe ‘Đáp Tích Nhân’ chúng ta là đạt được sự đồng thuận về lựa chọn, để có thể nhận được phần thưởng thêm, kiếm thời gian visa từ ‘Xuất Đề Nhân’;

Ngược lại, mục tiêu của phe ‘Xuất Đề Nhân’ là khiến chúng ta không thể đạt được sự đồng thuận.

Cách đơn giản hơn là, những người chơi bình thường thuộc phe ‘Xuất Đề Nhân’, chỉ cần cố ý 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 quy tắc phòng, buộc những người chơi này phải đưa ra lựa chọn của đa số.

Chức năng ‘Gửi Đề Xuất’ thực chất đang mô phỏng quá trình tính toán của ‘Thuật Toán Chịu Lỗi Byzantine’. Mỗi người chơi đều phải bắt buộc gửi đề xuất của đa số hiện tại, nhưng sẽ có một khoảng thời gian nhất định.

Vì vậy, sau khi gửi đi gửi lại nhiều lần, trừ Tự Do Nhân ra, tất cả đề xuất của Đáp Tích Nhân bình thường sẽ trở thành cùng một lựa chọn.

Sau đó, quy tắc trò chơi sẽ buộc những người chơi này phải gửi lựa chọn đó, từ đó đạt được mục tiêu ‘toàn viên nhất trí’.

Nhưng như Thái huynh đã nói, quá trình mô phỏng ‘Gửi Đề Xuất’ bản thân nó cần ‘đề xuất của đa số đạt đến một số lượng nhất định’ mới có thể thành lập.

Người chơi ‘Tự Do Nhân’ thực chất đóng vai ‘nút ác ý’ và ‘kẻ phản bội’, họ sẽ liên tục gửi đề xuất của thiểu số để làm nhiễu loạn quá trình tính toán.

Giả sử những ‘Tự Do Nhân’ ác ý này khá nhiều, thì có thể xảy ra tình huống như sau:

Lúc này vốn dĩ đề xuất A đang chiếm đa số, nhưng đột nhiên xuất hiện rất nhiều đề xuất B vượt lên, khiến một số người chơi chuyển sang đề xuất B, rồi lại đột nhiên xuất hiện một số đề xuất A…

Điều này sẽ khiến các đề xuất mà người chơi gửi đi liên tục thay đổi, không thể cố định được. Vậy thì khi chức năng ‘Gửi Đề Xuất’ kết thúc, một số người chơi gửi A, một số người chơi gửi B, mọi người sẽ không thể đạt được sự đồng thuận.

Phe ‘Đáp Tích Nhân’ không thể ổn định buộc ‘Xuất Đề Nhân’ liên tục thua, không thể ổn định thu lợi nhuận, vậy thì tương đương với việc, hắc điếm đã bị phá hủy.”

Thái Chí Viễn gật đầu: “Đúng vậy, vậy nên chỉ cần thông qua công thức xác định điều kiện ‘chịu lỗi Byzantine’ thành lập, rồi so sánh với số lượng Tự Do Nhân có thể vào từng phòng, là có thể xác định chiến lược vào phòng.

‘Phòng 8 Người’ cho phép 3 ‘Tự Do Nhân’ vào, vấn đề này sẽ không thể giải quyết khi xuất hiện 3 kẻ phản bội. Vì vậy, chúng ta chỉ cần đảm bảo trong phòng có 1 ‘Tự Do Nhân’ phe ta chiếm chỗ, là an toàn rồi.

Đương nhiên, ‘Tự Do Nhân’ phe ta này phải là người thiện ý, tức là hắn sẽ chủ động thực hiện chiến lược ‘gửi đề xuất đa số’.

‘Phòng 13 Người’ cho phép 6 Tự Do Nhân vào, vấn đề này sẽ không thể giải quyết khi xuất hiện 4 kẻ phản bội, vậy nên Vương Vệ Đông phải đảm bảo số lượng Tự Do Nhân ác ý cuối cùng vào ‘Phòng 13 Người’ phải dưới 4 người.

Vì vậy, số lượng ‘Tự Do Nhân thiện ý’ mà họ cần để chiếm chỗ phải nhiều hơn.

Nếu họ không nhận thức được điều này, chúng ta cũng có thể chọn chủ động tấn công. Nhưng vì Vương Vệ Đông đã nhận thức được và thực hiện phòng thủ, việc cố gắng tấn công mạnh mẽ sẽ không còn ý nghĩa lớn.

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

Cầu nguyệt phiếu.