Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 73
Текст из файла (страница 73)
Алгоритм Корача–Каттена–МоранаМы будем рассматривать алгоритм 7.13. Чтобы привести маркеры одногои того же уровня совместно в один процесс, каждому маркеру предписывается один из трех режимов: захват, погоня или ожидание. Всякий маркер будемпредставлять в виде пары (q, l), где q — это инициатор данного маркера, а l — этоего уровень. Переменная levp будет обозначать уровень, на котором пребываетпроцесс p, а переменная catp представляет инициатора того последнего маркера,который был захвачен процессом p, но уцелел и был переправлен эти процессомдалее (это и есть текущий активный обход процесса p). Переменная wait pпринимает значение udef, если ни один из маркеров не пребывает в режимеожидания в процессе p, и значение этой переменной равно q, если некоторыймаркер (q, levp) пребывает в режиме ожидания в процессе p.
Переменная last p7.4. Алгоритм Корача—Каттена—Морана275предназначена для маркеров, пребывающих в режиме погони: она указывает натого соседа, которому процесс p переправил захваченный им маркер уровня lev p ,если только догоняющий маркер уже не был отправлен вслед за ним в погоню;в таком случае lastp = udef. Наш алгоритм взаимодействует с алгоритмом обхода за счет обращения к функции trav: эта функция либо указывает того соседа,которому нужно переправить маркер, либо заявляет о принятии решения, еслиданный обход завершился.Маркер (q, l) инициируется в режиме захвата, и в этом режиме он подчиняется алгоритму обхода (как и в случае IV для алгоритма 7.13), до тех пор покане сложится одна из следующих ситуаций.1. Алгоритм обхода завершен, и в таком случае процесс q становится лидером (см.
вариант IV в описании алгоритма 7.13).2. Маркер достиг такого узла p, для которого выполняется неравенство lev p >> l; в этом случае наш маркер подавляется. (Этот вариант подразумевается в алгоритме 7.13; все условия в этом алгоритме требуют выполнения соотношенияl > levp или l = levp).3. Маркер достиг такого узла, в котором его уже ожидает другой маркеруровня l; тогда оба маркера подавляются, и из этого узла начинается новыйобход (см. вариант II в описании алгоритма 7.13).4.
Маркер достиг узла уровня l, который посетил последним некоторый маркер с отличительным признаком catp > q (см. вариант VI) или маркер в режимепогони (см. вариант III); тогда наш маркер переходит в режим ожидания и остается в этом узле.5. Маркер достиг узла уровня l, в котором в последний раз побывал некоторый маркер в режиме захвата с отличительным признаком cat p < q; тогданаш маркер переходит в режим погони и переправляется по тому же каналу, покоторому был отправлен предыдущий маркер (см. вариант V).Маркер (q, l) в режиме погони переправляется в каждом узле по тому каналу,по которому был отправлен самый последний из посетивших этот узел маркеров,если только не складывается одна из следующих ситуаций.1.
Маркер достиг процесса уровня levp > l; тогда наш маркер подавляется.2. Маркер достиг процесса, в котором хранится маркер уровня l, пребывающий в режиме ожидания; тогда оба маркера изымаются и в этом процессеначинается новый обход (см. вариант II).3. Маркер достиг процесса уровня l, и при этом последний из посетившихэтот процесс маркеров пребывал в режиме погони; тогда наш маркер переходитв режим ожидания (см.
вариант III).Маркер в режиме ожидания остается в том процессе, которого он достиг, до техпор пока не сложится одна из следующих ситуаций.1. Маркер более высокого уровня достигнет того же самого процесса; тогдаожидающий маркер будет подавлен (см. вариант I).2. Маркер того же самого уровня достиг того же самого процесса; тогда обамаркера изымаются, и в данном процессе начинается новый обход более высокогоуровня (см. вариант II).276Гл. 7.
Алгоритмы избрания лидераВ алгоритме 7.13 все переменные и переносимые маркерами данные, касающиесяалгоритма обхода, не принимались во внимание. Отметим, что если процесс pполучает маркер, уровень которого превосходит lev p , то этот маркер пребываетв режиме захвата и его инициатором является процесс, отличный от p. Если жеобход завершается в узле p, то p становится лидером и отправляет сообщениявсем процессам, призывая их прекратить работу.Корректность и сложность. Для доказательства корректности алгоритмаКорача—Каттена—Морана будет показано, что число маркеров, порожденныхна каждом уровне, сокращается, до тех пор пока на некотором уровне не будетвыпущен только один маркер, инициатор которого и становится лидером.Лемма 7.22. Если на уровне l было порождено k > 1 маркеров, то науровне l + 1 будет порождено не менее одного и не более k/2 маркеров.Д о к а з а т е л ь с т в о.
Поскольку при порождении одного маркера уровня l + 1 подавляются два маркера уровня l, всего на уровне l + 1 может бытьвыпущено не более k/2 маркеров.Предположим, что найдется такой уровень l, что на уровне l было порожденоk > 1 маркеров, а на уровне l + 1 ни одного. Обозначим символом q процессс наибольшим отличительным признаком, который породил маркер на уровне l.Маркер (q, l) не завершает обход, так как он достигает некоторого процесса p,который уже отправил другой маркер уровня l.
Когда это произойдет впервые,маркер (q, l) станет преследователем или, если процесс p уже отправил какой-топреследующий маркер, перейдет в режим ожидания. В любом случае это означает, что в сети есть преследующий маркер уровня l.Рассмотрим маркер (r, l) с наименьшим отличительным признаком, за которым был отправлен в погоню один из преследующих маркеров. Сам маркер (r, l)не может быть преследователем, поскольку преследователи гонятся за маркерами с меньшим отличительным признаком. Поэтому мы можем предполагать, чтомаркер (r, l) переходит в режим ожидания, как только он достигнет процесса p 0 ,который уже отправил какой-либо другой маркер уровня l.
Пусть p00 — последний из процессов на пути, по которому следует маркер (r, l), причем этот процессполучил после отправления (r, l) маркер, пребывавший в режиме захвата, который перешел затем в разряд преследователей маркера r. Этот преследующиймаркер либо настигнет маркер (r, l) в узле p0 , либо прервет погоню, если обнаружит какой-нибудь маркер, пребывающий в режиме ожидания, ранее чем будетдостигнут узел p0 .
В обоих случаях, вопреки предположению, будет выработанмаркер уровня l + 1.Теорема 7.23. Алгоритм Корача—Каттена—Морана (алгоритм 7.13)является алгоритмом избрания лидера.Д о к а з а т е л ь с т в о. Допустим, что хотя бы один процесс запустил этоталгоритм.
Согласно предыдущей лемме число маркеров, порожденных на каждом уровне, уменьшается, и поэтому найдется уровень, например уровень l, накотором будет порожден всего лишь один маркер, скажем (q, l). Ни один из мар-7.4. Алгоритм Корача—Каттена—Морана277керов уровня l0 < l не завершил обход, и поэтому ни один из них не привел ктому, что некоторый процесс был избран лидером. Единственный маркер уровняl сталкивается только с такими процессами, уровень которых уступает l или длякоторых выполняется равенство cat = q (если этот маркер достигает процесса,который он уже посетил ранее). В обоих случаях процессы переправляют егодалее.
Следовательно, обход завершится, и процесс q будет избран лидером.Функцию f назовем выпуклой, если выполняется неравенство f(a) + f(b) 66 f(a + b). Мы оценим здесь сложность нашего алгоритма исходя из предположения, что в его основу положен алгоритм f(x) -обхода (см. § 6.6.3), где f —выпуклая функция.Теорема 7.24. Если использовать произвольный алгоритм f(x)-обхода,где f — выпуклая функция, то алгоритм избрания лидера Корача—Каттена—Морана, будучи запущен k процессами-инициаторами, решит задачуо выборах, ограничившись (1 + log k) [f(N) + N] обменами сообщениями.Д о к а з а т е л ь с т в о. Если алгоритм был запущен k процессами, то науровне l может быть порождено не более 2−l k маркеров, откуда следует, чтонаивысший уровень, который может быть достигнут, не превосходит величиныblog kc.На любом уровне каждый процесс отправляет маркер в режиме захвата самое большее с одним отличительным признаком.
Если на некотором уровне lесть маркеры с отличительными признаками p1 , . . . , pj и имеется Ni процессов,отправивших маркеры (pi , l), пребывающие в режиме захвата, то справедливоjPнеравенствоNi 6 N. Так как используемый алгоритм обхода — это алгоритмi=1f(x)-обхода, маркеры (pi , l), остающиеся в режиме захвата, были переправленыне более f(Ni) раз, и поэтому общее число обменов сообщениями, сопряженныхс передачей маркеров уровня l, пребывающих в режиме захвата, не превосходитjPf(Ni), которая, в свою очередь, не превышает f(N), ибо функция fвеличиныi=1выпуклая. На любом уровне каждый процесс отправляет не более одного догоняющего маркера, и, следовательно, общее количество догоняющих маркеров накаждом уровне не превосходит N.Итак, мы имеем не более (1 + log k) различных уровней, на каждом из которыхсовершается самое большее f(N) + N обменов сообщениями.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
