Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 54
Текст из файла (страница 54)
Если событие decide происходит только в инициаторе волны(что имеет место для алгоритмов обхода), то оценка увеличивается до N сообщений и волновые алгоритмы для произвольных сетей используют по меньшеймере |E| сообщений.Теорема 6.5. Пусть C — такая волна с одним инициатором p, что в pпроисходит событие решения dp . Тогда в вычислении C происходит обменпо крайней мере N сообщениями.Д о к а з а т е л ь с т в о. По лемме 6.2 каждому событию в C предшествуетнекоторое событие в процессе p, и, воспользовавшись причинно-следственной198@Гл. 6.yx@@6.1. Определение и применение волновых алгоритмовВолновые алгоритмы и алгоритмы обхода@yy@ H H H@HGAAAA@zy yx@@@@@yyHHG0AAAAHHРис. 6.1. Вставка процесса в неиспользуемый каналцепочкой наподобие той, которая фигурировала в доказательстве леммы 6.4,нетрудно показать, что в p произойдет хотя бы одно событие отправления сообщения. По лемме 6.4 событие отправления сообщения также произойдет и в каждом другом процессе, а это означает, что произойдет как минимум N обменовсообщениями.Теорема 6.6.
Пусть A — волновой алгоритм для произвольной сети,в котором не используются первоначальные сведения об отличительныхпризнаках соседей. Тогда A в каждом вычислении проводит по меньшеймере |E| обменов сообщениями.Д о к а з а т е л ь с т в о. Предположим, что A имеет вычисление C, в котором проводится менее |E| обменов сообщениями, т. е. существует канал, например, xy, по которому не передаются сообщения в вычислении C (см. рис.
6.1.2).Рассмотрим сеть G0 , полученную за счет добавления одной точки z в каналемежду x и y. Поскольку точки не идентифицируют своих соседей, начальное состояние x и y в G0 будет тем же самым, что и в сети G. Это будет, конечно,справедливо и для всех остальных точек G. Следовательно, все события в Cпроизойдут в том же самом порядке начиная с исходной конфигурации G 0 , нотеперь событию decide не предшествует никакое событие в z.В гл. 7 будет доказана уточненная нижняя оценка сложности по числу сообщений для децентрализованных волновых алгоритмов на кольцах и произвольных сетях без предварительных сведений о соседях (см. следствия 7.14 и 7.16).6.1.3.
Распространение информации с обратной связьюВ этом параграфе будет показано, что волновые алгоритмы — это как разте самые алгоритмы, которые необходимы для широковещательного распространения информации всем процессам с тем условием, что некоторые выделенныепроцессы должны получить подтверждение о завершении выполнения широковещательной связи. Это требование применительно к распространению информации с обратной связью (Propagation of Information with Feedback, PIF) приводитк следующей задаче (см. [174]). Сформировано подмножество процессов, обла-199дающих некоторым сообщением M (одним и тем же для всех процессов этогоподмножества), которое должно быть распространено широковещательно, т. е.все процессы должны получить и принять M.
Некоторые выделенные процессыдолжны быть уведомлены о завершении широковещательной связи; это означает,что в них должно быть выработано специальное событие notify с тем условием, что событие notify произойдет только в том случае, когда все процессы ужеполучат сообщение M. Алгоритм будет использовать конечное число сообщений.Уведомление в алгоритме PIF рассматривается как событие решения.Теорема 6.7.
Каждый PIF-алгоритм — это волновой алгоритм.Д о к а з а т е л ь с т в о. Пусть P — это некоторый PIF-алгоритм. Тогда каждое вычисление алгоритма P конечно и в каждом вычислении происходит уведомляющее событие (decide). Если в некотором вычислении алгоритма P происходит уведомление dP , которому не предшествует никакое событие в процессе q, топо теореме 2.21 и утверждению 2.23 существует такое выполнение алгоритма P,в котором уведомление происходит, до того как q получит какое-либо сообщение,что противоречит нашим требованиям.Необходимо иметь в виду, что теорема 2.21 справедлива только для системс асинхронной передачей сообщений (см. упражнение 6.1).Теорема 6.8.
Каждый волновой алгоритм может быть использован в качестве PIF-алгоритма.Д о к а з а т е л ь с т в о. Пусть A — волновой алгоритм. Чтобы представить Aкак PIF-алгоритм, процессы, первоначально хранящие M, следует считать стартовыми.
Информацию M нужно добавить к каждому сообщению, передаваемомув алгоритме A. Это возможно, поскольку по построению стартовые процессыалгоритма A первоначально обладают информацией M, а последователи не отправляют сообщений, до тех пор пока сами они не получат хоть одно сообщение,а значит так же станут осведомлены о M. Событию decide в волне предшествуетпо крайней мере одно событие в каждом процессе. Следовательно, когда событиерешения произойдет, каждый процесс будет уже осведомлен о M, и это можнорасценивать как требуемое PIF-алгоритмом уведомление notify.Построенный PIF-алгоритм имеет такую же сложность, как и A, и он обладаетвсеми теми же свойствами, упомянутыми в § 6.1.1, что и A, за исключением битовой сложности.
Битовая сложность может быть понижена, если присоединять Mтолько к самому первому сообщению, отправляемому по каждому каналу. Еслиw — число битов сообщения M, то битовая сложность окончательного алгоритмапревзойдет битовую сложность алгоритма A на w|E|.6.1.4. СинхронизацияВ этом параграфе мы покажем, что волновые алгоритмы — это как раз теалгоритмы, которые необходимы для того, чтобы добиться глобальной синхронизации между процессами. Требование синхронизации (SYN) выдвинуто в следующей задаче; см. [79] . В каждом процессе q должно быть выполнено событие a q ,200Гл.
6.Волновые алгоритмы и алгоритмы обходаи в некоторых процессах событие bp должно быть выполнено так, чтобы выполнение aq произошло по времени ранее, нежели выполнение любого из событий b p .Алгоритм должен использовать конечное число сообщений.В SYN-алгоритме события bp рассматриваются как события decide.Теорема 6.9. Каждый SYN-алгоритм является волновым алгоритмом.Д о к а з а т е л ь с т в о. Пусть S — это некоторый SYN-алгоритм. Тогда каждое вычисление алгоритма S конечно и в каждом вычислении происходит событиеbp (decide). Если в некотором вычислении алгоритма S происходит событие b p ,у которого нет причинно-следственного предшественника aq , то по теореме 2.21 иутверждению 2.23, существует вычисление алгоритма S, в котором b p происходитранее aq .Теорема 6.10.
Каждый волновой алгоритм можно использовать в качестве SYN-алгоритма.Д о к а з а т е л ь с т в о. Пусть A — волновой алгоритм. Чтобы использовать A в качестве SYN-алгоритма, каждому процессу q требуется выполнить a q ,до того как q в рамках алгоритма A отправит некоторое сообщение или приметрешение. Событие bp произойдет в p после события decide. По лемме 6.4 всякому событию decide причинно-следственно предшествует событие aq в каждомпроцессе q.Построенный SYN-алгоритм имеет ту же самую сложность по числу сообщений, что и A, а также обладает всеми прочими свойствами алгоритма A, упомянутыми в § 6.1.1.6.1.
Определение и применение волновых алгоритмов201осведомлены о завершении вычисления. Они записывают результат вычисленияв переменной out, и им не разрешается впоследствии изменять значение этойпеременной.Запись значения в переменную out, рассматривается как событие decideв INF-алгоритме.Теорема 6.11. Каждый INF-алгоритм является волновым алгоритмом.Д о к а з а т е л ь с т в о. Пусть I — это некоторый INF-алгоритм.
Предположим, что существует вычисление C алгоритма I с начальной конфигурацией ,в котором процесс p записывает значение J в переменной out p , и этому событию записи не предшествует никакое событие в процессе q. Тогда рассмотримначальную конфигурацию 0 , отличающуюся от только тем, что q имеет другие входные данные j0q , которые выбраны так, чтобы выполнялось соотношениеJ 66 j0q . Поскольку никакое использование входных данных процесса q в вычислении C не является причинно-следственным предшественником события записив p, все события C, предшествующие этому событию записи, происходят в томже самом порядке и для вычисления, начинающегося с 0 .
В образовавшемсявычислении p записывает такой же результат J, как и в вычислении C, но теперьэтот результат ошибочный.Теорема 6.12. Каждый волновой алгоритм можно использовать длявычисления точной нижней грани.Д о к а з а т е л ь с т в о. Пусть задан алгоритм A. Придадим каждому процессу q дополнительную переменную vq , которая инициализирована элементом jq .По ходу волны значения этой переменной претерпевают следующие изменения.Всякий раз, когда процесс q отправляет сообщение, предусмотренное алгорит6.1.5.
Вычисление функций точной нижней гранимом A, текущее значение vq включается в сообщение. Всякий раз, когда процессq получает сообщение, предусмотренное алгоритмом A и содержащее значение v,В этом параграфе будет показано, что волновые алгоритмы — это в точностипеременная vq полагается равной vq u v. Когда в процессе p происходит событиеалгоритмы, необходимые для вычисления функции, значение которой существенdecide, текущее значение vp записывается в outp .но зависит от входных данных каждого процесса.
Представителем такого классаПокажем, что алгоритм выдает правильное значение. Правильным называетсяфункций могут служить функции точной нижней грани по всем входам, еслитакой ответ J, что J = inf{jq : q ∈ P}. Для всякого события a в процессе q обознаэто возможно для частично упорядоченного множества.чим символом v (a) значение vq сразу после осуществления события a. ПосколькуПусть (X, 6) — частично упорядоченное множество.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
