WikiSort.ru - Не сортированное

В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники. Эта отметка установлена 7 июня 2011 года.

Задача двух генералов — в вычислительной технике мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния двух систем по ненадёжному каналу связи. Эта задача является частным случаем задачи византийских генералов^{[источник не указан 2749 дней]}, и часто рассматривается в рамках курса компьютерных сетей (в частности протокола TCP), хотя применима и к другим средствам связи. В литературе также иногда упоминается как задача двух армий.

Определение

Две армии, каждая руководимая своим генералом, готовятся к штурму города. Лагеря этих армий располагаются на двух холмах, разделённых долиной. Единственным способом связи между генералами является отправка посыльных с сообщениями через долину. Но долина занята противником и любой из посыльных может быть перехвачен. Проблема заключается в том, что, генералы заранее (пока была связь) приняли принципиальное решение о штурме, но не согласовали точное время штурма (время Ч).

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

Отметим, что достичь такого соглашения очень просто — достаточно одного сообщения с временем начала штурма и одного сообщения, подтверждающего получение первого. Сложность задачи заключается в невозможности разработать алгоритм гарантированного обмена этими сообщениями.

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

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

Доказательство

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

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

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