Реферат: Распределенные алгоритмы
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 представляют некоторые другие решения.
Страницы: 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, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105
