Задача двух генералов (задача двух армий, проблема скоординированной атаки) — в вычислительной технике мысленный эксперимент, иллюстрирующий проблему синхронизации состояния двух систем по ненадежному каналу связи. Эта задача похожа на более общую задачу византийских генералов, хотя и была сформулирована позже ее. Задача часто упоминается в начале курса компьютерных сетей (в частности при рассмотрении протокола TCP). Название для этой задачи придумал Джим Грей.

Определение

Две армии, каждая под руководством своего генерала, готовятся к штурму города. Лагеря армий разделены вражеской территорией. Единственным средством связи для генералов является отправка посыльных через вражескую территорию, где они могут быть перехвачены.

Для успешного штурма генералы должны атаковать город одновременно. Атака одной армией обречена на поражение. Нужно разработать алгоритм обмена сообщениями, позволяет каждому генералу быть уверенным в согласовании времени атаки.

Иллюстрация проблемы

Первый генерал, отправив сообщение со временем атаки втором генералу, не может быть уверенным, что тот его получил, а ведь пока не получит от него сообщение.

В свою очередь, второй генерал получив сообщение со временем атаки и послав сообщение с подтверждением, не может быть уверенным, что первый генерал получит его подтверждение. Ему тоже необходимо подтверждение доставки своего сообщения.

Таким образом задача не имеет решения.

Доказательство от противного

Предположим, что существует некоторая минимальная последовательность доставленных или перехваченных сообщений, гарантирует обоим генералам уверенность в согласовании времени штурма. Рассмотрим последнее сообщение этой последовательности. Оно тоже может быть перехвачено. В таком случае его получателя не будет иметь подтверждение и может не начать атаку. В другой же генерала есть уверенность в согласованности действий, поэтому он начнет атаку. То есть, при существовании аглоритму согласования возможна ситуация поражения, противоречит предположению о существовании алгоритма.

Инженерный подход

Прагматичный подход к решению задачи не борется с устранением ненадежности канала связи, а сводит его до допустимого уровня.

К примеру:

  • Несмотря на то, что вероятность перехвата низкая, первый генерал отправляет 100 посыльных и атакует, второй генерал атакует, если он получает хотя бы одного посыльного.

Видео по теме

Изображения по теме

  • Задача двух генералов