Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 63
Текст из файла (страница 63)
Задаче о выборах была отведена роль «тестовой задачи» для сопоставления эффективности различных моделей вычислений. Поэтому мы затронем некоторые результаты, которые необходимы для проведения такого сравнения, и будем часто возвращаться к этой задаче в последующих главах (см. гл. 9, 12, 11).3. Мы сосредоточим внимание на результатах, касающихся сложности почислу обменов сообщениями; алгоритмы с улучшенной сложностью по времени, а также результаты, устанавливающие взаимосвязь между сложностью повремени и сложностью по числу обменов сообщениями, здесь не обсуждаются.7.1.
ВведениеВ задаче о выборах требуется, начав вычисление из конфигурации, в которойвсе процессы пребывают в одном и том же состоянии, достичь такой конфигурации, в которой ровно один процесс находится в особом состоянии leader, тогдакак все остальные процессы пребывают в состоянии lost. Тот процесс, который240Гл. 7. Алгоритмы избрания лидеранаходится в состоянии leader в конце вычисления, называется лидером, и о немговорится, что он был избран посредством заданного алгоритма.Определение 7 . 1 .
Алгоритмом избрания лидера называется алгоритм, который обладает следующими свойствами.1. Каждый процесс наделен одним и тем же локальным алгоритмом.2. Алгоритм является децентрализованным, т. е. вычисление может быть инициировано произвольным непустым подмножеством процессов.3. Алгоритм достигает заключительной конфигурации в каждом вычислении,и в каждой заключительной конфигурации существует ровно один процесс, который находится в состоянии leader, а все остальные процессы при этом пребывают в состоянии lost.Последнее свойство иногда бывает ослаблено и ограничено лишь требованием того, чтобы ровно один процесс находился в состоянии leader.
Тогда можетслучиться так, что избранный процесс будет осведомлен о своей победе на выборах, а проигравшие все еще не будут подозревать о своем поражении. Если заданалгоритм, удовлетворяющий этому ослабленному требованию, то его можно легко дополнить потоком сообщений, инициированным лидером, благодаря которомувсе процессы будут оповещены о результатах выборов. Это дополнительное замечание опущено в некоторых алгоритмах настоящей главы.Во всех алгоритмах этой главы процесс р наделен переменной statep, множество значений которой включает в себя состояния leader и lost.
Иногда мыбудем полагать, что значением statep является состояние sleep, до того как процесс р выполнил хоть один шаг нашего алгоритма, и состояние catid, как толькор присоединился к вычислению, но еще не был осведомлен о том, выиграл илипроиграл он эти выборы. В некоторых алгоритмах используются дополнительные состояния, наподобие active, passive и пр., которые особо отмечаются приописании алгоритма.7.1.1. Допущения, которых придерживаются в этой главеЗадача о выборах изучается в этой главе в рамках тех допущений, которыемы здесь рассмотрим.1. Система вполне асинхронна. Уже говорилось о том, что процессы неимеют доступа к общим часам и передача сообщений может длиться сколь угоднодолго или коротко.Оказывается, допущение о синхронной передаче сообщений (подразумевающее, что отправление и прием сообщения рассматриваются как единый переход) почти не влияет на результаты, относящиеся к задаче о выборах.
Читателю предоставляется возможность убедиться самостоятельно, что все алгоритмы,приведенные в этой главе, можно применять в системах с синхронной передачей сообщений и все результаты, касающиеся нижних оценок сложности, можнотакже переложить на этот случай.Допущение о глобальном отсчете времени, наподобие предположения о том,что процессы могут отслеживать реальное время и что задержка передачи сооб-7.1.
Введение241щения ограничена, действительно оказывает важное влияние на решение задачио выборах.2. Каждый процесс опознается по уникальному имени — своему отличительному признаку , — и это имя изначально известно самому процессу.Для простоты предполагалось, что отличительный признак процесса р — это само имя р. Отличительные признаки заимствованы из линейно упорядоченногомножества V, т. е.
на множестве отличительных признаков действует отношениеЧисло битов, необходимых для представления отличительного признака,обозначим w.Важное значение уникальных отличительных признаков состоит в том, что ихможно использовать не только для адресации сообщений, но и для того, чтобынарушить симметрию на множестве процессов. При проектировании алгоритма избрания лидера можно, например, постулировать, что на выборах победитпроцесс с наименьшим (или, напротив, наибольшим) по порядку отличительнымпризнаком. Наша проблема, таким образом, превращается в задачу отысканиянаименьшего отличительного признака посредством децентрализованного алгоритма. В этом случае задачу о выборах называют задачей отыскания экстремумов.Хотя некоторые из алгоритмов, которые обсуждаются в этой главе, были первоначально сформулированы так, чтобы избирался наибольший процесс, на самом деле для большинства из них мы будем пользоваться формулировкой, прикоторой избирается наименьший процесс; в каждом таком случае алгоритм, предназначенный для избрания наибольшего процесса, можно легко получить, обратив порядок, на основе которого проводится сравнение отличительных признаков.3.
Некоторые результаты в этой главе затрагивают алгоритмы сравнения. Алгоритмами сравнения называются алгоритмы, в которых используется единственная операция — сравнение отличительных признаков. Как можноувидеть из описания самих алгоритмов, все алгоритмы, рассматриваемые в этойглаве, — это алгоритмы сравнения. Всякий раз, представляя результат о нижнейоценке, мы явно указываем, касается ли она алгоритмов сравнения.Как было установлено (например, Бодлаэрдером в работе [33] для случаякольцевой сети), в асинхронных сетях произвольные алгоритмы не могут иметьсложность, меньшую, чем алгоритмы сравнения. Но, как будет показано в гл. 12,для синхронных систем это уже не так; в таких системах произвольные алгоритмыспособны иметь сложность, меньшую, нежели алгоритмы сравнения.4.
Каждое сообщение может содержать 0(w) битов. В каждом сообщении может содержаться лишь постоянное число отличительных признаков процессов. Это допущение сделано для того, чтобы справедливо сопоставлять сложность по числу обменов сообщениями для различных алгоритмов.7.1.2. Выборы и волныКак уже отмечалось, отличительные признаки процессов можно использоватьдля нарушения симметрии между процессами; алгоритм избрания можно спроектировать так, чтобы выделять процесс с наименьшим отличительным признаком.Гл. 7.
Алгоритмы избрания лидера242Согласно результатам, приведенным в §6.1.5, наименьший отличительный признак может быть вычислен процессами по ходу одной волны. Это значит, чтовыборы можно провести, запустив волну вычисления наименьшего отличительного признака, после чего процесс с наименьшим признаком становится лидером. Так как алгоритм избрания должен быть децентрализованным, этот принцип можно применять только к децентрализованным волновым алгоритмам (см.таблицу 6.18).re cp [q\: bool: integer: bool для каждого q € N e ig h pVp: Vs ta te p: { s le e p , le a d e r , lo s t )WSpw rpinit false ;init 0 ;init false ;init p ;init s le e p ;begin if р is initiator thenbegin wsp := t r u e ;forall q 6 N e ig h p do send (wakeup) to qend;while w r p < # N e i g h P dobegin receive (wakeup) ; w r p := w r p + 1 ;if not w s p thenbegin w s p := t r u e ;forall q 6 N e ig h p do send (wakeup) to qendend;(* Здесь начинает работать древесный алгоритм *)while #{<7 : ^ re c p [q \} > 1 dobegin receive (tok, r) from q ; re c p [ q ] := t r u e ;v p : = min( v p , r)end;send (tok, v p) to qa with -ire cp [q 0 ] ;receive (tok, r) from q Q ;v p := min(v p , r); (* принять решение с ответом v p *)if Vp = p then s t a t e p := l e a d e r else s t a t e p := l o s t ;forall q € N e ig h p , q Ф q 0 do send (tok, v p ) to qАлгоритм 7.1.
Алгоритм избрания лидера на деревьяхИзбрание посредством древесного алгоритма. Если топология сети имеет вид дерева, или у нас в распоряжении есть остовное дерево, выборы можнопровести, воспользовавшись древесным алгоритмом (см. §6.2.2). В древесномалгоритме требуется, чтобы среди его инициаторов были все листовые вершины. Чтобы запустить алгоритм и в том случае, когда лишь часть процессов являются инициаторами, к нему добавлен этап п о б у д к и .
Процессы, которые хотят затеять выборы, наводняют сеть сообщениями (wakeup). Булева перемен7.1. Введение243ная ws используется для того, чтобы каждый процесс не отправлял сообщение(wakeup) более одного раза, а переменная wr применяется для подсчета числасообщений (wakeup), которые получил процесс. Когда процесс получил сообщение (wakeup) по всем каналам, он запускает алгоритм 6.2, который снабженприставкой (как указано в теореме 6.12) для вычисления наименьшего отличительного признака, позволяющей, кроме того, вынудить каждый процесс принять решение. Когда процесс принимает решение, он располагает сведениями оботличительном признаке лидера; если этот признак совпадает с отличительнымпризнаком самого процесса, то он становится лидером, а в противном случае онполучает статус lost (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
