Проблема двух генералов

Введение

Мысленный эксперимент

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

Определение

Две армии, возглавляемые разными генералами, готовятся к нападению на укреплённый город. Армии расположились лагерем вблизи города, каждая в своей долине. Третья долина разделяет эти два холма, и единственный способ для генералов общаться – отправлять гонцов через долину. К сожалению, долина занята защитниками города, и существует вероятность, что любой отправленный гонец будет захвачен. Хотя генералы договорились о нападении, они не согласовали время его начала. Для успеха необходимо, чтобы обе армии атаковали город одновременно, иначе армия, атакующая в одиночку, будет уничтожена. Таким образом, им необходимо общаться друг с другом, чтобы определить время нападения и договориться о нём, и каждый генерал должен быть уверен, что другой генерал знает об их согласии относительно плана нападения. Поскольку подтверждение получения сообщения может быть потеряно так же легко, как и само сообщение, для достижения консенсуса может потребоваться потенциально бесконечная серия сообщений. Мысленный эксперимент заключается в рассмотрении того, как они могут прийти к согласию. В простейшем случае, один генерал известен как лидер, определяет время нападения и должен сообщить его другому генералу. Задача состоит в том, чтобы разработать алгоритмы, которые генералы могут использовать – включая отправку и обработку сообщений – чтобы они могли правильно заключить:

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

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

Первый генерал может начать с отправки сообщения: "Нападение 4 августа в 09:00". Однако, как только сообщение отправлено, первый генерал не имеет понятия, дошло ли оно до адресата. Эта неопределенность может заставить первого генерала колебаться с началом атаки из-за риска остаться единственным, кто нападает. Чтобы развеять сомнения, второй генерал может отправить подтверждение первому: "Я получил ваше сообщение и начну атаку 4 августа в 09:00". Однако посланник с подтверждением может быть захвачен, и второй генерал может засомневаться, зная, что первый может воздержаться от атаки, не получив подтверждения. Кажется, что дальнейшие подтверждения могут решить проблему – пусть первый генерал отправит второе подтверждение: "Я получил ваше подтверждение запланированной атаки 4 августа в 09:00". Однако и этот новый посланник от первого генерала также может быть захвачен. Таким образом, быстро становится ясно, что каким бы большим ни было количество раундов подтверждений, невозможно гарантировать, что каждый генерал уверен в согласии другого на план атаки. Оба генерала всегда будут сомневаться, дошло ли до адресата их последнее сообщение.

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

Поскольку этот протокол детерминирован, предположим, что существует последовательность сообщений фиксированной длины, в которой одно или несколько сообщений доставлено успешно, а одно или несколько – нет. Предполагается, что оба генерала должны прийти к общей уверенности в необходимости атаковать. Рассмотрим последнее сообщение из этой последовательности, которое было успешно доставлено. Если бы это последнее сообщение не было успешно доставлено, то по крайней мере один генерал (вероятно, получатель) принял бы решение не атаковать. Однако, с точки зрения отправителя этого последнего сообщения, последовательность отправленных и доставленных сообщений была бы точно такой же, как если бы сообщение было доставлено. Поскольку протокол детерминирован, генерал, отправивший последнее сообщение, все равно принял бы решение атаковать. Таким образом, мы пришли к ситуации, когда предложенный протокол приводит одного генерала к атаке, а другого – к отказу от нее, что противоречит предположению о том, что протокол является решением проблемы. Недетерминированный протокол с потенциально переменным количеством сообщений можно представить в виде конечного дерева с помеченными ребрами, где каждый узел дерева представляет собой исследованный пример на определенном этапе. Протокол, завершающийся до отправки каких-либо сообщений, представлен деревом, содержащим только корневой узел. Ребра, идущие от узла к каждому дочернему узлу, помечены сообщениями, отправленными для достижения соответствующего состояния. Листовые узлы представляют собой точки, в которых протокол завершается. Предположим, существует недетерминированный протокол P, решающий проблему двух генералов. Тогда, используя аналогичный аргумент, как и для детерминированных протоколов фиксированной длины, протокол P' также должен решать проблему двух генералов, причем дерево, представляющее P', получается из дерева для P путем удаления всех листовых узлов и ребер, ведущих к ним. Поскольку P конечен, следует, что протокол, завершающийся до отправки каких-либо сообщений, также решит проблему. Но это очевидно не так. Следовательно, недетерминированный протокол, решающий проблему, не может существовать.

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

Прагматичный подход к решению проблемы двух генералов заключается в использовании схем, которые учитывают неопределенность канала связи и не пытаются ее устранить, а скорее снижают ее до приемлемого уровня. Например, первый генерал мог бы отправить 100 гонцов, предполагая, что вероятность перехвата всех мала. При таком подходе первый генерал будет атаковать в любом случае, а второй генерал – если получит хотя бы одно сообщение. В качестве альтернативы, первый генерал мог бы отправлять поток сообщений, а второй – подтверждения получения каждого из них, при этом каждый генерал будет чувствовать себя увереннее с каждым полученным сообщением. Однако, как следует из доказательства, ни один из них не может быть уверен в координации атаки. Не существует алгоритма (например, атаковать, если получено более четырех сообщений), который гарантированно предотвратит атаку одного генерала без другого. Кроме того, первый генерал может добавлять к каждому сообщению номер – сообщение 1, 2, 3 из n. Это позволит второму генералу оценить надежность канала и отправить обратно соответствующее количество сообщений, чтобы обеспечить высокую вероятность получения хотя бы одного. Если канал достаточно надежен, то одного сообщения будет достаточно, а дополнительные не дадут преимущества. Последнее сообщение столь же вероятно может быть потеряно, как и первое. Если каждый раз, когда гонец отправляется и перехватывается, генералы несут потери, можно разработать алгоритм, минимизирующий число необходимых гонцов для достижения максимальной уверенности в координации атаки. Чтобы избежать гибели сотен гонцов ради очень высокой уверенности в координации, генералы могут договориться считать отсутствие гонцов сигналом о том, что генерал, инициировавший операцию, получил хотя бы одно подтверждение и обещал атаковать. Предположим, гонцу требуется 1 минута, чтобы пересечь опасную зону. Тогда 200 минут молчания после получения подтверждений позволят достичь чрезвычайно высокой уверенности, не жертвуя жизнями гонцов. В этом случае гонцы используются только в том случае, если одна из сторон не получила сигнала о времени атаки. По истечении 200 минут каждый генерал может рассуждать так: "Я не получал дополнительных сообщений в течение 200 минут; либо 200 гонцов не смогли пересечь опасную зону, либо это означает, что другой генерал подтвердил и принял решение об атаке, и уверен, что я тоже".

A pragmatic approach to dealing with the Two Generals' Problem is to use schemes that accept the uncertainty of the communications channel and not attempt to eliminate it, but rather mitigate it to an acceptable degree. For example, the first general could send 100 messengers, anticipating that the probability of all being captured is low. With this approach, the first general will attack no matter what, and the second general will attack if any message is received. Alternatively, the first general could send a stream of messages and the second general could send acknowledgments to each, with each general feeling more comfortable with every message received. As seen in the proof, however, neither can be certain that the attack will be coordinated. There is no algorithm that they can use (e. g. attack if more than four messages are received) that will be certain to prevent one from attacking without the other. Also, the first general can send a marking on each message saying it is message 1, 2, 3 of n. This method will allow the second general to know how reliable the channel is and send an appropriate number of messages back to ensure a high probability of at least one message being received. If the channel can be made to be reliable, then one message will suffice and additional messages do not help. The last is as likely to get lost as the first. Assuming that the generals must sacrifice lives every time a messenger is sent and intercepted, an algorithm can be designed to minimize the number of messengers required to achieve the maximum amount of confidence the attack is coordinated. To save them from sacrificing hundreds of lives to achieve very high confidence in coordination, the generals could agree to use the absence of messengers as an indication that the general who began the transaction has received at least one confirmation and has promised to attack. Suppose it takes a messenger 1 minute to cross the danger zone, allowing 200 minutes of silence to occur after confirmations have been received will allow us to achieve extremely high confidence while not sacrificing messenger lives. In this case, messengers are used only in the case where a party has not received the attack time. At the end of 200 minutes, each general can reason: "I have not received an additional message for 200 minutes; either 200 messengers failed to cross the danger zone, or it means the other general has confirmed and committed to the attack and has confidence I will too".

История

Проблема двух генералов и ее доказательство невозможности были впервые опубликованы Э. А. Аккоюнлу, К. Эканадамом и Р. В. Губером в 1975 году в работе "Некоторые ограничения и компромиссы при проектировании сетевых коммуникаций", где она описана, начиная со страницы 73, в контексте связи между двумя группами бандитов. Джим Грей в 1978 году в работе "Заметки об операционных системах баз данных", начиная со страницы 465, дал этой проблеме название "Парадокс двух генералов". Несмотря на то, что оба – определение проблемы и доказательство невозможности – были опубликованы ранее, как указано выше, эта работа часто цитируется как основной источник для их понимания.