Реферат: Распределенные алгоритмы

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), и завершение обнаружено. o

Если осуществляется правило 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  сохраняется в конфигурации g, в которой все еще передаеются подтверждения. Тогда происходят только действия Ap and Tp. Поскольку каждое действие Ap уменьшает на 1 число сообщений ( ack, q ) находящихся в процессе передачи, происходит только конечное число этих шагов. Каждый процесс становится quiet не более одного раза; следовательно маркер генерируется не более N раз, и каждый маркер передается не более N раз. Следовательно за a + N2 шагов алгоритм обнаружения завершения достигает когнечной конфигурации d, в которой term все еще сохраняется.

Пусть p0 процесс с максимальным значением qt в d, то есть, в конечной конфигурации 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 не отправляет маркер; т.о. мы пришли к противоречию. o

Описание этого алгоритма, который не полагался на кольцевую топологию, было представлено 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 Обозначения, Определения, Элементарные Результаты

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

Утверждение 13.1 Пусть последовательности и  применимы в конфигурации , и пусть ни один процесс не участвует одновременно в  и , тогда  применима в ,  применима в , и .

Доказательство. Следует из повторного применения Теоремы 2.19.                       o

Процесс  имеет входную переменную , доступную только для чтения, и выходной регистр однократной записи  с начальным значением . Входная конфигурация полностью определяется значением  для каждого процесса . Процесс  может принять решение о значении (обычно 1 или 0) записью его в ; начальное значение  не является значением решения. Предполагается, что корректный процесс исполняет бесконечно много событий при законном выполнении; в крайнем случае, процесс всегда может выполнять (возможно пустое) внутреннее событие.

Определение 13.2 t-аварийное законное выполнение - выполнение, в котором по меньшей мере N-t процессов исполняют бесконечно много событий, и каждое сообщение, посылаемое корректному процессу, получается. (Процесс корректен, если исполняет бесконечно много событий.)

Максимальное число сбойных процессов, с которым может справиться алгоритм, называется способностью восстановления алгоритма, и всегда обозначается . В этом разделе демонстрируется невозможность существования асинхронного, детерминированного алгоритма со способностью восстановления 1.

Определение 13.3 1-аварийно-устойчивый алгоритм согласия - алгоритм, удовлетворяющий следующим трем требованиям.

(1)   Завершение. В каждом 1-аварийном законном исполнении, все корректные процессы принимают решение.

(2)   Согласованность. Если в достижимой конфигурации  и  для корректных процессов  и , то .

(3)   Нетривиальность. Для  и для  существуют достижимые конфигурации, в которых для некоторого  .

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42