В вычислительной технике проблема двух генералов — это мысленный эксперимент, призванный проиллюстрировать ловушки и проблемы проектирования при попытке координировать действия, общаясь по ненадежной линии связи. В эксперименте два генерала могут общаться друг с другом, только отправляя посланника через вражескую территорию. Эксперимент спрашивает, как они могут достичь соглашения о времени начала атаки, зная, что любой посланник, которого они отправят, может быть схвачен.
Проблема двух генералов часто появляется как введение в более общую проблему византийских генералов на вводных занятиях по компьютерным сетям (особенно в отношении протокола управления передачей , где показано, что TCP не может гарантировать согласованность состояний между конечными точками и почему это так), хотя она применима к любому типу двусторонней связи, где возможны сбои связи. Ключевая концепция в эпистемической логике , эта проблема подчеркивает важность общих знаний . Некоторые авторы также называют это парадоксом двух генералов , проблемой двух армий или проблемой скоординированной атаки . [1] [2] Проблема двух генералов была первой проблемой компьютерной связи, неразрешимость которой была доказана. [3] Важным следствием этого доказательства является то, что обобщения, такие как проблема византийских генералов, также неразрешимы перед лицом произвольных сбоев связи, тем самым обеспечивая основу реалистичных ожиданий для любых протоколов распределенной согласованности.
Две армии , каждая из которых возглавляется своим генералом , готовятся атаковать укрепленный город. Армии расположились лагерем около города, каждая в своей долине. Третья долина разделяет два холма, и единственный способ для двух генералов общаться — это отправлять гонцов через долину. К сожалению, долина занята защитниками города, и есть вероятность, что любой посланник, отправленный через долину, будет схвачен. [4]
Хотя два генерала договорились, что они будут атаковать, они не договорились о времени для атаки. Требуется, чтобы армии двух генералов атаковали город одновременно, чтобы добиться успеха, иначе армия одинокого атакующего погибнет, пытаясь это сделать. Таким образом, они должны общаться друг с другом, чтобы решить, когда атаковать, и согласиться атаковать в это время, и каждый генерал должен знать, что другой генерал знает, что они согласились с планом атаки. Поскольку подтверждение получения сообщения может быть потеряно так же легко, как и исходное сообщение, для достижения консенсуса требуется потенциально бесконечная серия сообщений . [5]
Мысленный эксперимент включает рассмотрение того, как они могут прийти к консенсусу. В простейшей форме один генерал, как известно, является лидером, выбирает время атаки и должен сообщить это время другому генералу. Проблема заключается в том, чтобы придумать алгоритмы, которые генералы могут использовать, включая отправку сообщений и обработку полученных сообщений, что позволит им сделать правильный вывод:
Если допустить, что генералам довольно просто прийти к соглашению о времени атаки (т. е. одно успешное сообщение с успешным подтверждением), то тонкость проблемы двух генералов заключается в невозможности разработать алгоритмы, которые генералы могли бы использовать для безопасного согласия с приведенным выше утверждением. [ необходима цитата ]
Первый генерал может начать с отправки сообщения: «Атака в 09:00 4 августа». Однако после отправки первый генерал не имеет ни малейшего представления о том, дошло ли послание до него. Эта неопределенность может привести к тому, что первый генерал будет колебаться с атакой из-за риска оказаться единственным атакующим.
Конечно, второй генерал может отправить подтверждение первому: «Я получил ваше сообщение и нападу в 09:00 4 августа». Однако посыльный, доставивший подтверждение, может оказаться в плену, а второй генерал может колебаться, зная, что первый может воздержаться без подтверждения.
Дальнейшие подтверждения могут показаться решением — пусть первый генерал отправит второе подтверждение: «Я получил ваше подтверждение запланированной атаки в 09:00 4 августа». Однако этот новый посланник от первого генерала также может быть захвачен. Таким образом, быстро становится очевидным, что независимо от того, сколько раундов подтверждений будет сделано, нет способа гарантировать второе требование, что каждый генерал уверен, что другой согласился с планом атаки. Оба генерала всегда будут гадать, дошел ли их последний посланник. [6]
Поскольку этот протокол детерминирован , предположим, что есть последовательность из фиксированного числа сообщений, одно или несколько успешно доставленных и одно или несколько нет. Предполагается, что должна быть общая уверенность для обоих генералов атаковать . Рассмотрим последнее такое сообщение, которое было успешно доставлено. Если бы это последнее сообщение не было успешно доставлено, то по крайней мере один генерал (предположительно получатель) решил бы не атаковать. Однако с точки зрения отправителя этого последнего сообщения последовательность отправленных и доставленных сообщений точно такая же, какой она была бы, если бы это сообщение было доставлено. Поскольку протокол детерминирован, генерал, отправляющий это последнее сообщение, все равно решит атаковать. Теперь мы создали ситуацию, в которой предлагаемый протокол приводит одного генерала к атаке, а другого — к неатаке, что противоречит предположению, что протокол был решением проблемы.
Недетерминированный протокол с потенциально переменным количеством сообщений можно сравнить с конечным деревом с маркировкой ребер , где каждый узел в дереве представляет собой исследованный пример до указанной точки. Протокол, который завершается до отправки каких-либо сообщений, представлен деревом, содержащим только корневой узел. Ребра от узла до каждого дочернего элемента помечены сообщениями, отправленными для достижения дочернего состояния. Конечные узлы представляют собой точки, в которых протокол завершается. Предположим, что существует недетерминированный протокол P , который решает задачу двух генералов. Тогда, по рассуждению, аналогичному тому, что использовался для детерминированных протоколов фиксированной длины выше, P' также должен решить задачу двух генералов, где дерево, представляющее P', получается из дерева для P путем удаления всех конечных узлов и ребер, ведущих к ним. Поскольку P является конечным, то отсюда следует, что протокол, который завершается до отправки каких-либо сообщений, решит задачу. Но очевидно, что это не так. Следовательно, недетерминированный протокол, который решает задачу, не может существовать.
Прагматичный подход к решению проблемы двух генералов заключается в использовании схем, которые принимают неопределенность канала связи и не пытаются устранить ее, а скорее смягчают ее до приемлемой степени. Например, первый генерал может отправить 100 гонцов, ожидая, что вероятность того, что все будут захвачены, низка. При таком подходе первый генерал будет атаковать несмотря ни на что, а второй генерал будет атаковать, если будет получено какое-либо сообщение. В качестве альтернативы первый генерал может отправить поток сообщений, а второй генерал может отправить подтверждения каждому, причем каждый генерал будет чувствовать себя более комфортно с каждым полученным сообщением. Однако, как видно из доказательства, ни один из них не может быть уверен, что атака будет скоординированной. Нет алгоритма, который они могли бы использовать (например, атаковать, если получено более четырех сообщений), который наверняка предотвратит атаку одного без другого. Кроме того, первый генерал может отправить маркировку на каждое сообщение, говорящую, что это сообщение 1, 2, 3 ... из n. Этот метод позволит второму генералу узнать, насколько надежен канал, и отправить соответствующее количество сообщений обратно, чтобы обеспечить высокую вероятность получения хотя бы одного сообщения. Если канал можно сделать надежным, то одного сообщения будет достаточно, а дополнительные сообщения не помогут. Последнее с такой же вероятностью потеряется, как и первое.
Предполагая, что генералы должны жертвовать жизнями каждый раз, когда посыльный отправляется и перехватывается, можно разработать алгоритм, чтобы минимизировать количество посыльных, необходимых для достижения максимальной уверенности в координации атаки. Чтобы спасти их от жертвования сотнями жизней для достижения очень высокой уверенности в координации, генералы могли бы договориться использовать отсутствие посыльных как указание на то, что генерал, который начал транзакцию, получил по крайней мере одно подтверждение и пообещал атаковать. Предположим, что посыльному требуется 1 минута, чтобы пересечь опасную зону, и 200 минут тишины после получения подтверждений позволят нам достичь чрезвычайно высокой уверенности, не жертвуя жизнями посыльных. В этом случае посыльные используются только в том случае, если сторона не получила время атаки. По истечении 200 минут каждый генерал может рассуждать так: «Я не получал дополнительных сообщений в течение 200 минут; либо 200 посыльных не смогли пересечь опасную зону, либо это означает, что другой генерал подтвердил и взял на себя обязательство атаковать и уверен, что я тоже это сделаю».
Задача двух генералов и доказательство ее невозможности были впервые опубликованы Э. А. Аккоюнлу, К. Эканадхамом и Р. В. Хубером в 1975 году в работе «Некоторые ограничения и компромиссы при проектировании сетевых коммуникаций» [7] , где она описывается, начиная со страницы 73, в контексте общения между двумя группами гангстеров.
Джим Грей [8] в 1978 году в своей работе «Заметки об операционных системах баз данных» [9], начиная со страницы 465, дал этой проблеме название « Парадокс двух генералов » . Эта ссылка широко используется в качестве источника определения проблемы и доказательства невозможности, хотя оба они были опубликованы ранее, как упоминалось выше.
{{cite book}}: |journal=проигнорировано ( помощь ){{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )Онлайн-версия: Заметки об операционных системах баз данных. Portal.acm.org. Январь 1978 г. С. 393–481. ISBN 978-3-540-08755-7. Получено 2010-03-19 .