Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 64
Текст из файла (страница 64)
Алгоритмом избрания лидера называется алгоритм, который обладает следующими свойствами.1. Каждый процесс наделен одним и тем же локальным алгоритмом.2. Алгоритм является децентрализованным, т. е. вычисление может быть инициировано произвольным непустым подмножеством процессов.3. Алгоритм достигает заключительной конфигурации в каждом вычислении,и в каждой заключительной конфигурации существует ровно один процесс, который находится в состоянии leader, а все остальные процессы при этом пребывают в состоянии lost.Последнее свойство иногда бывает ослаблено и ограничено лишь требованием того, чтобы ровно один процесс находился в состоянии leader.
Тогда можетслучиться так, что избранный процесс будет осведомлен о своей победе на выборах, а проигравшие все еще не будут подозревать о своем поражении. Если заданалгоритм, удовлетворяющий этому ослабленному требованию, то его можно легко дополнить потоком сообщений, инициированным лидером, благодаря которомувсе процессы будут оповещены о результатах выборов. Это дополнительное замечание опущено в некоторых алгоритмах настоящей главы.Во всех алгоритмах этой главы процесс p наделен переменной state p , множество значений которой включает в себя состояния leader и lost.
Иногда мыбудем полагать, что значением statep является состояние sleep, до того как процесс p выполнил хоть один шаг нашего алгоритма, и состояние cand, как толькоp присоединился к вычислению, но еще не был осведомлен о том, выиграл илипроиграл он эти выборы. В некоторых алгоритмах используются дополнительные состояния, наподобие active, passive и пр., которые особо отмечаются приописании алгоритма.7.1.1.
Допущения, которых придерживаются в этой главеЗадача о выборах изучается в этой главе в рамках тех допущений, которыемы здесь рассмотрим.1. Система вполне асинхронна. Уже говорилось о том, что процессы неимеют доступа к общим часам и передача сообщений может длиться сколь угоднодолго или коротко.Оказывается, допущение о синхронной передаче сообщений (подразумевающее, что отправление и прием сообщения рассматриваются как единый переход) почти не влияет на результаты, относящиеся к задаче о выборах. Читателю предоставляется возможность убедиться самостоятельно, что все алгоритмы,приведенные в этой главе, можно применять в системах с синхронной передачей сообщений и все результаты, касающиеся нижних оценок сложности, можнотакже переложить на этот случай.Допущение о глобальном отсчете времени, наподобие предположения о том,что процессы могут отслеживать реальное время и что задержка передачи сооб-7.1.
Введение241щения ограничена, действительно оказывает важное влияние на решение задачио выборах.2. Каждый процесс опознается по уникальному имени — своему отличительному признаку, — и это имя изначально известно самому процессу.Для простоты предполагалось, что отличительный признак процесса p — это само имя p. Отличительные признаки заимствованы из линейно упорядоченногомножества P , т. е. на множестве отличительных признаков действует отношение 6. Число битов, необходимых для представления отличительного признака,обозначим w.Важное значение уникальных отличительных признаков состоит в том, что ихможно использовать не только для адресации сообщений, но и для того, чтобынарушить симметрию на множестве процессов.
При проектировании алгоритма избрания лидера можно, например, постулировать, что на выборах победитпроцесс с наименьшим (или, напротив, наибольшим) по порядку отличительнымпризнаком. Наша проблема, таким образом, превращается в задачу отысканиянаименьшего отличительного признака посредством децентрализованного алгоритма. В этом случае задачу о выборах называют задачей отыскания экстремумов.Хотя некоторые из алгоритмов, которые обсуждаются в этой главе, были первоначально сформулированы так, чтобы избирался наибольший процесс, на самом деле для большинства из них мы будем пользоваться формулировкой, прикоторой избирается наименьший процесс; в каждом таком случае алгоритм, предназначенный для избрания наибольшего процесса, можно легко получить, обратив порядок, на основе которого проводится сравнение отличительных признаков.3. Некоторые результаты в этой главе затрагивают алгоритмы сравнения.
Алгоритмами сравнения называются алгоритмы, в которых используется единственная операция — сравнение отличительных признаков. Как можноувидеть из описания самих алгоритмов, все алгоритмы, рассматриваемые в этойглаве, — это алгоритмы сравнения. Всякий раз, представляя результат о нижнейоценке, мы явно указываем, касается ли она алгоритмов сравнения.Как было установлено (например, Бодлаэрдером в работе [33] для случаякольцевой сети), в асинхронных сетях произвольные алгоритмы не могут иметьсложность, меньшую, чем алгоритмы сравнения. Но, как будет показано в гл.
12,для синхронных систем это уже не так; в таких системах произвольные алгоритмыспособны иметь сложность, меньшую, нежели алгоритмы сравнения.4. Каждое сообщение может содержать O(w) битов. В каждом сообщении может содержаться лишь постоянное число отличительных признаков процессов. Это допущение сделано для того, чтобы справедливо сопоставлять сложность по числу обменов сообщениями для различных алгоритмов.7.1.2.
Выборы и волныКак уже отмечалось, отличительные признаки процессов можно использоватьдля нарушения симметрии между процессами; алгоритм избрания можно спроектировать так, чтобы выделять процесс с наименьшим отличительным признаком.242Гл. 7. Алгоритмы избрания лидераСогласно результатам, приведенным в § 6.1.5, наименьший отличительный признак может быть вычислен процессами по ходу одной волны. Это значит, чтовыборы можно провести, запустив волну вычисления наименьшего отличительного признака, после чего процесс с наименьшим признаком становится лидером. Так как алгоритм избрания должен быть децентрализованным, этот принцип можно применять только к децентрализованным волновым алгоритмам (см.таблицу 6.18).var wspwrprecp [q]vpstatep:::::boolintegerbool для каждого q ∈ NeighpP(sleep, leader, lost)initinitinitinitinitfalse ;0;false ;p;sleep ;begin if p is initiator thenbegin wsp := true ;forall q ∈ Neighp do send hwakeupi to qend;while wrp < #Neighp dobegin receive hwakeupi ; wrp := wrp + 1 ;if not wsp thenbegin wsp := true ;forall q ∈ Neighp do send hwakeupi to qendend;(* Здесь начинает работать древесный алгоритм *)while #{q : ¬recp [q] } > 1 dobegin receive htok, ri from q ; recp [q] := true ;vp := min(vp , r)end;send htok, vp i to q0 with ¬recp [q0 ] ;receive htok, ri from q0 ;vp := min(vp , r); (* принять решение с ответом vp *)if vp = p then statep := leader else statep := lost ;forall q ∈ Neighp , q 6= q0 do send htok, vp i to qendАлгоритм 7.1.
Алгоритм избрания лидера на деревьяхИзбрание посредством древесного алгоритма. Если топология сети имеет вид дерева, или у нас в распоряжении есть остовное дерево, выборы можнопровести, воспользовавшись древесным алгоритмом (см. § 6.2.2). В древесномалгоритме требуется, чтобы среди его инициаторов были все листовые вершины. Чтобы запустить алгоритм и в том случае, когда лишь часть процессов являются инициаторами, к нему добавлен этап побудки. Процессы, которые хотят затеять выборы, наводняют сеть сообщениями hwakeupi. Булева перемен-7.1.
Введение243ная ws используется для того, чтобы каждый процесс не отправлял сообщениеhwakeupi более одного раза, а переменная wr применяется для подсчета числасообщений hwakeupi, которые получил процесс. Когда процесс получил сообщение hwakeupi по всем каналам, он запускает алгоритм 6.2, который снабженприставкой (как указано в теореме 6.12) для вычисления наименьшего отличительного признака, позволяющей, кроме того, вынудить каждый процесс принять решение.
Когда процесс принимает решение, он располагает сведениями оботличительном признаке лидера; если этот признак совпадает с отличительнымпризнаком самого процесса, то он становится лидером, а в противном случае онполучает статус lost (см. алгоритм 7.1).Теорема 7.2. Алгоритм 7.1 решает задачу о выборах на древесных сетях с использованием O(N) обменов сообщениями, затрачивая при этомO(D) единиц времени.Д о к а з а т е л ь с т в о.
Когда хоть один процесс запускает данный алгоритм, все процессы отправляют сообщение hwakeupi всем своим соседям, икаждый процесс запускает выполнение древесного алгоритма после получениясообщения hwakeupi от каждого соседа. Все процессы завершают выполнениедревесного алгоритма с одним и тем же значением переменной v, а именно cнаименьшим отличительным признаком среди всех процессов. И (единственный)процесс с таким признаком завершит работу в состоянии leader, а все прочиепроцессы — в состоянии lost.По каждому каналу передаются два сообщения hwakeupi и два сообщенияhtok, ri, и поэтому сложность по числу обменов сообщениями становится равной 4N − 4.
По истечении D единиц времени, после того как первый процессзапустил наш алгоритм, каждый процесс уже отправит сообщения hwakeupi, и,следовательно, спустя D + 1 единиц времени каждый процесс уже запустит волну. И в самом деле, нетрудно увидеть, что первое решение будет принято спустяD единиц времени после начала движения волны, а последнее решение будетпринято спустя D единиц времени после первого, и поэтому общее затраченноевремя становится равным 3D+1. Более подробный анализ позволяет обнаружить,что алгоритм всегда завершается спустя 2D единиц времени, но это оставленочитателю в качестве упражнения (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
