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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 53)

Тогда граф Т = (Р, Ет), где Ет == {qr : q Ф р А г = father q}, является остовным деревом, направленнымк р.Д о к а з а т е л ь с т в о . Поскольку число вершин в Т превосходит число дугна единицу, достаточно показать, что Т не содержит циклов. И это действительнотак, поскольку для еч, первого события в q, наличие дуги q re Етвлечет ег ■<eq,а отношение ■< является частичным порядком.□В качестве события /, упомянутого в третьем пункте определения 6 .1, можновыбрать событие отправления сообщения для всех процессов q за исключениемтого процесса, в котором происходит событие decide.Лемма 6.4.

Пусть С — волна и dp e С — событие решения в процессе р.ТогдаVq Ф р : 3/ е Cq : (/ Д dp А / — событие отправления сообщения).Д о к а з а т е л ь с т в о . Так как С — волна, существует событие / € Cq, ко­торое является причинно-следственным предшественником события dp. Выберемв качестве / последнее событие в Cq, предшествующее dp. Чтобы показать, что/ — это событие отправления сообщения, заметим, что из определения причинноследственной зависимости (определение 2 .2 0 ) вытекает существование такой по­следовательности (причинно-следственной цепочки)/ = во, е \ , .

. . , ek = d p ,что для каждого i < k события е* и e,+i являются либо последовательнымисобытиями в одном и том же процессе, либо парой соответствующих событийотправления-приема сообщения. Поскольку / — последнее событие в процессе q,предшествующее событию dp, событие е\ происходит в процессе, отличном от q.Значит, / — событие отправления сообщения.□Нижние оценки сложности волн.

Из леммы 6.4 немедленно вытекает ниж­няя оценка N — 1 для числа сообщений, которыми обмениваются процессы припрохождении волны. Если событие decide происходит только в инициаторе волны(что имеет место для алгоритмов обхода), то оценка увеличивается до N сооб­щений и волновые алгоритмы для произвольных сетей используют по меньшеймере |£| сообщений.Теорема 6.5. Пусть С — такая волна с одним инициатором р, что в рпроисходит событие решения dp. Тогда в вычислении С происходит обменпо крайней мере N сообщениями.Д о к а з а т е л ь с т в о .

По лемме 6.2 каждому событию в С предшествуетнекоторое событие в процессе р, и, воспользовавшись причинно-следственной198Гл. 6.Волновые алгоритмы и алгоритмы обходав неиспользуемый каналцепочкой наподобие той, которая фигурировала в доказательстве леммы 6.4,нетрудно показать, что в р произойдет хотя бы одно событие отправления сооб­щения. По лемме 6.4 событие отправления сообщения также произойдет и в каж­дом другом процессе, а это означает, что произойдет как минимум N обменовсообщениями.□Теорема 6 .6 .

Пусть А — волновой алгоритм для произвольной сети,в котором не используются первоначальные сведения об отличительныхпризнаках соседей. Тогда А в каждом вычислении проводит по меньшеймере |£| обменов сообщениями.Д о к а з а т е л ь с т в о . Предположим, что А имеет вычисление С, в кото­ром проводится менее |£| обменов сообщениями, т. е. существует канал, напри­мер, ху, по которому не передаются сообщения в вычислении С (см. рис. 6.1.2).Рассмотрим сеть G', полученную за счет добавления одной точки z в каналемежду х и у.

Поскольку точки не идентифицируют своих соседей, начальное со­стояние х и у в G' будет тем же самым, что и в сети G. Это будет, конечно,справедливо и для всех остальных точек G. Следовательно, все события в Спроизойдут в том же самом порядке начиная с исходной конфигурации G', нотеперь событию decide не предшествует никакое событие в z.□В гл. 7 будет доказана уточненная нижняя оценка сложности по числу сооб­щений для децентрализованных волновых алгоритмов на кольцах и произволь­ных сетях без предварительных сведений о соседях (см. следствия 7.14 и 7.16).6.1.3. Распространение информации с обратной связьюВ этом параграфе будет показано, что волновые алгоритмы — это как разте самые алгоритмы, которые необходимы для широковещательного распростра­нения информации всем процессам с тем условием, что некоторые выделенныепроцессы должны получить подтверждение о завершении выполнения широкове­щательной связи. Это требование применительно к распространению информа­ции с обратной связью (Propagation of Information with Feedback, PIF) приводитк следующей задаче (см.

[174]). Сформировано подмножество процессов, обла­6.1. Определение и применение волновых алгоритмов199дающих некоторым сообщением М (одним и тем же для всех процессов этогоподмножества), которое должно быть распространено широковещательно, т. е.все процессы должны получить и принять М. Некоторые выделенные процессыдолжны быть уведомлены о завершении широковещательной связи; это означает,что в них должно быть выработано специальное событие notify с тем услови­ем, что событие notify произойдет только в том случае, когда все процессы ужеполучат сообщение М. Алгоритм будет использовать конечное число сообщений.Уведомление в алгоритме PIF рассматривается как событие решения.Теорема 6.7. Каждый PIF-алгоритм — это волновой алгоритм.Д о к а з а т е л ь с т в о .

Пусть Р — это некоторый PIF-алгоритм. Тогда каж­дое вычисление алгоритма Р конечно и в каждом вычислении происходит уведом­ляющее событие (decide). Если в некотором вычислении алгоритма Р происхо­дит уведомление dp, которому не предшествует никакое событие в процессе q , топо теореме 2.21 и утверждению 2.23 существует такое выполнение алгоритма Р,в котором уведомление происходит, до того как q получит какое-либо сообщение,что противоречит нашим требованиям.□Необходимо иметь в виду, что теорема 2.21 справедлива только для системс асинхронной передачей сообщений (см.

упражнение 6 . 1 ).Теорема 6 .8 . Каждый волновой алгоритм может быть использован в ка­честве PIF-алгоритма.Д о к а з а т е л ь с т в о . Пусть А — волновой алгоритм. Чтобы представить Акак PIF-алгоритм, процессы, первоначально хранящие М , следует считать стар­товыми. Информацию М нужно добавить к каждому сообщению, передаваемомув алгоритме А. Это возможно, поскольку по построению стартовые процессыалгоритма А первоначально обладают информацией М , а последователи не от­правляют сообщений, до тех пор пока сами они не получат хоть одно сообщение,а значит так же станут осведомлены о М. Событию decide в волне предшествуетпо крайней мере одно событие в каждом процессе. Следовательно, когда событиерешения произойдет, каждый процесс будет уже осведомлен о М, и это можнорасценивать как требуемое PIF-алгоритмом уведомление notify.□Построенный PIF-алгоритм имеет такую же сложность, как и А, и он обладаетвсеми теми же свойствами, упомянутыми в § 6 .1.1, что и А, за исключением бито­вой сложности.

Битовая сложность может быть понижена, если присоединять Мтолько к самому первому сообщению, отправляемому по каждому каналу. Еслиw — число битов сообщения М, то битовая сложность окончательного алгоритмапревзойдет битовую сложность алгоритма А на w\E\.6.1.4. СинхронизацияВ этом параграфе мы покажем, что волновые алгоритмы — это как раз теалгоритмы, которые необходимы для того, чтобы добиться глобальной синхрони­зации между процессами. Требование синхронизации (SYN) выдвинуто в следу­ющей задаче; см. [79]. В каждом процессе q должно быть выполнено событие ач,200Гл.

6.Волновые алгоритмы и алгоритмы обходаи в некоторых процессах событие Ьр должно быть выполнено так, чтобы выпол­нение aq произошло по времени ранее, нежели выполнение любого из событий Ьр.Алгоритм должен использовать конечное число сообщений.В SYN-алгоритме события Ьр рассматриваются как события decide.Теорема 6.9. Каждый SYN-алгоритм является волновым алгоритмом.Д о к а з а т е л ь с т в о . Пусть S — это некоторый SYN-алгоритм.

Тогда каж­дое вычисление алгоритма S конечно и в каждом вычислении происходит событиеЬр (decide). Если в некотором вычислении алгоритма S происходит событие Ьр,у которого нет причинно-следственного предшественника aq, то по теореме 2 .2 1 иутверждению 2.23, существует вычисление алгоритма S, в котором Ьр происходитранее aq.□Теорема 6.10.

Каждый волновой алгоритм можно использовать в ка­честве SYN-алгоритма.Д о к а з а т е л ь с т в о . Пусть А — волновой алгоритм. Чтобы использо­вать А в качестве SYN-алгоритма, каждому процессу q требуется выполнить aq,до того как q в рамках алгоритма А отправит некоторое сообщение или приметрешение. Событие Ьр произойдет в р после события decide. По лемме 6.4 вся­кому событию decide причинно-следственно предшествует событие aq в каждомпроцессе q.□Построенный SYN-алгоритм имеет ту же самую сложность по числу сооб­щений, что и А, а также обладает всеми прочими свойствами алгоритма А, упо­мянутыми в § 6 .

1 . 1 .6.1.5. Вычисление функций точной нижней граниВ этом параграфе будет показано, что волновые алгоритмы — это в точностиалгоритмы, необходимые для вычисления функции, значение которой существен­но зависит от входных данных каждого процесса. Представителем такого классафункций могут служить функции точной нижней грани по всем входам, еслиэто возможно для частично упорядоченного множества.Пусть (X,— частично упорядоченное множество. Тогда элемент с называ­ется точной нижней гранью элементов а и Ь, если с ^ а, с ^ b и Vd: (d ^ a/\d ^ bДопустим, что X обладает тем свойством, что точная нижняя грань всегда суще­ствует. В таком случае эта точная нижняя грань определяется однозначно и обо­значается а П Ь.

Характеристики

Список файлов книги