Bài toán hai vị tướng (Two Generals Problem) là một bài toán không có lời giải, một trong những vấn đề đau đầu trong ngành khoa học máy tính về đường truyền tin cậy, xử lý lỗi trong một hệ phân tán.
Có nhiều tên gọi tiếng Anh khác nhau của bài toán này như: Two Generals Paradox, Two Armies Problem, hay là Coordinated Attack Problem.

Bài toán suy rộng từ bài toán này: Bài toán các vị tướng Byzantine cũng được coi là một bài toán không có lời giải.

Nội dung bài toán

Có 2 đạo quân, lãnh đạo bởi 2 vị tướng khác nhau, cùng hiệp lực bao vây tấn công 1 thành trì của quân địch.
Hai đạo quân này mỗi đạo bao vây một mạn thành, đóng quân tại 2 thung lũng gần đó. Để thông tin liên lạc giữa hai đạo quân, người đưa tin bắt buộc phải đi qua thung lũng nằm giữa, cũng chính là địa điểm của thành phố quân địch đang cư trú.

Tình huống đặt ra, quân địch khá mạnh.
Để giành được phần thắng, hai đạo quân cần hợp lực tấn công vào cũng một thời điểm, nếu không sẽ thất bại. Đặt ra nhu cầu phải dùng người đưa tin để thông tin liên lạc giữa hai bên.
Hai vị tướng cần liên lạc để thống nhất thời gian tấn công, tướng này phải biết được là tướng kia đã biết và đồng ý với quyết định.
Người đưa tin phải đi qua vị trí quân địch nên tiềm tàng khả năng người đưa tin bị bắt không tới được nơi, hoặc xấu hơn là tin nhắn bị giả mạo.

Giả sử liên lạc diễn ra như sau:

  1. Tướng A gửi thông tin cho tướng B: “Tấn công lúc 9:00 pm ngày 17 tháng 1”.
    Sau khi gửi tin tướng A cần nhận được confirm của tướng B để biết chắc B đã nhận được tin và biết được giờ tấn công.
  2. Tướng B confirm lại: “Tôi đã nhận thông tin và đồng ý tấn công lúc 9:00 pm ngày 17 tháng 1”.
    Sẽ có khả năng tin nhắn của B không tới nơi, hoặc bị đánh tráo, dẫn tới A không tấn công nữa. Vì thế B cần nhận được confirm của A.
  3. Tướng A nhận được tin và confirm lại: “Tôi đã nhận confirm của bạn là sẽ tấn công vào lúc 9:00 pm ngày 17 tháng 1”.
    Sau khi gửi tin, A vẫn cần nhận thông tin confirm của B vì sẽ có khả năng B (ở step 2) không nhận được tin nhắn này, và nghi ngờ dẫn tới không tấn công. Nếu A tấn công sẽ trở thành người tấn công một mình.
  4. Tướng B nhận được tin và confirm lại.
    Sau khi gửi tin, B lại tiếp tục cần nhận thông tin confirm của A…

Số lần cần confirm trở thành vô cùng vì sẽ không có cách nào để biết chắc chắn rằng mỗi vị tướng đã biết chắc về quyết định của vị tướng kia.

Mỗi vị tướng sẽ luôn có một nghi ngờ rằng tin nhắn cuối cùng mình gửi đi không đến nơi, hoặc bị làm giả, và vị tướng còn lại sẽ không tấn công đúng theo kế hoạch. Dẫn tới nếu mình tấn công sẽ trở thành người tấn công một mình.