Khi bạn nhắn cho một người bạn “Mai 3 giờ chiều gặp nhau trước nhà ga nhé” mà mãi không thấy trả lời, bạn sẽ thấy bồn chồn vì không biết người đó đã đọc tin nhắn chưa. Ngay cả khi nhận được câu trả lời “OK”, lần này bạn lại có thể băn khoăn liệu người kia có biết là bạn đã nhận được câu trả lời đó hay không. Trong khoa học máy tính có một bài toán nổi tiếng giải thích vòng lặp xác nhận vô tận này bằng câu chuyện về hai vị tướng. Đó chính là ‘Bài toán hai vị tướng (Two Generals’ Problem)’.
Nói một cách đơn giản, Bài toán hai vị tướng là một thí nghiệm tư duy cho thấy ‘trên một kênh liên lạc mà tin nhắn có thể biến mất giữa đường, hai bên không bao giờ có thể hoàn toàn chắc chắn rằng họ đã thống nhất cùng một hành động’. Bài toán này hầu như luôn xuất hiện khi người ta mới học về mạng và hệ thống phân tán, và được xem là bài toán truyền thông máy tính đầu tiên được chứng minh là không thể giải được.
Trong bài viết này, chúng ta sẽ lần lượt tìm hiểu Bài toán hai vị tướng mô tả tình huống gì, vì sao nó không thể giải được, bài toán này bắt nguồn từ đâu và công nghệ thực tế xử lý giới hạn này như thế nào.
Bài toán hai vị tướng: Khi xác nhận của xác nhận không bao giờ kết thúc
Bài toán hai vị tướng mô tả tình huống gì?
Bài toán bắt đầu bằng câu chuyện về hai đạo quân bị ngăn cách bởi một tòa lâu đài.
(1) Hai đạo quân đóng trại riêng rẽ
Hai đạo quân do hai vị tướng chỉ huy đóng trại trên hai ngọn đồi khác nhau để tấn công cùng một tòa lâu đài. Nếu hai đạo quân tấn công cùng lúc, họ có thể chiếm được lâu đài, nhưng nếu chỉ một bên tấn công, đạo quân đó sẽ thua thảm hại.
(2) Người đưa tin vượt qua thung lũng nguy hiểm
Cách duy nhất để hai vị tướng liên lạc với nhau là cử người đưa tin đi qua thung lũng do quân trong lâu đài canh giữ. Người đưa tin có thể bị bắt bất cứ lúc nào, và bên gửi không có cách nào biết người đưa tin đã đến nơi hay chưa.
(3) Sự chắc chắn mà các vị tướng mong muốn
Các vị tướng không chỉ muốn định ra giờ tấn công mà còn muốn cả hai bên biết chắc chắn rằng ‘cả hai chúng ta sẽ cùng tấn công vào giờ đó’. Bởi chỉ khi có được sự chắc chắn này, họ mới có thể yên tâm điều quân.
Như vậy, Bài toán hai vị tướng gói gọn trong một khung cảnh đơn giản những khó khăn nảy sinh khi hai bên cố gắng phối hợp hành động trên một kênh liên lạc không đáng tin cậy.
Vì sao rốt cuộc vẫn không thể chắc chắn?
Có vẻ như chỉ cần trao đổi người đưa tin nhiều lần là giải quyết được, nhưng càng thêm xác nhận thì cùng một nỗi lo lại càng lặp lại.
(1) Nỗi bất an của tin nhắn đầu tiên
Ngay cả khi vị tướng thứ nhất cử người mang tin “Tấn công lúc 6 giờ sáng”, ông vẫn không biết người đưa tin đã đến nơi chưa, nên sẽ do dự vì sợ rằng chỉ mình mình tấn công.
(2) Những hồi âm nối tiếp không dứt
Nếu vị tướng thứ hai gửi hồi âm “Đã nhận, sẽ tấn công lúc 6 giờ”, thì lần này đến lượt vị tướng thứ hai lo lắng không biết hồi âm đó đã đến nơi chưa. Dù vị tướng thứ nhất lại gửi xác nhận rằng mình đã nhận được hồi âm, người đưa tin cuối cùng ấy cũng vẫn có thể bị bắt.
(3) Nghịch lý của người đưa tin cuối cùng
Dù trao đổi bao nhiêu lần, bên gửi cũng không thể biết người đưa tin cuối cùng đã đến nơi hay chưa. Ngay cả khi người đưa tin cuối cùng bị bắt, tình hình đối với bên gửi vẫn trông y hệt, nên nếu quyết định tấn công phụ thuộc vào đúng một người đưa tin đó, có thể xảy ra chuyện chỉ một bên tấn công. Vì vậy, người ta đi đến kết luận rằng không có phương pháp trao đổi xác nhận với số lần cố định nào có thể khiến hai vị tướng phối hợp hoàn hảo.
Điểm mấu chốt là tin nhắn xác nhận cũng có thể bị thất lạc dễ dàng như tin nhắn ban đầu. Dù có chồng bao nhiêu lớp xác nhận đi nữa, sự bất định của lớp cuối cùng vẫn còn nguyên.
Bài toán hai vị tướng bắt nguồn từ đâu?
Bài toán này được hệ thống hóa vào những năm 1970, khi mạng máy tính vừa bắt đầu phát triển.
- Bài báo công bố đầu tiên (First Publication): Năm 1975, E. A. Akkoyunlu, K. Ekanadham và R. V. Huber lần đầu trình bày bài toán này cùng chứng minh rằng nó không thể giải được, trong một bài báo bàn về các ràng buộc trong thiết kế truyền thông mạng. Trong bài báo đó, tình huống được mô tả không phải bằng các vị tướng mà bằng hai băng nhóm liên lạc với nhau.
- Người đặt tên (Naming): Nhà nghiên cứu cơ sở dữ liệu Jim Gray đã gọi bài toán này là ‘Nghịch lý hai vị tướng (Two Generals Paradox)’ trong một bài viết năm 1978 về hệ điều hành cơ sở dữ liệu, và từ đó nó được biết đến rộng rãi qua câu chuyện về các vị tướng như ngày nay.
- Mở rộng thành bài toán lớn hơn (Byzantine Generals Problem): Năm 1982, Leslie Lamport, Robert Shostak và Marshall Pease công bố ‘Bài toán các vị tướng Byzantine’, đề cập đến tình huống có kẻ phản bội lẫn trong số nhiều vị tướng. Bài toán hai vị tướng thường được giới thiệu như phần nhập môn trước khi học bài toán này.
Công nghệ thực tế xử lý giới hạn này như thế nào?
Nếu sự chắc chắn tuyệt đối là không thể, công nghệ thực tế chọn cách giảm sự bất định xuống mức có thể chấp nhận được thay vì loại bỏ nó.
(1) Gửi nhiều lần
Nếu vị tướng thứ nhất cử nhiều người đưa tin, xác suất tất cả đều bị bắt sẽ giảm mạnh. Dù không phải là chắc chắn, cách này vẫn có thể nâng khả năng thành công lên đủ cao.
(2) Xác nhận và gửi lại
TCP (Transmission Control Protocol), giao thức truyền thông cơ bản của Internet, trao đổi ba tin nhắn khi thiết lập kết nối, và sau khi gửi dữ liệu, nếu xác nhận đã nhận không đến trong một khoảng thời gian định sẵn thì sẽ gửi lại. Cách này cũng không thể bảo đảm trạng thái của hai bên luôn giống nhau, nhưng tạo ra độ tin cậy đủ để sử dụng trong thực tế.
(3) Dùng cả sự im lặng làm tín hiệu
Cũng có cách thỏa thuận trước rằng nếu không có liên lạc nào trong một khoảng thời gian nhất định thì coi như bên kia đã chấp nhận kế hoạch. Cách này giúp cử ít người đưa tin hơn mà vẫn đạt được mức độ chắc chắn cao.
Điểm chung của tất cả các cách này là hướng tới mục tiêu ‘đủ đáng tin cậy’ thay vì sự hoàn hảo.
Bài toán hai vị tướng nhắc nhở chúng ta rằng dù công nghệ có tinh vi đến đâu cũng không thể hoàn toàn vượt qua giới hạn của một kênh liên lạc không đáng tin cậy. Các ứng dụng nhắn tin, hệ thống thanh toán và dịch vụ đám mây mà chúng ta dùng ngày nay cũng được thiết kế trên cơ sở thừa nhận giới hạn này.
Chấp nhận rằng sự chắc chắn tuyệt đối là không thể và xây dựng các cơ chế an toàn trên nền tảng đó, đó chính là bước đầu tiên để thiết kế một hệ thống đáng tin cậy.
