Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 63
Текст из файла (страница 63)
К сожалению, такому компромиссному вариантуприсущи недостатки обоих альтернативных определений. Читателю предоставляется возможность самостоятельно убедиться в том, что для алгоритма эха его-сложность по времени равна O(min(N, D/ )).Наиболее точная мера сложности по времени получается при введении распределения вероятностей времени задержки сообщения, позволяющего определять математическое ожидание времени вычисления заданного алгоритма. У этого подхода есть два главных недостатка. Во-первых, анализ алгоритмов становится зависящим от свойств системы, поскольку для каждой распределеннойсистемы имеется свое распределение вероятностей времени задержки сообщения. А во-вторых, в подавляющем большинстве случаев сам анализ оказался быслишком сложной задачей.Определения на основе цепочек сообщений.
Вместо того чтобы обращаться к идеализированным допущениям, мы можем определить время, расходуемое распределенным вычислением, при помощи структурных свойств самоговычисления. Рассмотрим вычисление C.Определение 6.39. Цепочкой сообщений в C называется такая последовательность сообщений m1 , m2 , . . . , mk , что для каждого i, 0 6 i < k, приемсообщения mi предшествует в причинно-следственной связи отправлению сообщения mi+1 .Цепной сложностью по времени распределенного алгоритма называется длинасамой протяженной цепочки сообщений в произвольном вычислении указанногоалгоритма.В этом определении, как и в определении 6.31, для оценки сложности алгоритма по времени рассматриваются все возможные выполнения алгоритма, ноиспользуются при этом разные меры сложности вычислений.
Рассмотрим слу-236Гл. 6.6.6. Упражнения к главе 6Волновые алгоритмы и алгоритмы обходачай такого вычисления (описанного в доказательстве теоремы 6.38), когда одноединственное сообщение передается медленнее, чем цепочка из k сообщений.Обычная сложность по времени такого фрагмента вычисления равна 1, тогдакак цепная сложность того же самого фрагмента вычисления равна k. В системах, где гарантирована верхняя оценка длительности задержки сообщения (какэто подразумевается в определении обычной сложности по времени), обычнаясложность по времени служит хорошей мерой.
А в системах, где большинствосообщений поступают по истечении некоторой «средней» задержки и лишь малаяих доля задерживается на гораздо больший срок, предпочтение отдается цепнойсложности по времени.6.6. Упражнения к главе 66.6.1Упражнение 6.1. Приведите пример PIF-алгоритма для систем с синхронным обменом сообщениями, который не позволяет проводить вычисление точныхнижних граней (так, как это указано в теоремах 6.7 и 6.12).
Этот пример можетбыть пригоден только для топологии специального вида.Упражнение 6.2. Элемент b частично упорядоченного множества (X, 6) называется нижней точкой, если для всякого c ∈ X выполняется неравенство b 6 c.Доказательство теоремы 6.11 опирается на тот факт, что в частично упорядоченном множестве (X, 6) отсутствует нижняя точка. В каком месте доказательстваиспользуется этот факт?Можно ли привести пример алгоритма, который не является волновым и приэтом вычисляет точную нижнюю грань в частично упорядоченном множестве,обладающим нижней точкой?Упражнение 6.3.
Приведите пример двух отношений частичного порядка намножестве натуральных чисел, для которых в качестве функции точной нижнейграни используется (1) наибольший общий делитель, и (2) наименьшее общеекратное.Приведите пример отношений частичного порядка на семействе подмножествуниверсума U, для которого в качестве функции точной нижней грани используется (1) пересечение множеств, и (2) объединение множеств.Упражнение 6.4.
Докажите теорему о точной нижней грани (теорему 6.13).6.6.2Упражнение 6.5. Покажите, что в каждом вычислении древесного алгоритма (см. алгоритм 6.2) в точности два процесса принимают решение.Упражнение 6.6. Воспользуйтесь алгоритмом эха (алгоритм 6.4) для построения алгоритма, вычисляющего схему разметки префикса (см. § 4.4.3) дляпроизвольной сети за O(N) единиц времени с использованием 2|E| сообщений.Можно ли построить алгоритм, который вычислял бы схему разметки за времяO(D)? (Здесь D обозначает диаметр сети.)237Упражнение 6.7. Покажите, что взаимосвязь, которая проявляется в лемме 6.19, сохраняется и в том случае, когда сообщения могут утеряны в каналеpq, но не сохраняется, когда сообщения могут дублироваться.
Какой из этаповдоказательства утратит силу, если сообщения могут дублироваться?Упражнение 6.8. Примените конструкцию из теоремы 6.12 к фазовому алгоритму для построения алгоритма вычисления максимума на множестве целочисленных входных данных всех процессов.Какова битовая сложность, а также сложность по времени и числу обменов сообщениями построенного алгоритма?Упражнение 6.9.
Предположим, что есть желание использовать волновойалгоритм в сети, в которой возможно дублирование сообщений.1) Какие изменения нужно внести в алгоритм эха?2) Какие изменения нужно внести в алгоритм Финна?6.6.3Упражнение 6.10. Полным двудольным графом называется граф G = (V, E),в котором V = V1 ∪ V2 , причем V1 ∩ V2 = ∅ и E = V1 × V2 .Приведите пример алгоритма 2x-обхода для полного двудольного графа.Упражнение 6.11. В работе [67] было показано, что обход и широковещательное распространение сообщений возможны в гиперкубе и при отсутствиивосприятия направления. При каком значении f такой алгоритм будет алгоритмомf-обхода?6.6.4Упражнение 6.12.
Приведите пример вычисления алгоритма Тарри, в котором построенное дерево T не является DFS-деревом.Упражнение 6.13. Напишите алгоритм, реализующий поиск в глубину с разметкой интервалов (см. § 4.4.2) для произвольной связной сети.Может ли этот алгоритм провести поиск за O(N) единиц времени? Может лиэтот алгоритм провести поиск с использованием O(N) обменов сообщениями?Упражнение 6.14. Предположим, что алгоритм поиска в глубину с учетомсведений о соседях используется в системе, в которой каждый процесс не толькорасполагает сведениями об отличительных признаках соседей, но имеет такжедоступ к множеству отличительных признаков всех процессов системы (P). Покажите, что в этом случае можно обойтись сообщениями, состоящими из N битовкаждое.6.6.5Упражнение 6.15. Адаптируйте алгоритм эха (алгоритм 6.4) для вычислениясуммы входных данных всех процессов.Упражнение 6.16.
Допустим, что все процессы сетей, изображенных на рис. 6.20,обладают индивидуальными отличительными признаками и на вход каждого процесса подано целое число. Промоделируйте на обеих сетях вычисление фазовогоалгоритма, вычисляющего множество S = { (p, jp) : p ∈ P}, а также сумму всехвходных данных.238Гл. 6.Волновые алгоритмы и алгоритмы обходаУпражнение 6.17. Какова цепная сложность по времени фазового алгоритма на кликах (алгоритм 6.7)?ГЛАВА 7АЛГОРИТМЫ ИЗБРАНИЯ ЛИДЕРАВ этой главе будет обсуждаться задача о выборах, которую называют такжезадачей избрания лидера. Впервые задачу о выборах сформулировал Ле-Ланнв работе [131] , и он же предложил первое ее решение (см.
§ 7.2.1). Проблемасостоит в том, чтобы исходя из конфигурации, в которой все процессы пребываютв одном и том же состоянии, достичь такой конфигурации, в которой ровно одинпроцесс будет находиться в состоянии leader, тогда как все остальные процессыбудут пребывать в состоянии lost.Выборы лидера среди процессов должны быть проведены, когда требуетсявыполнить какой-нибудь централизованный алгоритм и при этом нет заранее заданного кандидата, который мог бы выступить инициатором этого алгоритма. Такое может произойти, например, в том случае, когда процедура инициализациивыполняется в начале работы или после выхода системы из строя.
Посколькумножество активных процессов может быть заранее неизвестно, нельзя назначить раз и навсегда один из процессов на роль лидера.Существует великое множество результатов (алгоритмов и более общих теорем), касающихся задачи о выборах. При отборе результатов, включенных в настоящую главу, мы придерживались следующих критериев.1. Синхронные системы, анонимные процессы и отказоустойчивые алгоритмы рассматриваются в других главах. В этой главе всегда подразумевается, чтопроцессы и каналы надежны, система вполне асинхронна и все процессы можноопознать по индивидуальным отличительным признакам.2. Задаче о выборах была отведена роль «тестовой задачи» для сопоставления эффективности различных моделей вычислений.
Поэтому мы затронем некоторые результаты, которые необходимы для проведения такого сравнения, и будем часто возвращаться к этой задаче в последующих главах (см. гл. 9, 12, 11).3. Мы сосредоточим внимание на результатах, касающихся сложности почислу обменов сообщениями; алгоритмы с улучшенной сложностью по времени, а также результаты, устанавливающие взаимосвязь между сложностью повремени и сложностью по числу обменов сообщениями, здесь не обсуждаются.7.1.
ВведениеВ задаче о выборах требуется, начав вычисление из конфигурации, в которойвсе процессы пребывают в одном и том же состоянии, достичь такой конфигурации, в которой ровно один процесс находится в особом состоянии leader, тогдакак все остальные процессы пребывают в состоянии lost. Тот процесс, который240Гл. 7. Алгоритмы избрания лидеранаходится в состоянии leader в конце вычисления, называется лидером, и о немговорится, что он был избран посредством заданного алгоритма.Определение 7.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
