|
Распределенные алгоритмыволну в черный цвет. P ослабляется до (P0 ( P1 ( P2), где P2 ( волна черная. Это утверждение сохраняется по следующему правилу. Правило 3. Посещенный процесс представляет волне свой текущий цвет. Действительно, все основные коммуникации также как деятельность волны сохраняют это утверждение, которое является поэтому инвариантом. Волна заканчивается неудачно, если процессы принимают решение для черной волны, но в этом случае просто начинается новая волна. Новая волна может быть успешной, только если процессы могут стать белыми, и это случается немедленно после посещения волны. Правило 4. Решающий узел в черной волне начинает новую волну. Правило 5. Процессы немедленно становятся белыми после каждого посещения волны. Эти правила гарантируют возможный успех волны после завершения основного вычисления. Действительно, если основное вычисление закончилось, первая волна, начатая после завершение, окрашивает все процессы в белый цвет, и следующая волна заканчивается успешно. В этом алгоритме только одна волна может бежать в любой время. Если две волны, скажем А и B, бегут одновременно, окрашивание процесса в белый цвет после посещения волной B может нарушить инвариант для волны A. Поэтому, если алгоритм обнаружения должен быть децентрализован, должен также использоваться децентрализованный алгоритм волны, чтобы все инициаторы алгоритма обнаружения сотрудничали в той же самой волне. Также возможно использовать другой принцип обнаружения, в котором различные волны могут вычислять одновременно без того, чтобы нарушить правильное действие алгоритма обнаружения; см. Подраздел 8.4.2. 8.4 Другие Решения Еще два решения проблемы обнаружения завершения будут обсуждены в этом разделе: алгоритм восстановления кредита и алгоритм временных пометок. 8.4.1 Алгоритм восстановления кредита Mattern [Mat89a] предложил алгоритм, который обнаруживает завершение очень быстро, а именно, за одну единицу времени после возникновения (при принятии предположений идеализации времени из Определения 6.31). Алгоритм обнаруживает завершение централизованного вычисления и предполагает, что каждый процесс может послать сообщение инициатору вычисления непосредственно (то есть, сеть содержит звезду с инициатором в центре). В алгоритме каждому сообщению и каждому процессу назначается значение кредита, которое всегда находится между 0 и 1 (включая границы), и алгоритм поддерживает следующие утверждения как инварианты. S1. Сумма всех кредитов (в сообщениях и процессах) равняется 1. S2. Основное сообщение имеет положительный кредит. S3. Активный процесс имеет положительный кредит. Процессы имеют положительный кредит, когда правилами не предписано (то есть, пассивным процессам) посылать их кредиты инициатору. Инициатор действует как банк, собирая все кредиты, посланные ему, в переменной ret . Когда инициатор имеет все кредиты, требование для активных процессов и основных сообщений иметь положительный кредит означает, что не имеется никаких таких процессов и никаких таких сообщений; следовательно term сохраняется. Правило 1. Когда ret = 1, инициатор вызывает алгоритм объявления. Для выполнения требования живости, все кредиты в конечном счете должны быть переданы инициатору при возникновении завершения. Если основное вычисление закончилось, больше нет основных сообщений, и нас интересуют только кредиты, поддерживаемые процессами. var statep : (active, passive) init if p = p0 then active else passive ; credp : fraction init if p = p0 then I else 0 ; ret : fraction init 0 ; for p0 only Sp: { statep = active } (* Праволо 3 *) begin send (mes,credp / 2) : credp := credp / 2 end Rp: { Сообщение (mes,c) прибыло в p } begin receive (mes,c) ; statep := active; credp := credp + c (* Правила 4 and 5b *) end Ip: { statep = active } begin statep := passive ; send ( ret, credp ) to p0 ; credp :== 0 (* Правило 2 *) end AP0: { Сообщение (ret, c) прибыло в p0 } begin receive ( ret, c ) ; ret := ret + c ; if ret = 1 then Announce (* Правило I *) end Алгоритм 8.9 Алгоритм восстановления кредита. Правило 2. Когда процесс становится пассивным, он посылает свой кредит инициатору. В начальной конфигурации только инициатор активен и имеет положительный кредит, а именно 1, и ret = 0, что означает, что S1- S3 удовлетворz.ncz. Инвариант должен поддержаться в течение вычисления; об этом заботятся следующие правила. Сначала, каждому основному сообщению при посылке нужно дать положительный кредит; к счастью, отправитель активен, и следовательно имеет положительный кредит. Правило 3. Когда активный процесс p посылает сообщение, кредит разделяется между p и сообщением. Процессу при его активизации нужно дать положительный кредит; к счастью, сообщение, которое он получает при этом, содержит положительный кредит. Правило 4. При активизации процесса ему дается кредит активизирующего сообщения. Единственная ситуация, не охваченная этими правилами - получение основного сообщения уже активным процессом. Процесс уже имеет положительный кредит, следовательно не нуждается в кредите сообщения, чтобы удовлетворить S3; однако, кредит не может быть разрушен, поскольку это привело бы вело бы к нарушению S1 . Процесс получающий сообщение может обращаться с кредитом двумя различными способами, оба порождают правильные алгоритмы. Правило 5a. Когда активный процесс получает основное сообщение, кредит этого сообщения посылается инициатору. Правило 5b. Когда активный процесс получает основное сообщение, кредит того сообщения добавляется к кредиту процесса. Алгоритм дается как Алгоритм 8.9. В этом алгоритме, принимается, что каждый процесс знает имя инициатора (по крайней мере, когда он сначала становится пассивным) и алгоритм использует правило 5b. Когда инициатор становится пассивным, он посылает сообщение самому себе. Теорема 8.11 Алгоритм восстановления кредита (Алгоритм 8.9) - правильный алгоритм обнаружения завершения. Доказательство. Алгоритм осуществляет правила 1-5, из чего следует, что S1 ( S2 ( S3 инвариант, где S1 ((((( ( ((mes, c) c )+ ((p(P credp )+ ( ((ret, c) c )+ret S2 ((( mes, c ) в процессе передачи : c > 0 S3 ((p ( P : (statep = passive ( credp = 0) ( (statep = active ( credp > 0). Завершение обнаружено, когда ret = 1, который вместе с инвариантом означает, что term выполняется. Чтобы показать живучесть, заметим что после завершения не происходят никакие основные действия, следовательно происходят только получения сообщений (ret, c), и каждое получение уменьшает на 1 число сообщений находящихся в процессе передачи. Следовательно, алгоритм достигает конечной конфигурации. В такой конфигурации не имеется никаких основных сообщений (соглачно term), credp = 0 для всех p (согласно term и S3), и не имеется никакого сообщения (ret, c) (конфигурация конечная). Следовательно, ret = 1(из S1), и завершение обнаружено. ( Если осуществляется правило 5a, число управляющих сообщений равняется числу основных сообщений плюс один. (Здесь мы также считаем сообщение, посланное p0 самому себе после того, как он стал пассивным.) Если осуществляется правило 5b, число управляющих сообщений равняется числу внутренних событий в основном вычислении плюс один, не больше числа основных сообщений плюс один. Казалось бы, что правило 5b более предпочтительно с точки зрения сложности по сообщениям управляющего алгоритма. Иная ситуация возникает при рассмотрении битовой сложности. Согласно правилу 5a, каждое значение кредита в системе кроме ret - отрицательная степень 2 (i.e .., 2-i для некоторого целого числа i). Представление кредита отрицательным логарифмом уменьшает число передаваемых бит. Алгоритм восстановления кредита - единственный алгоритм в этой главе, который требует включения дополнительной информации (а именно, кредита) в основные сообщения. Добавление информации к основным сообщениям называется piggybacking. Если piggybacking не желателен, кредит сообщения может быть передан в управляющем сообщении, посланном сразу после основного сообщения. (Алгоритм следующего подраздела также требует piggybacking, если это осуществлено, используя логические часы Лампорта.) Проблема может возникнуть, если кредиты (сообщений и процессов) хранятся в установленном числе бит. В этом случае существует самый маленький положительный кредит, и не возможно разделить это количество кредита на два. Когда кредит с наименьшим возможным значением нужно разделить, основное вычисление приостанавливается на время пока процесс не приобретет дополнительный кредит от инициатора. Инициатор вычитает этот кредит из ret (ret, может получиься в результате отрицательным) и передает его процессу, который возобновляет основное вычисление после получения. Это увеличение кредита вызывает блокирование основного вычисления, что противоречит требованию невмешательства алгоритма обнаружения завершения в основное вычисление. К счастью, эти действия редки. 8.4.2 Решения, использующие временные пометки Этот подраздел обсуждает решения проблемы обнаружения завершения, основанной на использовании временных пометок. Предполагается, чтопроцессы оборудованы для этой цели часами (Подраздел 2.3.3); могут использоваться часы аппаратных средств ЭВМ также как логические часы Лампорта (Подраздел 2.3.3). Принцип обнаружения был предложен Rana [Ran83]. Подобно решениям Подраздела 8.3.3, решение Рана основано на локальном предикате quiet(p) для каждого процесса p, где quiet(p) ( statep = passive ( в не передаются соощения посланные процессом p, что означаетс, что((p quiet(p)) ( term. Как и прежде, quiet определяется как quiet(p) ( (statep = passive ( unackp = 0). Алгоритм стремится проверить для некоторого момента времени t, все ли процессы quiet ; при положительном ответе следует заключение о завершении. Реализуется это волной, которая опрашивает каждый процесс был ли он quiet в тот момент или позже; процесс, который не был quiet, не отвечает на сообщения волны, эффективно гася волну. var statep : (active, passive) ; ?p : integer init 0 ; (* Логические часы *) unackp : integer init 0 ; (* Число сообщений оставшихся без ответа*) qtp : integer init 0 ; (* Время последнего перехода на quiet *) Sp: { statep = active } begin ?p := ?p + 1 ; send (mes, ?p) ', unack p := unack p + 1 end Rp: { Сообщение (mes, ?) из q прибыло в p } begin receive (mes, ?) ; ?p := max(?p, ?) + 1 ; send ( ack, ?p ) to q ; statep := active end Ip: { statep = active } begin ?p := ?p + 1 ; statep := passive ; if unackp = 0 then (* p становится quiet *) begin qtp := ?p ; send (tok, ?p , qtp , p) to Nextp end end Ap: { Подтверждение ( ack, ?) прибыло в p } begin receive ( ack, ? ) ; ?p :== max(?p, ?) + 1 ; unackp := unackp - 1 ; if unackp = 0 and statep = passive then (* p сиановится quiet *) begin qtp := ?p ; send (tok, ?p, qtp ,p) to Nextp end end Tp: { Маркер ( tok, ?, qt, q ) прибывает в p } begin receive ( tok, ?, qt, q} ; ?p := max(?p, ?) + 1 ; if quiet(p) then if p = q then Announce else if qt ( qtp then send (tok , ?p , qt, q) to Nextp end Алгоритм 8.10 алгоритм rana. В отличие от решений в Разделе 8.3 посещение волной процесса р не затрагивает переменные процесса p, используемые для обнаружения завершения. (Посещение волны может затрагивать переменные алгоритма волны и, если используются логические часы Лампорта, часы процесса.) В следствии этого правильное действие алгоритма не нарушается параллельным выполнением нескольких волн. Алгоритм Рана децентрализован; все процессы выполняют один и тот же алгоритм обнаружения. Децентрализованный алгоритм также можно получить обеспечив алгоритм Подраздела 8.3.4 децентрализованным алгоритмом волны. В решении Рана процессы могут начинать частные волны, которые бегут одновременно. Процесс p, когда становится quiet, сохраняет время qtp, в которое это случается, и начинает волну, чтобы проверить, все ли процессы quiet со времяни qtp. Если дело обстоит так, завершение обнаружено. Иначе, будет иметься процесс, который становится quiet позже, и новая волна будет начата. Алгоритм 8.10 исполльзует этот принцип, используя часы Лампорта и используя кольцевой алгоритм как волновой алгоритм. Теорема 8.12 Алгоритм Рана (Алгоритм 8.10) - правильный алгоритм обнаружения завершения. Доказательство. Чтобы доказывать живучесть алгоритма, предположим что term сохраняется в конфигурации (, в которой все еще передаеются подтверждения. Тогда происходят только действия Ap and Tp. Поскольку каждое действие Ap уменьшает на 1 число сообщений ( ack, ( ) находящихся в процессе передачи, происходит только конечное число этих шагов. Каждый процесс становится quiet не более одного раза; следовательно маркер генерируется не более N раз, и каждый маркер передается не более N раз. Следовательно за a + N2 шагов алгоритм обнаружения завершения достигает когнечной конфигурации (, в которой term все еще сохраняется. Пусть p0 процесс с максимальным значением qt в (, то есть, в конечной конфигурации qtP0 ( qtP для каждого процесса p. Когда p0 стал quiet в последний раз (то есть, во время qtP0), он передает маркер (tok,qtP0 ,qtP0 ,p0 ).Этот маркер проходит полный круг по кольцу и возвращается к p0. Действительно, каждый процесс p должен быть quiet и удовлетворять qtP ( qtP0, когда он получает этот маркер. Если нет, p установил бы часы на значение большее чем qtP0 после получения маркера и стал бы quiet позже чем p0, противореча выбору p0. Тогда маркер возвратился к p0, p0 был еще quiet, и следовательно вызвал алгоритм объявления. Чтобы доказавать безопасность алгоритма, предположим что p0 вызвал алгоритм объявления; это произойдет, когда p0 quiet и получает назад макер (tok,qtP0 ,qtP0 ,p0 ), который был отправлен всеми процессами. Доказательство приводит к противоречию. Предположим, что term не сохраняется, когда p0 обнаруживает завершение; это означает, что имеется процесс p такой, что p не quiet. В этом случае p стал не quiet после отправления маркера p0; действительно, p был quiet, когда он отправил этот маркер. Пусть q первый процесс, который стал не quiet после отправления маркера (tok, ?, qt, p0). Это означает, что q был активизирован при получении сообщения от процесса, скажем r, который еще не отправил маркер процесса p0. (Иначе r стал бы не quiet после отправления маркера, но прежде, чем q стал не quiet, что противоречит выбору q.) Теперь после отправления маркера ?q > qtP0 продолжает сохраняться. Это означает, что подтверждение для сообщения, которое сделало q не quiet, послается r с временной пометкой ?0 > qtP0 . Таким образом, когда r стал quiet, после получения этого подтверждения, ?r > qtP0 сохраняется, и следовательно qtr > qtP0 сохраняется, когда r получает маркер. Согласно алгоритму r не отправляет маркер; т.о. мы пришли к противоречию. ( Описание этого алгоритма, который не полагался на кольцевую топологию, было представлено Huang [Hua88]. Упражнения к Главе 8 Раздел 8.1 Упражнение 8.1 Оаарактеризуйте активные и пассивные состояния Алгоритма А.2. Где эти состояния находятся в Алгоритме A.1? Раздел 8.2 Сложность по времени алгоритма обнаружения завершения определена как число единиц времени в худшем случае (согласно идиализационным предположениям Определения 6.31) между завершением основного вычисления и вызова алгоритмя объявления. Упражнение 8.2. Что является сложностью по времени Dijkstra-Scholten алгоритма? Упражнение 8.3. Shavit-Francez алгоритм применяется в произвольной сети с уникальными идентификаторами, и для того, чтобы минимизировать накладные расходы на управляющие сообщения Gallager-Humblet-Spira алгоритм используется как алгоритм волны. Сложность времени обнаружения - ?(NlogN). Можите ли вы улучшить сложность по времени до 0 (N) за счет обмена 0 (N) дополнительных управляющих сообщений? Раздел 8.3 Упражнение 8.4. Почему предикат P0 в выводе алгоритма Dijkstra-Feijen-Van Gasteren, не принимает значение ложь, если pj активизирован pi, где j ( t или i > t? Упражнение 8.5 Покажите, что для каждого m существует основное вычисление, которое использует m сообщений и заставляет алгоритм Dijkstra-Feijen-Van Gasteren использовать m(N - 1) управляющих сообщений. Раздел 8.4 Упражнение 8.6. Какие модификации должны быть сделаны в Алгоритме 8.9, чтобы осуществить правило 5a алгоритма восстановления кредита, вместо правила 5b? Упражнение 8.7 В алгоритме Рана принято, что процессы имеют идентификаторы. Теперь примите вместо этого, что процессы анонимны, но имеют средства посылки сообщений их преемникам в кольце, и что число процессов известен. Измените Алгоритм 8.10, чтобы работать согласно этому предположению. Упражнение 8.8 Покажите правильность алгоритма Рана (Алгоритм 8.10) из инварианта алгоритма. 13 Отказоустойчивость в Асинхронных Системах Эта глава рассматривает разрешимость проблем решения в асинхронных распределенных системах. Результаты организованы вокруг фундаментального результата Фишера, Линча и Патерсона [FLP85], представленного в Разделе 13.1. Сформулированный как доказательство невозможности для класса алгоритмов решения, результат можно также трактовать как список предположений, которые совместно исключают разрешение проблем решения. Смягчение этих предположений позволяет получить практические решения различных проблем, как показано в последующих разделах. Дальнейшее обсуждение см. в Подразделе 13.1.3. 13.1 Невозможность согласия В этом разделе доказывается фундаментальная теорема Фишера, Линча и Патерсона [FLP85] об отсутствии асинхронных, детерминированных 1-аварийно устойчивых протоколов согласия. Результат показан рассуждением, включающим в себя законные последовательности выполнения алгоритмов. Сначала введем обозначения (вдобавок к введенным в Разделе 2.1) и укажем элементарные результаты, которые окажутся полезными далее. 13.1.1 Обозначения, Определения, Элементарные Результаты Последовательность событий [pic] применима в конфигурации [pic], если [pic] применима в [pic], [pic]- в [pic], и т.д. Если [pic] - результирующая конфигурация, то, чтобы явно указать события, ведущие от [pic] к [pic], мы пишем [pic] или [pic]. Если [pic] и [pic] содержит только события в процессах из [pic], мы также пишем [pic]. Утверждение 13.1 Пусть последовательности[pic] и [pic] применимы в конфигурации [pic], и пусть ни один процесс не участвует одновременно в [pic] и [pic], тогда [pic] применима в [pic], [pic] применима в [pic], и [pic]. Доказательство. Следует из повторного применения Теоремы 2.19. ( Процесс [pic] имеет входную переменную [pic], доступную только для чтения, и выходной регистр однократной записи [pic] с начальным значением [pic]. Входная конфигурация полностью определяется значением [pic] для каждого процесса [pic]. Процесс [pic] может принять решение о значении (обычно 1 или 0) записью его в [pic]; начальное значение [pic] не является значением решения. Предполагается, что корректный процесс исполняет бесконечно много событий при законном выполнении; в крайнем случае, процесс всегда может выполнять (возможно пустое) внутреннее событие. Определение 13.2 t-аварийное законное выполнение - выполнение, в котором по меньшей мере N-t процессов исполняют бесконечно много событий, и каждое сообщение, посылаемое корректному процессу, получается. (Процесс корректен, если исполняет бесконечно много событий.) Максимальное число сбойных процессов, с которым может справиться алгоритм, называется способностью восстановления алгоритма, и всегда обозначается [pic]. В этом разделе демонстрируется невозможность существования асинхронного, детерминированного алгоритма со способностью восстановления 1. Определение 13.3 1-аварийно-устойчивый алгоритм согласия - алгоритм, удовлетворяющий следующим трем требованиям. Завершение. В каждом 1-аварийном законном исполнении, все корректные процессы принимают решение. Согласованность. Если в достижимой конфигурации [pic] и [pic] для корректных процессов [pic] и [pic], то [pic]. Нетривиальность. Для [pic] и для [pic] существуют достижимые конфигурации, в которых для некоторого [pic] [pic]. Для [pic] конфигурация называется v-решенной, если для некоторого [pic] [pic]; конфигурация называется решенной, если она 0-решенная или 1- решенная. В [pic]-решенной конфигурации какой-нибудь процесс принял решение [pic]. Конфигурация называется v-валентной, если все решенные конфигурации, достижимые из нее, v-решенны. Конфигурация называется бивалентной, если из нее достижимы как 0-валентные, так и 1-валентные конфигурации, и унивалентной, если она либо 1-валентная, либо 0-валентная. В унивалентной конфигурации, хотя никакое решение не было обязательно принято никаким процессом, окончательное решение уже неявно определено. Конфигурация [pic] [pic]-устойчивого протокола называется развилкой, если существует множество [pic] (самое большее) из [pic] процессов и конфигурации [pic] и [pic] такие, что [pic], [pic], и [pic] [pic]-валентна. Неформально, [pic]- развилка, если подмножество из [pic] процессов может добиться 0-решенности так же, как и 1-решенности. Следующее утверждение формально фиксирует, что в любой момент оставшиеся процессы должна вынести аварию самое большее [pic] процессов. Утверждение 13.4 Для каждой достижимой конфигурации t-устойчивого алгоритма и каждого подмножества S по меньшей мере из N-t процессов существует решенная конфигурация [pic] такая, что [pic]. Доказательство. Пусть [pic] и [pic] удовлетворяют условию и рассмотрим выполнение, которое достигает конфигурации [pic] и содержит бесконечно много событий в каждом процессе из [pic] впоследствии (и никаких шагов процессов не из [pic]). Это выполнение - t-аварийное законное, и процессы в [pic] корректны; следовательно они достигают решения ( Лемма 13.5 Достижимой развилки не существует. Доказательство. Пусть [pic] - достижимая конфигурация и [pic] - подмножество самое большее из [pic] процессов. Пусть [pic] будет дополнением [pic], т.е., [pic]. В [pic] по меньшей мере N- t процессов, следовательно существует решенная конфигурация [pic] такая, что [pic] (Утверждение 13.4). Конфигурация [pic] либо 0-, либо 1-решенная; положим, что она 0-решенная. Сейчас будет показано, что [pic] ни для какой 1-валентной [pic]; пусть [pic] - любая такая конфигурация, что [pic]. Так как шаги в [pic] и [pic] заменяются (Утверждение 13.1), есть конфигурация [pic], которая достижима и из [pic], и из[pic]. Так как [pic] - 0-решенна, то и[pic]- тоже, что показывает не 1-валентность [pic]. ( 13.1.2 Доказательство невозможности Сначала, используя нетривиальность проблемы, покажем что существует бивалентная начальная конфигурация (Лемма 13.6). Вполедствии будет показано, что начиная с бивалентной конфигурации, каждый доступный шаг можно исполнять без перехода в унивалентную конфигурацию (Лемма 13.7). Этого достаточно, чтобы показать невозможность алгоритмов согласия (Теорема 13.8). В дальнейшем, пусть А - 1-аварийно-устойчивый алгоритм согласия. Лемма 13.6 Для А существует бивалентная начальная конфигурация. Доказательство. Так как А нетривиален (Определение 13.3), то есть достижимые 0- и 1-решенные конфигурации; пусть [pic] и [pic] - начальные конфигурации такие, что [pic]-решенная конфигурация достижима из [pic]. Если [pic], эта начальная конфигурация бивалентна и результат имеет силу. Иначе, есть начальные конфигурации [pic] и [pic] такие, что [pic]-решенная конфигурация достижима из [pic], и [pic] и [pic] различаются входом одного процесса. Действительно, рассмотрим последовательность начальных конфигураций, начинающуюся с [pic] и заканчивающуюся [pic], в которой каждая следующая начальная конфигурация отличается от предыдущей в одном процессе. (Эта последовательность получается инвертированием входных битов одного за другим.) Из первой конфигурации в последовательности, [pic], достижима 0-решенная конфигурация, и из последней, [pic], достижима 1- решенная конфигурация. Так как решенная конфигурация достижима из каждой начальной конфигурации, описанные [pic] и [pic] можно найти в последовательности. Пусть [pic] - процесс, в котором [pic] и [pic] различны. Рассмотрим законное выполнение, начинающееся с [pic], в которой [pic] не делает шагов; это выполнение 1-аварийно законное и следовательно достигает решенной конфигурации [pic]. Если [pic] 1-решенная, [pic] бивалентна. Если [pic] 0-решенная, заметьте, что [pic] отличается от [pic] только в [pic], а [pic] не делает шагов в выполнении; следовательно [pic] достижима из [pic], что показывает бивалентность [pic]. (Более точно, конфигурация [pic] достижима из [pic], где [pic] отличается от [pic] только в состоянии [pic]; следовательно [pic] 0-решенная.) ( Чтобы построить законное выполнение без принятия решения мы должны показать, что каждый процесс может сделать шаг, и что каждое сообщение может быть получено не обуславливая принятие решения. Пусть шаг s обозначает получение и обработку отдельного сообщения или спонтанное действие (внутреннее или посылки) отдельного процесса. Состояние процесса, делающего шаг, может привести к различным событиям. Прием сообщения применим, если оно в пути, и спонтанный шаг всегда применим. Лемма 13.7 Пусть [pic]- достижимая бивалентная конфигурация и s - применимый шаг для процесса p в [pic]. Существует последовательность событий [pic] такая, что s применим в [pic], и [pic] бивалентна. Доказательство. Пусть С - множество конфигураций, достижимых из [pic] без применения s, т.е., С = {[pic]: s не происходит в [pic]}; s применим в каждой конфигурации С (напомним, что s - шаг, а не отдельное событие). В С есть конфигурации [pic] и [pic] такие, что из [pic] достижима v- решенная конфигурация. Чтобы убедится в этом, заметим, что, т.к. [pic] бивалентна, из нее достижимы v-решенные конфигурации [pic] для v =0,1. Если [pic] (т.е. для достижения решенной конфигурации s не применялся), заметим, что [pic], тем не менее, v-решенная, поэтому выберем [pic]. Если [pic] (т.е. для достижения решенной конфигурации s применялся), выберем [pic] как конфигурацию, из которой применялся s. Если [pic], [pic] - искомая бивалентная конфигурация. Предположим, что [pic], и рассмотрим конфигурации на путях от [pic] до [pic] и [pic]. Две конфигурации на этих путях называются соседними, если одна получается из другой за один шаг. Так как 0-решенная конфигурация достижимаа из [pic] и 1- решенная конфигурация достижима из [pic], то на путях есть конфигурация [pic] такая, что [pic] бивалентна; или есть соседи [pic] и [pic] такие, что [pic] 0-валентна и [pic] - 1-валентна. В первом случае [pic] - искомая бивалентная конфигурация и лемма доказана. Во втором случае, одна конфигурация из [pic] и [pic] - развилкой, что является противоречием. Действительно, предположим, что [pic] получена за один шаг из [pic], т.е., [pic] для события e в процессе q. Теперь [pic] - это [pic] и, следовательно, 1-валентна, но [pic] не 1-валентна, т.к. [pic] уже 0-валентна. Итак, е и s не заменяются, что подразумевает (Теорема 2.19) , что p = q, но тогда достижимая конфигурация [pic] удовлетворяет [pic] и [pic]. Так как первая 0-валентна, а последняя 1-валенттна, [pic] - развилка, что является противоречием. ( Теорема 13.8 Асинхронного, детерминированного, 1-аварийно-устойчивого алгоритма согласия не существует. Доказательство. Если предположить, что такой алгоритм существует, можно построить законное выполнение без принятия решения, начиная с бивалентной начальной конфигурации [pic]. Когда построение дойдет до конфигурации [pic], выберем в качестве [pic] применимый шаг, который был применим самое большое число раз. По предыдущей лемме, выполнение можно расширить так, что исполняется [pic] и достигается бивалентная конфигурация [pic]. Такое построение дает бесконечное законное выполнение, в котором все процессы корректны, но решение никогда не будет принято. ( 13.1.3 Обсуждение Вывод утверждает, что не существует асинхронных, детерминированных, 1- аварийно-устойчивых алгоритмов решения для проблемы согласия; это исключает алгоритмы для класса нетривиальных проблем. (см. Подраздел 12.2.2). К счастью, некоторые предположения, лежащие в основе результата Фишера, Линча и Патерсона, можно выразить явно, и результат, как оказывается, очеть чувствителен к ослаблению любого из них. Несмотря на вывод о невозможности, многие нетривиальные проблемы имеют решения, даже в асинхронных системах и где процессы могут отказывать. Ослабленная модель отказов. Раздел 13.2 рассматривает модель отказов изначально-мертвых процессов, которая слабее, чем модель аварий, и в этой модели согласие и выборы детерминированно достижимы. Ослабленная координация. Раздел 13.3 рассматривает проблемы, которые требуют менее тесной координации между процессами, чем согласие, и показывает, что некоторые из этих проблем, включая переименование, разрешимы в модели аварий. Рандомизация. Раздел 13.4 рассматривает протоколы с уравненными вероятностями, где требование завершения достаточно ослаблено, чтобы обеспечить решения даже при присутствии Византийских отказов. Слабое требование завершения. Раздел 13.5 рассматривает другое ослабление требования завершения, а именно где разрешение требуется только когда данный процесс корректен; здесь также возможны Византийско-устойчивые решения. Синхронность. Влияние синхронности изучается далее в Главе 14. Возможны довольно тривиальные решения, если одно из трех требований Определения 13.3 просто опущено; см. Упражнение 13.1. Исключение предположения (неявно использованного в доказательстве Леммы 13.6) о том, что возможны все комбинации входов, изучается в Упражнении 13.2. 13.2 Изначально-мертвые Процессы В модели изначально-мертвых процессов, ни один процесс не может отказать после исполнения события, следовательно, при законном выполнении каждый процесс исполняет либо 0, либо бесконечно много событий. Определение 13.9 t-изначально-мертвых законное выполнение - выполнение, в котором по крайней мере N-t процессов активны, каждый активный процесс исполняет бесконечно много событий, и каждое сообщение, посылаемое корректному процессу, принимается. В t-изначально-мертвых-устойчивом алгоритме согласия, каждый корректный процесс принимает решение в каждом t-изначально-мертвых законном выполнении. Согласованность и нетривиальность определяются так же, как в модели аварий. var [pic], [pic], [pic]: sets of processes init 0; begin shour ; (* т.е.: forall [pic] do send to [pic] *) while [pic] < L do begin receive; [pic] end; shout; [pic]; while [pic] do begin receive; [pic]; [pic]; end; ¤?ҐЙ¤П¦©Ф¬кЇfµрј6В.Т„СWдЄЬјйМвЖвужюЧFйНРвжЭНaгnПP,#з0ИК*1?иА с?8ьЧУш‚5/Ш26hІ-’'jп§ Ў Є ? 5[pic], зная, что [pic] уже послал по меньшей мере одно сообщение. Будет показано, что проблемы согласия и выборов разрешимы в модели изначально- мертвых, пока отказывает меньшинство процессов (t < N/2). Большее число изначально-мертвых процессов не допускается (см. Упражнение 13.3). Соглашение о подмножестве корректных процессов. Сначала представляется алгоритм Фишера, Линча и Патерсона [FLP], с помощью которого каждый из корректных процессов вычисляет одну и ту же совокупность корректных процессов. Способность восстановления этого алгоритма [pic]; пусть [pic] равно [pic], и заметим, что корректных процессов по меньшей мере [pic]. Алгоритм работает в два этапа; см. Алгоритм 13.1. Заметим, что процессы посылают сообщения сами себе; это делается во многих устойчивых алгоритмах и облегчает анализ. Здесь и в дальнейшем, операция “shout” означает forall [pic] do send to [pic]. Эти процессы строят ориентированный граф [pic], “выкрикивая” свой идентификатор (в сообщении ) и ожидая приема [pic] сообщений. Так как корректных процессов по меньшей мере [pic], каждый корректный процесс получает достаточно много сообщений для завершения этой части. Преемники [pic] в графе [pic] - вершины [pic], из которых [pic] получил сообщение . Изначально-мертвый процесс не получал и не посылал никаких сообщений, следовательно он формирует изолированную вершину в [pic]; у корректного процесса есть [pic] преемников, следовательно, он не изолирован. Узел - это сильносвязный компонент без исходящих дуг, содержащий по меньшей мере две вершины. В [pic] есть узел, содержащий корректные процессы, и, так как каждый корректный процесс имеет степень выхода [pic], этот узел имеет размер по меньшей мере [pic]. В результате, так как [pic], существует ровно один узел; назовем его [pic]. В конечном счете, так как корректный процесс [pic] имеет [pic] преемников, по меньшей мере один из них принадлежит [pic], что означает, что все процессы в [pic] - потомки [pic]. Следовательно, на втором этапе алгоритма, процессы образуют индуцированный подграф графа [pic], содержащий по меньшей мере их потомков, получая множество преемников от каждого процесса, который, как они знают, корректен. Так как процессы не отказвыают после посылки сообщения, на этом этапе не возникает тупика. Действительно, [pic] ждет сообщения от [pic] только если на первом этапе некоторый процесс получил сообщение , показывающее на корректность [pic]. После завершения Алгоритма 13.1 каждый корректный процесс получил набор преемников каждого из своих потомков, позволяя таким образом вычислить уникальный узел в G. Согласие и выбор. Поскольку все корректные процессы договариваются об узле корректных процессов, избрать процесс теперь тривиально; избирается процесс с самым большим идентификатором в K. Теперь так же просто достигнуть согласия. Каждый процесс вещает, вместе со своими преемниками, свой вход (x). После вычисления K, процессы принимают решение о значении, которое является функцией совокупности входов в K (например, значение, которое встречается наиболее часто, ноль в случае ничьей). Алгоритмы узел-соглашения, согласия, и выбора обменивают [pic] сообщениями, где сообщение может содержать список из L имен процессов. Были предложены более эффективные алгоритмы выбора. Итаи и другие [IKWZ90] привели алгоритм, использующий [pic] сообщения и показали, что это является нижней границей. Масузава и другие [MNHT89] рассмотрели проблему для клик с чувством направления и предложили алгоритм [pic] сообщений, который также является оптимальным. Любой алгоритм выбора, выбирая корректный процесс в качестве лидера также решает проблему согласия; лидер вещает свой вход и все корректные процессы принимают решения по нему. Следовательно, вышеупомянутые верхние границы остаются в силе также для проблемы согласия для изначально-мертвых процессов. В модели аварий, однако, наличие лидера не помогает в решении проблемы согласия; сам лидер может отказать до вещания своего входа. Кроме того, проблема выбора не разрешима в модели аварийного отказа, что будет показано в следующем разделе. 13.3 Детерминированно Достижимые Случаи Проблема согласия, изучаемая до сих пор, требует, чтобы каждый процесс принял решение об одном и том же значении; этот раздел изучает разрешимость задач, которые требуют менее близкой координации между процессами. В Подразделе 13.3.1 представлено решение практической проблемы, а именно, переименование совокупности процессов в малом пространстве имен. В Подразделе 13.3.2 выведенные ранее результаты о невозможности расширяются, чтобы охватить больший класс проблем решения. Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 |
|
