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

Пусть (r, l) маркер с минимальным идентификатором после, которого посылается маркер chasing . Маркер (r, l) сам не может быть chasing, потому что маркер chasing преследует только маркеры с меньшим идентификатором. Мы можем поэтому предполагать, что (r, 1) стал waiting, когда он впервые достиг процесса p¢, который уже отправил другой маркер уровня l.Пусть p"   последний процесс на пути следования (r, l), который получил маркер annexing, после того как он отправил

(r, l), и маркер сменил режим на chasing r. Этот маркер chasing встретит (r, 1) в p ', или откажется от преследования, если маркер waiting был найден прежде, чем маркер достиг p '. В обоих случаях маркер на уровне l + 1 произведен, т.е. мы пришли к противоречию.

Теорема 7.23 Korach-Kutten-Moran алгоритм (Алгоритм 7.13) - алгоритм выбора.

Доказательство Предположим, что по крайней мере один процесс начинает алгоритм. Согдасно предыдущей лемме, число маркеров, произведенных на каждом уровня уменьшается, и будет иметься уровень,  на котором точно один маркер, скажем (q, 1) произведен. Никакой маркер уровня l ' < l не заканчивает обход, следовательно ни один из этих маркеров не заставляет процесс стать избранным. Уникальный маркер на уровне l только сталкивается с процессами на уровнях меньше чем l, или с cat = q (если он достигает процесса, который уже посещал), и отправляется в обоих случаях. Следовательно обход этого маркера заканчивается, и q избран.

Функция f,  как считается  выпуклой если f (a) + f (b) £ f (+ b). Сложность алгоритма проанализирована здесь согласно предположению что f (x) - алгоритм обхода(см. Раздел 6.3) , где f - выпуклая функция.

Теорема 7.24 если f (x) - используется алгоритмом обхода, где f  выпуклая , KKM алгоритм выбора не более (1+log k)[f(N)+N] сообщений если он начинается k процессами.

Доказательство. Если алгоритм начат k процессами, не более 2-l маркеров произведены на уровне l, что означает, что самый высокий уровень - не более ëlogkû.

Каждый процесс посылает маркеры annexing не более одного идентификатора на каждом уровне. Если на некотором уровне l имеются маркеры с идентификаторами p1, …, pj и имеются процессы Ni, которые отправили маркер annexing (pi, l), то из этого следует что S1j Ni £ N .  Т.к.  алгоритм обхода  является f (x) - алгоритмом обхода, маркер annexing (pj, l) был послан не более f (Nj) раз, что дает общее количество сообщений передающих маркеры annexing уровня l не более S1j f(Ni) , что не превышает f (N), потому что f выпуклая. Каждый процесс посылает не более одного маркера chasing на каждом уровне, что дает не более N маркеров chasing на уровень.

Таким образом имеется не более (1 + log k) различных уровней, и не более f (N) + N сообщений посылаются на каждом уровене, что доказывает результат. o

Построение Attiya. Другое постоения алгоритма выбора из алгоритмов обхода давалось Attiya [Att87]. В этом построении обход одного маркера, скажем с  идентификатором q , не прерывается до тех пор, пока маркер не достигнет процесса r уже посещенного другим маркером, скажем процесса p.Маркер annexing ждет в r, но посылает маркер "охотник", чтобы преследовать маркер p и затем ветнуться в r, если p может быть успешно побежден. Если охотник возвращается,  не нужно начинать новый обход, а текущий обход маркера q продолжается, таким образом потенциально сокращается сложность по сообщениям. Чтобы позволять охотнику возвращаться, чтобы обработать r,  сеть должна быть двунаправленая. Если используется f (x) - алгоритм обхода, результирующий алгоритм выбора имеет сложность по сообщениям приблизительно 3. S1j f(N/i)

7.4.2 Применения Алгоритма KKM

Если f (x) - алгоритм обхода для класса сетей существует, этот класс как считают - f (x) -обходимый.

Выбор в кольцах. Кольца - x-обходимо, следовательно KKM алгоритм выбирает лидера в кольце используя 2N log N сообщений.

Выбор в кликах. Клики - 2x-обходимы, следовательно KKM алгоритм выбирает лидера в клике, использующей 3N log N сообщений согласно Теореме 7.24. Более осторожный анализ алгоритма показывает, что сложность - фактически 2N log N + 0 (N) в этом случае. Каждый маркер преследуется, используя не более трех сообщений chasing, так что общее количество сообщения chasing в вычислении,  ограничено 3.S0logN+12-i N= 0(N). Никакой алгоритм выбора для клик со сложностью лучше чем 2NlogN + 0 (N) не известен до настоящего времени. Нижняя граница Ω(NlogN ) была доказана Korach, Moran, и Zaks [KMZ84].

 Нижняя граница не соблюдается, если сеть имеет направление глобального смысла [LMW86]. В сети, которая имеет направление глобального смысла,  каналы процесса помечены целыми числами от 1 до N-1, и там существует направленный гамильтонов цикл такой, что канал pq помечен в процессе p расстоянием от p до q в цикле: см. Раздел B. 3. Loui, Matsushita. И West [LMW86] дал 0 (N) алгоритм выбора для клик с направление глобального смысла, но на вычисление направление глобального смысла затрачивается Ω(N2) сообщений, даже если лидер  доступен [Tel94].

Выбор в торе. Торические сети - x-обходимы, следовательно KKM алгоритм выбирает лидера в торе используя 2N log N сообщений.

Тор должен быть помечен (то есть, каждый край помечен как Up, Left и т.д.) чтобы применить x-алгоритм обхода (Алгоритм 6.11). Peterson [Pet85] дал алгоритм выбора для решетки и тора, который использует 0 (N) сообщения и не требует, чтобы  грани были помечены.

Выбор в гипекубах. Гиперкубы со смыслом направлений  - x-обходимы (см. Алгоритм 6.12), следовательно KKM алгоритм выбирает лидера в гиперкубе, использование 2N log N сообщений. Tel [Tel93] предложил алгоритм выбора для гиперкубов со смыслом направлений,  который использует только 0 (N) сообщений. Вычисление смысла направлений стоит 0 (1.51) сообщений [Tel94], это также и сложность GHS алгоритма когда он применяется к гиперкубу.

Tel [Tel93] дал алгоритм выбора для гиперкубов со смыслом направлений, который использует 0 (N) сообщений.

Упражнения к  Главе 7

Раздел 7.1

Упражнение 7.1 Докажите, что сравнительный алгоритм выбора  для произвольных сетей - алгоритм волны, если случай, в котором процесс становится лидером,  расценен как случай решения.

Упражнение 7.2 Покажите, что сложность по времени Алгоритма 7.1 2D.

Раздел 7.2

Упражнение 7.3 Докажите, что идентификатор Σ1m Hi = (m + 1)Hi - m используемый в Подразделе 7.2.1.

Упражнение 7.4  Покажите, что ln (N + 1) < HN < ln (N) + 1. (ln  означает натуральный логарифм.)

Упражнение 7.5 Рассмотрите алгоритм Chang-Роберта согласно предположению, что каждый процесс является инициатором. Для какого распределения идентификаторов по кольцу сложность по сообщениям минимальна и  сколько сообщений обменены в этом случае?

Упражнение 7.6 Какова средняя сложностью алгоритма Chang-Роберта, если имеется точно S инициаторов, где каждый выбор процессов S, одинаково, вероятно будет набором инициаторов?

Упражнение 7.7 Дайте начальную конфигурацию для Алгоритма 7.7, для которого алгоритм фактически требует ëJog N + 1û  раундов. Также дайте начальную конфигурацию, для которой алгоритм требует только двух раундов, независимо от числа инициаторов. Является ли это возможным для алгоритма, чтобы закончиться в одном круге?

Упражнение 7.8 Определите набор ecr (как определяет Lemma 7.10) для алгоритма Chang-Роберта.

Раздел 7.3

Упражнение 7.9 Примените вырождение к кольцевому алгоритму и сравните алгоритм с алгоритмом Chang-Роберта. Каково различие и каково влияние этого различия?

Упражнение 7.10Определите для каждого из семи типов сообщения, используемых в Gallager/Humblet/Spira алгоритме, может ли сообщение этого типа быть послано узлу в состоянии sleep.

Упражнение 7.11 Предположим, что GHS алгоритм использует дополнительную процедуру пробуждения, которая гарантирует, что каждый узел начинает алгоритм в пределах единиц N время.

Докажите по индукции, что после не более чем 5N l — 3N единиц времени каждый узел - на 1 уровне. Докажите, что алгоритм заканчивает в пределах 5NlogN единиц время.

Раздел 7.4

Упражнение 7.12 Покажите, что O (NlogN) алгоритм для выбора в плоских сетях существует.

Упражнение 7.13 Покажите, что существует 0 (NlogN) алгоритм выбора для тора без смысла направлений.

Упражнение 7.14 Покажите, что существует 0 (NlogN) алгоритм выбора для гиперкубов без смысла направлений.

Упражнение 7.15 Покажите, что существует O (N (logN + k)) алгоритм выбора для сетей с ограниченной степенью k (то есть, сети, где каждый узел имеет не более k соседей).

8 Обнаружение завершения

Вычисление распределенного алгоритма заканчивается, когда алгоритм достигает конечной конфигурации; то есть конфигурация, в которой никакие дальнейшие шаги алгоритма невозможны. Не всегда  в предельной конфигурации каждый процесс находится в конечном состоянии; то есть в таком состоянии,что нет ни одного события применимого  к процессу. Рассмотрим конфигурацию, в которой каждый процесс находится в состоянии, которое позволяет получать сообщения, и все каналы пусты. Такая конфигурация является конечной, но состояния процессов могут быть промежуточными состояния в вычислении. В этом случае, процессы не знают, что вычисление закончилось; такое завершение вычисления называется  неявным. Завершение называется  явным в процессе, если состояние этого процесса в конечной конфигурации - конечное состояние. Неявное завершение вычисления также называется завершением сообщений, потому что после достижения конечной конфигурации сообщения больше не посылаются. Явное завершение также называется завершением процессов, потому что при явном завершении алгоритма процессы закончивают свое выполнение.

Обычно более легкое разрабатывать алгоритм, который заканчивается неявно чем  алгоритм , который заканчивается явно. Действительно, в время разработки алгоритма все аспекты надлежащего завершения процессов могут игнорироваться; пр разработке концентрируются на ограничении полного числа событий, которые могут произойти. С другой стороны, применение алгоритма может потребовать, чтобы процессы закончились явно. Только после явного завершения результаты вычисления могут быть расцененным как заключительные, и переменные используемые в вычислении освобождены. Тупик распределенного алгоритма также приводит конечной конфигурации; в этом случае после достижения конечной конфигурации вычисление должно быть начато снова.

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

Наиболее трудной частью преобразования оказывается  алгоритм, обнаруживающий завершение. Процедура отправки сообщений завершения довольно тривиальна и будет обсуждена кратко в Подразделе 8.1.3. В этой главе будет показано, что обнаружение завершения возможно для всех классов сетей, для которых можно получить волновой алгоритм. Эти классы включают сети, где лидер доступен, сети, где процессы имеют идкентификаторы, древовидные сети, и сети, в которых доступна топологическая информация, типа диаметра или количества  процессов. С другой стороны, в Главе 9 будет показано, что для анонимных сетей неизвестного размера существует неявно заканчивающийся алгоритм, но нет явно заканчивающегося алгоритма для вычисления максимума по входам процессов. Следовательно, обнаружение завершения невозможно в анонимных сетях где неизвестен размер.

Для тех случаев, в которых возможно обнаружение завершения, мы установим нижении границы числа сообщений, используемых алгоритмом обнаружения завершения. Будет показано, что существуют алгоритмы, которые удовлетворяют этим границам. Раздел 8.1 представляет проблему формально,  предлагая модель поведения распределенного вычисления и представляя  низшую границу и процедуру посылки сообщений завершения. Раздел 8.2 представляет несколько решений, основанные на использовании дерева (или леса) процессов, включающего по крайней мере все процессы, которые все еще производят вычисление. Решения в этом разделе не слишком сложны и удовлетворяют низшей границе Разделе 8.1. Эти первые два раздела содержат все фундаментальные результаты касающиеся существования и сложности алгоритмов обнаружения завершения. По различным причинам один алгоритм обнаружения завершения может быть более подходящий для конкретного применения чем другой алгоритм. Поэтому, Разделы 8.3 и 8.4 представляют некоторые другие решения. 

8.1 Предварительные замечания

8.1.1 Определения

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

Множество состояний процесса p - Zp,  разделено в два подмножества - активных и пассивных состояний. Состояние процесса p - Сp  активно если в нем к процессу p применимо внутреннее событи или событие посылки,   и пассивено в остальных случаях. В пассивном состоянии Сp применимо только событие приема  или вообще нет применимого события, т.е. Сp - конечное состояние процессо p. Процесс p  будем называть  активным, если он находится в активном состоянии и пассивным в противном случае. Очевидно, что сообщение может быть послано только активным процессом, и пассивный процесс может стать активным только, после получения сообщения. Активный процесс может стать пассивным, если он войдет в пассивное состояние. Сделаем некоторые из предположения для упрощения описания алгоритмов в этой главе.

(1) Активный процесс становится пассивным только после внутреннего события. Любой процесс можно достаточно просто модифицировать, для того чтобы он удовлетворял этому предположению. Пусть (c, m, d ) событие посылки (или получения) процесса p, где d - пассивное состояние. Заменим это событие процесса p  на (c, m, d'), где d' является новым состоянием, и единственным событием, применимым в d' является внутреннее ссобытие (d', d). Так как d' является активным состоянием, p становится пассивным после внутреннего события (d', d).

(2) Процесс всегда становится активным после получения сообщения. Любой процесс можно достаточно просто модифицировать, для того чтобы он удовлетворял этому предположению. Пусть (c, m, d) событие получения процесса  p,  где d - пассивное состоянием. Заменим это событие на (c, m, d'), где d' является новым состоянием, и единственным событием, применимым в d' является внутреннее событие (d', d). Так как d' является активным состоянием, p становится активным после события получения и пассивным в его следующем событии (d', d).

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

Из состояния процесса p нас интересует только активное оно или пассивное; эта информация будет представлена  переменной statep. Все переходы вычисления представлены в алгоритме 8.1

var statep   : (active, passim) ;

Sp: { statep = active }

      begin send (mes) end

Rp: { A message ( mes) has arrived at p }

      begin receive ( mes ) ; statep := active end

Ip: { statep = active }

     begin statep := passive end

Алгоритм 8.1 ОСНОВНОЙ распределенный алгоритм.

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

Чтобы отличить этот алгоритм от алгоритма обнаружения завершения, его часто называют основным алгоритмом, и вычисление тогда называется основным вычислением. Алгоритм обнаружения завершения также называют управляющим или добавочным алгоритмом,  и его вычисление называют управляющими или добавочными вычислениями. Аналогично, сообщения называются основные или управляющими.

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

Теорема 8.1

term <==>   ("p ÎP : statep = passive)

                   Ù("pq Î E : Mpq  не содержит сообщений (mes)).

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

Если некоторый процесс активен, событие посылки или внутреннее событие возможно в том процессе, и если некоторый канал содержит сообщение (mes),  событие получения этого сообщения применимо. o                                                      

В конечной конфигурации основного алгоритма каждый процесс ожидает получения сообщения и остается ожидающим навсегда. Проблема, обсуждаемая в этой главе - какой управляющий алгоритм нужно добавить в систему, чтобы перевести процессы в конечное состояние после того, как основное вычисление достигло конечной конфигурации. Для объединенного алгоритма (основного алглоритма вместе с управляющим алгоритмом) конфигурация, удовлетворяющая предикату term  не обязательно является конечной: в общем случае могут иметься применимые события для управляющегоалгоритма. В управляющем алгоритме происходит обмен сообщениями, они могут быть посланы пассивными процессами и не переводить пассивный процесс в активное состояние после получения сообщения.

Управляющий алгоритм состоит из алгоритма обнаружения завершения и алгоритма объявления завершения. Алгоритм обнаружения завершения вызывает алгоритм объявления, и этот алгоритм переводит процессы в конечное состояние. Алгоритм обнаружения должен удовлетворять следующим трем требованиям.

(1) Невмешательство.Он не должен влиять на вычисление основного алгоритма.

(2) Живучесть. Если предикат term истинен , алгоритм объявления должен быть вызван за конечное число шагов.

(3) Безопасность. Если алгоритм объявления  вызыван, конфигурация должна удовлетворить предикату term.

Проблема обнаружения завершения была впервые сформулирована Francez [Fra80]. Francez предложил решение, которое не удовлетворяет приципу невмешательства;  сначала вычисление основного алгоритма "замораживалось" блокировкой всех событий, затем проверялось является ли конфигурация конечной. При положительном ответе вызывался алгоритм объявления; в противном случае, основное вычисление "размораживалось", и процедура повторялась спустя некоторое время. Вышеупомянутые требования не выполняются при таком решении проблемы.Они требуют, чтобы алгоритм обнаружения работал "непрерывно", то есть, во время работы основного вычисления. В доказательствах правильности обнаружения завершения в этой главе не дается объяснений по поводу выполнения требования невмешательства, потому что из самого описания алгоритма обычно вполне ясно, что это требование удовлетворено.

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

8.1.2 Две нижних границы

Сложность алгоритма обнаружения завершения выражается как и ранее параметрами N и ú Eú  и числом сообщений М, используемых основным вычислением. Сложность обнаружения завершения также связана со сложностью алгоритма волны; обозначим сложность по сообщениям лучшего алгоритма волны W. W конечно зависит от характеристик класса сетей, которые мы рассматриваем , например, характеристики типа, является ли лидер доступным, топологии, и начального знания процессов.

Будет показана сложность обнаружения завершения в наихудшем случае. Как для централизованных, так и для децентрализованных вычислений, она ограничена снизувеличиной  М. Затем будет показано, что сложность обнаружения завершения для децентрализованных основных вычислений ограничена снизу величиной W. В конце этого подраздела будет обсуждена ниняя граница по сообщениям ú Eú , выведенная Chandrasekaran и Venkatesan [CV90],.

Страницы: 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