Реферат: Распределенные алгоритмы
waitp := q
end
end
Алгоритм 7.13 korach-kutten-moran алгоритм.
Доказательство. Не более k/2 маркеров произведены на уровне l + 1, потому что, когда такой маркер произведен, два маркера уровня l убиты в то же самое время.
Предположим, что имеется уровень l такой, что k> l маркеров произведены на уровне l, но никаком маркер не произведен на уровне l + 1. Пусть q процесс с максимальным идентификатором, который производит маркер на уровне l.Маркер (q, l) не заканчивает обход, потому что он будет получен процессом p, который уже отправил другой маркер уровня l.Когда это случается впервые (q, l) становится chasing или, если p уже отправил маркер chasing, (q, l) становится waiting. В любом случае, уровне l есть маркеры chasing .
Пусть (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.1 Докажите, что сравнительный алгоритм выбора для произвольных сетей - алгоритм волны, если случай, в котором процесс становится лидером, расценен как случай решения.
Упражнение 7.2 Покажите, что сложность по времени Алгоритма 7.1 2D.
Упражнение 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.9 Примените вырождение к кольцевому алгоритму и сравните алгоритм с алгоритмом Chang-Роберта. Каково различие и каково влияние этого различия?
Упражнение 7.10Определите для каждого из семи типов сообщения, используемых в Gallager/Humblet/Spira алгоритме, может ли сообщение этого типа быть послано узлу в состоянии sleep.
Упражнение 7.11 Предположим, что GHS алгоритм использует дополнительную процедуру пробуждения, которая гарантирует, что каждый узел начинает алгоритм в пределах единиц N время.
Докажите по индукции, что после не более чем 5N l — 3N единиц времени каждый узел - на 1 уровне. Докажите, что алгоритм заканчивает в пределах 5NlogN единиц время.
Упражнение 7.12 Покажите, что O (NlogN) алгоритм для выбора в плоских сетях существует.
Упражнение 7.13 Покажите, что существует 0 (NlogN) алгоритм выбора для тора без смысла направлений.
Упражнение 7.14 Покажите, что существует 0 (NlogN) алгоритм выбора для гиперкубов без смысла направлений.
Упражнение 7.15 Покажите, что существует O (N (logN + k)) алгоритм выбора для сетей с ограниченной степенью k (то есть, сети, где каждый узел имеет не более k соседей).
Вычисление распределенного алгоритма заканчивается, когда алгоритм достигает конечной конфигурации; то есть конфигурация, в которой никакие дальнейшие шаги алгоритма невозможны. Не всегда в предельной конфигурации каждый процесс находится в конечном состоянии; то есть в таком состоянии,что нет ни одного события применимого к процессу. Рассмотрим конфигурацию, в которой каждый процесс находится в состоянии, которое позволяет получать сообщения, и все каналы пусты. Такая конфигурация является конечной, но состояния процессов могут быть промежуточными состояния в вычислении. В этом случае, процессы не знают, что вычисление закончилось; такое завершение вычисления называется неявным. Завершение называется явным в процессе, если состояние этого процесса в конечной конфигурации - конечное состояние. Неявное завершение вычисления также называется завершением сообщений, потому что после достижения конечной конфигурации сообщения больше не посылаются. Явное завершение также называется завершением процессов, потому что при явном завершении алгоритма процессы закончивают свое выполнение.
Обычно более легкое разрабатывать алгоритм, который заканчивается неявно чем алгоритм , который заканчивается явно. Действительно, в время разработки алгоритма все аспекты надлежащего завершения процессов могут игнорироваться; пр разработке концентрируются на ограничении полного числа событий, которые могут произойти. С другой стороны, применение алгоритма может потребовать, чтобы процессы закончились явно. Только после явного завершения результаты вычисления могут быть расцененным как заключительные, и переменные используемые в вычислении освобождены. Тупик распределенного алгоритма также приводит конечной конфигурации; в этом случае после достижения конечной конфигурации вычисление должно быть начато снова.
В основных методах этой главы будет исследовано для преобразование заканчивающихся неявно в явно заканчивающиеся. Зная такой метод, алгоритм можно разрабатывать беря во внимание только завершение сообщений (то есть, гарантируя только то, что алгоритм закончит вычисления), после чего алгоритм преобразуется в алгоритм завершения процессов с помощью использования одного из предложенных методов. Методы состоят из двух дополнительных алгоритмов, которые взаимодействуют с данным алгоритмом завершения сообщений и друг с другом. Один из этих алгоритмов наблюдает за вычислением и некоторым образом обнаруживает , что вычисление основного алгоритма достигло конечной конфигурации. После обнаружения такого завершения он вызывает второй алгоритм, который отправляет сообщения завершения всем процессам, заставляя их войти в конечное состояние.
Наиболее трудной частью преобразования оказывается алгоритм, обнаруживающий завершение. Процедура отправки сообщений завершения довольно тривиальна и будет обсуждена кратко в Подразделе 8.1.3. В этой главе будет показано, что обнаружение завершения возможно для всех классов сетей, для которых можно получить волновой алгоритм. Эти классы включают сети, где лидер доступен, сети, где процессы имеют идкентификаторы, древовидные сети, и сети, в которых доступна топологическая информация, типа диаметра или количества процессов. С другой стороны, в Главе 9 будет показано, что для анонимных сетей неизвестного размера существует неявно заканчивающийся алгоритм, но нет явно заканчивающегося алгоритма для вычисления максимума по входам процессов. Следовательно, обнаружение завершения невозможно в анонимных сетях где неизвестен размер.
Для тех случаев, в которых возможно обнаружение завершения, мы установим нижении границы числа сообщений, используемых алгоритмом обнаружения завершения. Будет показано, что существуют алгоритмы, которые удовлетворяют этим границам. Раздел 8.1 представляет проблему формально, предлагая модель поведения распределенного вычисления и представляя низшую границу и процедуру посылки сообщений завершения. Раздел 8.2 представляет несколько решений, основанные на использовании дерева (или леса) процессов, включающего по крайней мере все процессы, которые все еще производят вычисление. Решения в этом разделе не слишком сложны и удовлетворяют низшей границе Разделе 8.1. Эти первые два раздела содержат все фундаментальные результаты касающиеся существования и сложности алгоритмов обнаружения завершения. По различным причинам один алгоритм обнаружения завершения может быть более подходящий для конкретного применения чем другой алгоритм. Поэтому, Разделы 8.3 и 8.4 представляют некоторые другие решения.
В этом подразделе будет определена модель распределенных вычислений для изучения проблемы завершения распределенных вычислений. Модель получена из модели в Главе 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).
Страницы: 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, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62
