|
Здравствуйте, уважаемые эксперты тематики Computer science! Широко известен мысленный эксперимент о двух генералах, военные соединения которых находятся на холмах, разделяемых долиной с вражескими войсками, и которым нужно достичь соглашения об одновременной атаке
Также широко известно, что такая задача не имеет гарантированного решения, и приводится доказательство с индукцией, подтверждающее этот факт; тем не менее при должной сноровке добиться такого соглашения элементарно
Итак каждый генерал имеет возможность отправить посыльного с письмом своему союзнику-генералу, но письмо будет доставлено только с некоторой вероятностью, причем не нулевой; более того, еще до расположения армий на этих холмах, генералы виделись лично и могли согласовать любой протокол действий на будущее
Окей первый генерал придумывает послание для второго, после чего пока что не пишет его на листке бумаги, но предваряет этот листок (L1-0) в верхней строке тремя элементами: S1, A1, C1, где S1=0, вместо A1 записан вопросительный знак, а C1=длине сообщения от первого генерала (N1), и отправляет в таком виде
Посыльный отправляет это письмо второму генералу, который составляет ответ на него (L2-0), и также предваряет элементами S2, A2 и C2, где S2=0, A2=0 и C2=предполагаемой длине сообщения (N2), и также отправляет свой ответ первому генералу
Первый генерал ожидает, пока к нему придет посыльный от второго с письмом вида L2-0, а если посыльный был перехвачен и не приходит, то через каждый промежуток времени от отправляет дубликат исходного сообщения L1-0; после получения ожидаемого письма он отправляет сообщения L1-1 следующего вида: преамбула S1=0, A1=0, C1=N1-m, после которой следует m букв целевого текста, который генерал хотел отправить
Второй генерал ожидает послание вида L1-1, а пока таковое не приходит, повторяет отправку посыльных в письмом L2-0, а после получения искомого сообщения отправляет ответ вида: преамбула S2=0, A2=C1*, C2=N2-m, после которой также идет m букв текста, которого он хотел отправить (C1* - значение преамбулы C1 из ожидаемого письма)
Далее процесс повторяет до тех пор, пока каждый не отправит свое послание целиком, при этом с очередным полученным сообщением каждый генерал оценивает, равно ли значение A из преамбулы полученного письма величине его текущего S плюс длина последнего сообщения, и если не равна - то отправляет повторных посыльных со всеми письмами, предшествующими этому моменту
Процесс очевидно заканчивается в тот момент, когда каждый из генералов не имеет более текста для отправки, при этом полученные A-значения от собеседника показывают, что им успешно получен весь переданный текст
Более того можно быть уверенным, что собеседник об этом знает, поскольку ранее он получал информацию о том, что A-значение покрывает весь переданный им текст
Очевидно что предложенная схема позволяет обеспечить гарантированную доставку сообщений, причем даже при очень высоком показателе перехвата писем; более того при небольших модификациях можно и защитить сообщения от изменения
А теперь внимание, вопрос! Чем приведенная в текущей теме постановка отличается от исходной задачи генералов? Очевидно что вряд ли за много лет никто не смог придумать ее решение, хотя оно довольно простое и понятное
А раз предложено такое элементарное решение, значит оно решает задачу, несколько или даже сильно, отличающуюся от исходных генералов
ВОПРОС: В ЧЕМ?
Заранее спасибо!
|
17.06.2015, 00:09 
