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

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

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

Влияние централизации на сложность по числу сообщенийОказывается, общего метода для вычисления сумм при помощи волновогоалгоритма не существует, но в отдельных случаях вычисление суммы возмож­но. Это те случаи, когда алгоритм является алгоритмом обхода, когда процессынаделены отличительными признаками, или когда алгоритм порождает остовноедерево, которое может быть использовано.Невозможность общего построения. Нельзя предложить общую конструк­цию для вычисления сумм на основе произвольного волнового алгоритма, по­добную той, которая была использована в теореме 6 . 1 2 для вычисления точныхнижних граней. И вот почему.

Есть волновой алгоритм, а именно фазовый алго­ритм (с параметром D = 2), для определенного класса сетей, включающего всенеориентированные безымянные сети диаметра два. Но нет алгоритма, способно­го вычислять сумму всех входных данных, который делал бы это корретно на всехнеориентированных безымянных сетях диаметра два. К этому классу сетей отно­сятся две сети, изображенные на рис. 6.20. Предположим, что на вход каждогопроцесса поступила 1. Тогда искомый результат равен 6 для левой сети и 8 дляправой сети.

Применяя метод, предложенный в гл. 9, можно показать, что всякийалгоритм будет выдавать одинаковый результат на каждой из этих двух сетей, и,значит, он не является одновременно корректным для обеих сетей. Детальнуюразработку этой аргументации оставляем читателю в качестве упражнения 9.7.Вычисление суммы с помощью алгоритмов обхода. Если А является ал­горитмом обхода, то сумму всех входных данных можно вычислить так. Пустьпроцесс р обладает переменной jp, первоначальное значение которой — это вход­ные данные процесса р. Наделим маркер дополнительным полем s. Всякий раз,когда процесс р передает маркер, он выполняет операторs '■= s + jp ; jp := 0 .И тогда можно показать, что каждый раз, когда маркер покидает процесс р, будетвыполняться соотношение jp = 0 , a s будет иметь значение, равное сумме входныхданных для всех ранее пройденных процессов.

Следовательно, как только нашалгоритм завершит свое выполнение, s будет равно сумме всех входных данных.Вычисление суммы при помощи остовного дерева. Некоторые волновыеалгоритмы при выполнении процессом р события решения dp открывают ему до­232Гл. 6.Волновые алгоритмы и алгоритмы обходаступ к остовному дереву с корнем р, по которому сообщения направляются к р.На самом деле в каждом вычислении всякого волнового алгоритма содержитсятакое остовное дерево; однако может случиться так, что процесс q отправляетнесколько сообщений и не располагает сведениями о том, какие исходящие изнего ребра принадлежат одному из таких деревьев.

Если процесс осведомлен отом, какое исходящее ребро ведет к родительской вершине в подобном дереве,то само дерево можно использовать для вычисления сумм. Каждый процесс от­правляет своей родительской вершине в этом дереве сумму всех входных данных,вычисленных в своем поддереве.Этот принцип можно применять для древесного алгоритма, алгоритма эха, фа­зового алгоритма на кликах. Древесный алгоритм можно легко адаптировать так,чтобы в сообщение, отправляемое из р в q, включать сумму всех входных данныхв дереве Tpq. Процесс, принимающий решение, вычисляет окончательный резуль­тат, суммируя значения, содержащиеся в двух сообщениях, следующих навстречудруг другу по одному и тому же ребру. Фазовый алгоритм на кликах адаптиру­ется за счет того, что в каждое сообщение из q в р включаются входные данныеq.

Процесс р суммирует все полученные значения и свои собственные входныеданные, и в результате будет получен правильный ответ, как только р приметрешение. В алгоритме эха входные данные суммируются при помощи остовногодерева Т, которое явно строится по ходу вычисления (см. упражнение 6.15).Вычисление сумм с использованием отличительных признаков. Предпо­ложим, что каждый процесс наделен индивидуальным отличительным признаком.Сумма всех входных данных может быть вычислена так. Каждый процесс поме­чает свои входные данные своим индивидуальным ярлыком, образуя пару (р, j p).Отметим, что никакие два процесса не могут сформировать одну и ту же па­ру. Алгоритм гарантирует, что всякий раз, когда процесс принимает решение,он осведомлен о всех входных данных отдельных процессов; множество S == {{р, jp) : р е Р} является объединением множеств Sp = {(/?, jp)} по всем р,и его можно вычислить по ходу одной волны. На основе этого множества жела­емый результат вычисляется с помощью локальных операций.Рис.

6.20.Д ве сети диаметра два и степени триДля такого решения задачи требуется, чтобы индивидуальные отличительныепризнаки всех процессов стали доступны, а это весьма значительно увеличивает6.5. Прочие вопросы233битовую сложность. Каждое сообщение волнового алгоритма включает подмно­жество S, для представления которого требуется до Nw битов, если считать, чтоодин ярлык и входные данные одного процесса требуют в совокупности w битов(см. упражнение 6.16).6.5.3.

Альтернативные определения сложности по времениСложность по времени для распределенных алгоритмов можно определятьнесколькими разными способами. В этой книге всякий раз, когда речь заходито сложности по времени, мы обращаемся к определению 6.31, но здесь мы об­судим и другие возможные определенияОпределения, основанные на более ограниченных допущениях о вре­мени. Время, расходуемое распределенными вычислениями, можно оценивать,воспользовавшись более ограниченными допущениями о хронометрировании со­бытий в системе.Определение 6.37. Для заданного алгоритма его равномерная сложностьпо времени — это наибольшее время вычисления алгоритма при следующих до­пущениях.01. Процесс может выполнять любой конечный набор действий за нулевоевремя.02.

Время между отправлением и приемом сообщения в точности равно од­ной единице времени.Сравнивая это определение с определением 6.31, заметим, что допущение 01точно такое же, как и Т1. Поскольку длительность передачи сообщений соглас­но допущению Т2 не превосходит длительности передачи согласно допущению0 2 , может возникнуть мысль о том, что равномерная сложность по времени неменьше обычной сложности по времени. Аргументацию можно было бы осно­вать на том, что каждое вычисление проводится в соответствии с допущением Т2не медленнее, нежели в соответствии с допущением 0 2 , и, следовательно, вы­числение с максимальной задержкой также будет выполняться при допущенииТ2 не хуже, чем при допущении 02.

Изъян в этом рассуждении состоит в том,что изменчивость длительности передачи сообщения, допускаемая Т2, приводитк более разнообразному классу вычислений, в который, быть может, придетсявключить вычисления с неудовлетворительным поведением во времени. Напом­ним, что Т2 — это не ограничение, налагаемое на выполнения алгоритмов, кото­рые нужно хронометрировать, а определение единицы времени.

В таком случаедопущение 0 2 в действительности сужает множество выполнений, ограничиваяего теми, в которых все сообщения передаются с одной и той же задержкой. Сутьдела видна ниже на примере алгоритма эха.На самом деле верно обратное: для всякого алгоритма его обычная сложностьпо времени не меньше, чем равномерная сложность по времени того же алгорит­ме дальнейшем в этой главе, говоря о сложности алгоритмов по времени согласно определе­нию 6.31, мы будем называть эту сложность обычной сложностью по времени. — Прим, перев.234Гл.

6.Волновые алгоритмы и алгоритмы обходама. Каждое вычисление, согласованное с допущениями 01 и 02, соответствуеттакже и допущениям Т1 и Т2, и при этом оно укладывается точно в такой жеотрезок времени. Следовательно, наихудший возможный случай поведения ал­горитма согласно допущениям 01 и 0 2 охвачен определением 6.31 и дает намнижнюю оценку сложности по времени.Теорема 6.38. Равномерная сложность по времени алгоритма эха рав­на 0(D).

Обычная сложность по времени алгоритма эха равна Q(N) дажедля сетей диаметра 1 .Д о к а з а т е л ь с т в о . Чтобы проанализировать равномерную сложностьпо времени, воспользуемся допущениями 0 1 и 02. Всякий процесс, отстоящий наd переходов от инициатора, получает первое сообщение tok спустя в точностиd единиц времени после начала вычисления, и он будет расположен на уровне dв построенном дереве Т. (Это можно показать, применив индукцию по d.) ПустьDT обозначает высоту дерева Т.

Тогда Dp С /) и процесс, расположенный науровне d в дереве Т, отправит сообщение tok в свою родительскую вершину непозднее, чем через (2Dp + 1) —d единиц времени после начала вычисления. (Этоможно показать при помощи обратной индукции по d.) Значит, инициатор приметрешение не позднее, чем через 2Dp+ 1 единиц времени после начала вычисления.Чтобы оценить обычную сложность по времени, обратимся к допущениям Т 1и Т2. Всякий процесс, отстоящий на d переходов от инициатора, получает первоесообщение tok спустя не более d единиц времени после начала вычисления (этоможно обосновать, воспользовавшись индукцией по d).

Предположим, что по­строение остовного дерева завершилось спустя F единиц времени после началавычисления, и тогда F ^ D. Высота остовного дерева D j совсем не обязательнобудет ограничена его диаметром (это показано ниже на примере одного вычисле­ния), но, поскольку есть всего N процессов, высота дерева не будет превосходитьyV— 1. Процесс, расположенный на уровне d в дереве Т, отправляет сообщениеtok в свою родительскую вершину не позднее, чем через (F+l) + (Dr —d) единицвремени после начала вычисления (это можно показать при помощи обратной ин­дукции по d).

Отсюда следует, что инициатор примет решение спустя не более(F+ 1) + D j единиц времени после начала вычисления, а это есть величина 0(N).Чтобы убедиться в том, что D(N) является нижней оценкой сложности по вре­мени, построим вычисление на клике, для которого требуется N единиц времени.Выделим в клике остовное дерево высоты N — 1 (представляющее собой не чтоиное, как линейную цепочку вершин). Условимся считать, что все сообщения tok,передаваемые по ребрам дерева от родительских вершин к их последователям,поступают к адресату 1/N единиц времени спустя после отправления, а сообще­ния tok по стягивающим ребрам поступают спустя одну единицу времени.

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

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