Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно).pdf), страница 105

Вычисления в гиперкубах397линейные и постоянные и получим в итоге следующую цепочку равенств∞∞XXT (d)T (2c)=d+1222c+1d=0=c=0∞Xc=0=4 · 2c + 2c − 222c+1∞ X4 · 2cc=012=3 ·+22c+1X∞c=0+∞XT (2c + 1)c=0∞Xc=022c+2=6 · 2c + 2c − 2=22c+2∞ X6 · 2c 2c2c −+ 2c+2 ++222c+122c+2c=012c∞ X22 −=+22c+122c+2c=0X∞c3+ ·−84c−1c=0X∞13− ·=24cc=012= 3 ·2= 7++2−233 16·8 9−3 4· =2 323=5 .23Отсюда следует, что E(n) < 5 · N.11.3.3. Алгоритм потока по многим путямТеперь мы представим алгоритм, вычисляющий восприятие направления вгиперкубе размерности n, и этот алгоритм послужит нам опорой при разработкеалгоритма широковещательного распространения сообщений, имеющего линейную сложность. В алгоритме, который мы будем рассматривать, предполагается,что есть процесс, назначенный на роль инициатора алгоритма (лидера), и каналы связи, примыкающие к лидеру, помечены произвольным образом числами0, .

. . , n − 1. Разметка каналов инициатора однозначно определяет восприятиенаправления, о чем свидетельствует следующая теорема (которую мы приводимздесь без доказательства).Теорема 11.20. Пусть задана вершина w и разметка P дуг, исходящихиз w, числами, начинающимися с 0 и оканчивающимися n − 1. Тогда существует единственная ориентация L, удовлетворяющая условию Lw (v) == P (v) для каждого соседа вершины w.Наш алгоритм вычисляет в точности эту ориентацию и, кроме того, единственную свидетельствующую разметку вершин, в которой лидер помечен набо-398Гл.

11. Восприятие направления и ориентацияром (0, . . . , 0). В алгоритме используются три типа сообщений. Лидер отправляеткаждому из своих соседей метку того канала, который их соединяет, в сообщенияхhdmn, ii. Нелидеры отправляют свои метки вершин другим процессам в сообщениях hiam, nlai. Нелидеры информируют своих соседей о метках каналов связив сообщениях hlabl, ii.begin num_recp := 0 ; disp := 0 ; lblp := (0, .

. . , 0) ;for l = 0 to n − 1 do(* Отправление сообщений на этапе 1 *)begin send hdmn, li по каналу l ;p [l] := lend;while num_recp < n do(* Прием сообщений на этапе 2 *)begin receive hlabl, li ;(* обязательно по каналу l *)num_recp := num_recp + 1endendАлгоритм 11.6. Ориентация гиперкуба (Инициатор)Рассматриваемый алгоритм состоит из двух процедур — алгоритм 11.6 (длялидера) и алгоритм 11.7 (для нелидеров). Работа алгоритма разбита на два этапа: на первом этапе поток сообщений расходится от лидера, а на втором этапепоток сообщений направлен к лидеру.

Предшественником вершины p называется такой ее сосед q, для которого выполняется неравенство d(q, w) < d(p, w),а последователем вершины p называется такой сосед q вершины p, для которого выполняется неравенство d(q, w) > d(p, w).

В гиперкубе у вершины p нетсоседей q, для которых выполнялось бы равенство d(q, w) = d(p, w), и всякаявершина, расположенная на расстоянии d от лидера, имеет d предшественникови n − d последователей.Лидер запускает алгоритм, отправляя сообщение hdmn, ii по каналу связи,помеченному i. Когда процессу p, не являющемуся лидером, становится известнорасстояние disp от него до лидера и, кроме того, ему доставлены все сообщения отего предшественников, процесс p может приступать к вычислению пометки nla pсвоей вершины.

Он отправляет эту пометку в сообщении hiam, nla p i своим последователям. Чтобы убедиться в том, что p может осуществить это, рассмотримвначале случай, когда p получает сообщение hdmn, ii по каналу l. Так как сообщение было отправлено лидером, disp = 1 и все его остальные соседи являютсяего последователями. Процессор p помечает свою вершину двоичным набором,в котором в позиции i ставится 1, а во всех остальных позициях ставится 0.(В таком случае меткой канала l становится i.) Далее p отправляет сообщениеhiam, nlap i по всем каналам k 6= l.Теперь обратимся к случаю, когда процесс p получает сообщение hiam, labeli.Из этого сообщения извлекается расстояние d от отправителя сообщения до лидера (оно равно количеству единиц в наборе label).

Так как сообщения hiam, labeliотправляются только последователям, отправитель этого сообщения является11.3. Вычисления в гиперкубах399begin num_recp := 0 ; disp := n + 1 ; lblp := (0, . . . , 0) ;forall l do neip [l] := nil ;while num_recp < disp do(* Прием сообщений на этапе 1 *)begin receive msg по каналу l ; num_recp := num_recp + 1 ;(* msg — это сообщение одного из двух типов hdmn, ii или hiam, nlai *)if msg is hdmn, ii thenbegin disp := 1 ;neip [l] := (0, . . .

, 0) ; lblp [i] := 1(* Теперь в наборе lblp = (0, .., 1, .., 0) есть только одна 1 *)endelsebegin disp := 1 + # of 1’s in nla ;lblp := (lblp or nla) ;neip [l] := nlaendend;(* Отправление сообщений на этапе 1 *)forall l with neip [l] = nil dosend hiam, lblp i по каналу l ;while num_recp < n do (* прием сообщений на этапе 2 *)begin receive hlabl, ii по каналу l ;num_recp := num_recp + 1 ; p [l] := iend;(* Отправление сообщений на этапе 2 *)forall l with neip [l] 6= nil dobegin p [l] := бит, которым различаются lblp и neip [l] ;send hlabl, p [l] i по каналу lendendАлгоритм 11.7.

Ориентация гиперкуба (Неинициатор)предшественником процесса p, и поэтому disp = d + 1. Отсюда становится ясно,сколько предшественников имеет процесс, и p ожидает, пока не будут полученывсе disp сообщений hiam, labeli. После этого процесс p определяет пометку своей вершины, вычислив покомпонентную дизъюнкцию тех пометок, которые былиим получены, и отправляет ее тем из своих соседей, от которых не было доставлено сообщений hiam, labeli, так как именно они являются его последователями.На первом этапе каждый процесс p, не являющийся лидером, вычисляет своюпометку.

На втором этапе каждый процесс p, не являющийся лидером, узнает отсвоих последователей ориентацию каналов, связывающих его с ними, и вычисляет ориентацию своих каналов, связывающих процесс p с его предшественниками.Эта информация отправляется по каждому каналу в сообщении hlabl, ii. Процессор отправляет сообщения hlabl, ii своим предшественникам, как только онполучает подобные сообщения от всех своих последователей, и после этого пре-400Гл.

11. Восприятие направления и<b>Текст обрезан, так как является слишком большим</b>.