Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 62
Текст из файла (страница 62)
Следовательно, как только нашалгоритм завершит свое выполнение, s будет равно сумме всех входных данных.Вычисление суммы при помощи остовного дерева. Некоторые волновыеалгоритмы при выполнении процессом p события решения d p открывают ему до-232Гл.
6.Волновые алгоритмы и алгоритмы обходаступ к остовному дереву с корнем p, по которому сообщения направляются к p.На самом деле в каждом вычислении всякого волнового алгоритма содержитсятакое остовное дерево; однако может случиться так, что процесс q отправляетнесколько сообщений и не располагает сведениями о том, какие исходящие изнего ребра принадлежат одному из таких деревьев. Если процесс осведомлен отом, какое исходящее ребро ведет к родительской вершине в подобном дереве,то само дерево можно использовать для вычисления сумм. Каждый процесс отправляет своей родительской вершине в этом дереве сумму всех входных данных,вычисленных в своем поддереве.Этот принцип можно применять для древесного алгоритма, алгоритма эха, фазового алгоритма на кликах.
Древесный алгоритм можно легко адаптировать так,чтобы в сообщение, отправляемое из p в q, включать сумму всех входных данныхв дереве Tpq . Процесс, принимающий решение, вычисляет окончательный результат, суммируя значения, содержащиеся в двух сообщениях, следующих навстречудруг другу по одному и тому же ребру. Фазовый алгоритм на кликах адаптируется за счет того, что в каждое сообщение из q в p включаются входные данныеq. Процесс p суммирует все полученные значения и свои собственные входныеданные, и в результате будет получен правильный ответ, как только p приметрешение.
В алгоритме эха входные данные суммируются при помощи остовногодерева T, которое явно строится по ходу вычисления (см. упражнение 6.15).Вычисление сумм с использованием отличительных признаков. Предположим, что каждый процесс наделен индивидуальным отличительным признаком.Сумма всех входных данных может быть вычислена так. Каждый процесс помечает свои входные данные своим индивидуальным ярлыком, образуя пару (p, j p).Отметим, что никакие два процесса не могут сформировать одну и ту же пару. Алгоритм гарантирует, что всякий раз, когда процесс принимает решение,он осведомлен о всех входных данных отдельных процессов; множество S == { (p, jp) : p ∈ P} является объединением множеств Sp = { (p, jp) } по всем p,и его можно вычислить по ходу одной волны.
На основе этого множества желаемый результат вычисляется с помощью локальных операций.uHHHHuuHHH H HHHuuHHHuHuuB@B @u@uPPPB P B Pu B PPu@@ BBu@uРис. 6.20. Две сети диаметра два и степени триДля такого решения задачи требуется, чтобы индивидуальные отличительныепризнаки всех процессов стали доступны, а это весьма значительно увеличивает6.5. Прочие вопросы233битовую сложность.
Каждое сообщение волнового алгоритма включает подмножество S, для представления которого требуется до Nw битов, если считать, чтоодин ярлык и входные данные одного процесса требуют в совокупности w битов(см. упражнение 6.16).6.5.3. Альтернативные определения сложности по времениСложность по времени для распределенных алгоритмов можно определятьнесколькими разными способами.
В этой книге всякий раз, когда речь заходито сложности по времени, мы обращаемся к определению 6.31, но здесь мы обсудим и другие возможные определения 1) .Определения, основанные на более ограниченных допущениях о времени. Время, расходуемое распределенными вычислениями, можно оценивать,воспользовавшись более ограниченными допущениями о хронометрировании событий в системе.Определение 6.37. Для заданного алгоритма его равномерная сложностьпо времени — это наибольшее время вычисления алгоритма при следующих допущениях.O1.
Процесс может выполнять любой конечный набор действий за нулевоевремя.O2. Время между отправлением и приемом сообщения в точности равно одной единице времени.Сравнивая это определение с определением 6.31, заметим, что допущение O1точно такое же, как и T1. Поскольку длительность передачи сообщений согласно допущению T2 не превосходит длительности передачи согласно допущениюO2, может возникнуть мысль о том, что равномерная сложность по времени неменьше обычной сложности по времени.
Аргументацию можно было бы основать на том, что каждое вычисление проводится в соответствии с допущением T2не медленнее, нежели в соответствии с допущением O2, и, следовательно, вычисление с максимальной задержкой также будет выполняться при допущенииT2 не хуже, чем при допущении O2. Изъян в этом рассуждении состоит в том,что изменчивость длительности передачи сообщения, допускаемая T2, приводитк более разнообразному классу вычислений, в который, быть может, придетсявключить вычисления с неудовлетворительным поведением во времени. Напомним, что T2 — это не ограничение, налагаемое на выполнения алгоритмов, которые нужно хронометрировать, а определение единицы времени.
В таком случаедопущение O2 в действительности сужает множество выполнений, ограничиваяего теми, в которых все сообщения передаются с одной и той же задержкой. Сутьдела видна ниже на примере алгоритма эха.На самом деле верно обратное: для всякого алгоритма его обычная сложностьпо времени не меньше, чем равномерная сложность по времени того же алгорит1) В дальнейшем в этой главе, говоря о сложности алгоритмов по времени согласно определению 6.31, мы будем называть эту сложность обычной сложностью по времени.
— Прим. перев.234Гл. 6.Волновые алгоритмы и алгоритмы обходама. Каждое вычисление, согласованное с допущениями O1 и O2, соответствуеттакже и допущениям T1 и T2, и при этом оно укладывается точно в такой жеотрезок времени. Следовательно, наихудший возможный случай поведения алгоритма согласно допущениям O1 и O2 охвачен определением 6.31 и дает намнижнюю оценку сложности по времени.Теорема 6.38.
Равномерная сложность по времени алгоритма эха равна O(D). Обычная сложность по времени алгоритма эха равна Θ (N) дажедля сетей диаметра 1.Д о к а з а т е л ь с т в о. Чтобы проанализировать равномерную сложностьпо времени, воспользуемся допущениями O1 и O2. Всякий процесс, отстоящий наd переходов от инициатора, получает первое сообщение tok спустя в точностиd единиц времени после начала вычисления, и он будет расположен на уровне dв построенном дереве T. (Это можно показать, применив индукцию по d.) ПустьDT обозначает высоту дерева T. Тогда DT 6 D и процесс, расположенный науровне d в дереве T, отправит сообщение tok в свою родительскую вершину непозднее, чем через (2DT + 1) − d единиц времени после начала вычисления.
(Этоможно показать при помощи обратной индукции по d.) Значит, инициатор приметрешение не позднее, чем через 2DT + 1 единиц времени после начала вычисления.Чтобы оценить обычную сложность по времени, обратимся к допущениям T1и T2. Всякий процесс, отстоящий на d переходов от инициатора, получает первоесообщение tok спустя не более d единиц времени после начала вычисления (этоможно обосновать, воспользовавшись индукцией по d).
Предположим, что построение остовного дерева завершилось спустя F единиц времени после началавычисления, и тогда F 6 D. Высота остовного дерева D T совсем не обязательнобудет ограничена его диаметром (это показано ниже на примере одного вычисления), но, поскольку есть всего N процессов, высота дерева не будет превосходитьN − 1. Процесс, расположенный на уровне d в дереве T, отправляет сообщениеtok в свою родительскую вершину не позднее, чем через (F + 1) + (D T − d) единицвремени после начала вычисления (это можно показать при помощи обратной индукции по d). Отсюда следует, что инициатор примет решение спустя не более(F + 1) + DT единиц времени после начала вычисления, а это есть величина O(N).Чтобы убедиться в том, что Ω (N) является нижней оценкой сложности по времени, построим вычисление на клике, для которого требуется N единиц времени.Выделим в клике остовное дерево высоты N − 1 (представляющее собой не чтоиное, как линейную цепочку вершин).
Условимся считать, что все сообщения tok,передаваемые по ребрам дерева от родительских вершин к их последователям,поступают к адресату 1/N единиц времени спустя после отправления, а сообщения tok по стягивающим ребрам поступают спустя одну единицу времени. Такиезадержки не противоречат допущению T2, и в этом вычислении все дерево строится за одну единицу времени, но имеет высоту N − 1. А теперь представим себе,что все сообщения, передаваемые процессами по ребрам дерева в их родительские вершины, также претерпевают задержку на одну единицу времени. В такомслучае решение будет принято спустя в точности N единиц времени после началавычисления.6.5. Прочие вопросы235Читатель может задаться вопросом: которое из этих двух определений предпочтительнее, когда речь заходит о сложности распределенных алгоритмов повремени.
Равномерная сложность по времени обладает тем недостатком, чтонекоторые вычисления выпадают из рассмотрения, хотя они и возможны длязаданного алгоритма. Среди неучтенных вычислений могут оказаться такие, длякоторых требуется особенно много времени. А вот допущения, представленныев определении 6.31, не упускают ни одного вычисления: ведь в этом определении всего лишь вводится единица измерения времени для каждого вычисления.Недостатком обычной сложности по времени является то, что окончательныйитог подводится теми вычислениями (наподобие приведенного в доказательстветеоремы 6.38), которые, хотя и будучи осуществимыми в принципе, выглядяткрайне неправдоподобно. И в самом деле, в этом вычислении одно-единственноесообщение передается по одному каналу медленнее, чем N − 1 сообщений попоследовательной цепочке каналов.В качестве компромисса между этими двумя определениями можно рассмотреть -сложность по времени, которая определяется допущением о том, чтозадержка передачи каждого сообщения располагается между и 1 ( — это константа, не превосходящая 1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
