Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 62
Текст из файла (страница 62)
Такиезадержки не противоречат допущению Т2, и в этом вычислении все дерево строится за одну единицу времени, но имеет высоту N — I. А теперь представим себе,что все сообщения, передаваемые процессами по ребрам дерева в их родительские вершины, также претерпевают задержку на одну единицу времени. В такомслучае решение будет принято спустя в точности N единиц времени после началавычисления.□6.5. Прочие вопросы235Читатель может задаться вопросом: которое из этих двух определений предпочтительнее, когда речь заходит о сложности распределенных алгоритмов повремени. Равномерная сложность по времени обладает тем недостатком, чтонекоторые вычисления выпадают из рассмотрения, хотя они и возможны длязаданного алгоритма.
Среди неучтенных вычислений могут оказаться такие, длякоторых требуется особенно много времени. А вот допущения, представленныев определении 6.31, не упускают ни одного вычисления: ведь в этом определении всего лишь вводится единица измерения времени для каждого вычисления.Недостатком обычной сложности по времени является то, что окончательныйитог подводится теми вычислениями (наподобие приведенного в доказательстветеоремы 6.38), которые, хотя и будучи осуществимыми в принципе, выглядяткрайне неправдоподобно.
И в самом деле, в этом вычислении одно-единственноесообщение передается по одному каналу медленнее, чем N — 1 сообщений попоследовательной цепочке каналов.В качестве компромисса между этими двумя определениями можно рассмотреть а - с л о ж н о с т ь п о в р е м е н и , которая определяется допущением о том, чтозадержка передачи каждого сообщения располагается между а и 1 (а — это константа, не превосходящая 1 ). К сожалению, такому компромиссному вариантуприсущи недостатки обоих альтернативных определений. Читателю предоставляется возможность самостоятельно убедиться в том, что для алгоритма эха егоa -сложность по времени равна 0(min(jV, D / а)).Наиболее точная мера сложности по времени получается при введении распределения вероятностей времени задержки сообщения, позволяющего определять математическое ожидание времени вычисления заданного алгоритма.
У этого подхода есть два главных недостатка. Во-первых, анализ алгоритмов становится зависящим от свойств системы, поскольку для каждой распределеннойсистемы имеется свое распределение вероятностей времени задержки сообщения. А во-вторых, в подавляющем большинстве случаев сам анализ оказался быслишком сложной задачей.Определения на основе цепочек сообщений. Вместо того чтобы обращаться к идеализированным допущениям, мы можем определить время, расходуемое распределенным вычислением, при помощи структурных свойств самоговычисления.
Рассмотрим вычисление С.Определение 6.39. Ц е п о ч к о й с о о б щ е н и й в С называется такая последовательность сообщений т\, m 2 , . . . , т ь что для каждого i, 0 ^ г < k , приемсообщения т,- предшествует в причинно-следственной связи отправлению сообщения т,-+ 1.Ц е п н о й с л о ж н о с т ь ю п о в р е м е н и распределенного алгоритма называется длинасамой протяженной цепочки сообщений в произвольном вычислении указанногоалгоритма.В этом определении, как и в определении 6.31, для оценки сложности алгоритма по времени рассматриваются все возможные выполнения алгоритма, ноиспользуются при этом разные меры сложности вычислений.
Рассмотрим слу236Гл. 6.Волновые алгоритмы и алгоритмы обходачай такого вычисления (описанного в доказательстве теоремы 6.38), когда одноединственное сообщение передается медленнее, чем цепочка из k сообщений.Обычная сложность по времени такого фрагмента вычисления равна 1, тогдакак цепная сложность того же самого фрагмента вычисления равна k. В системах, где гарантирована верхняя оценка длительности задержки сообщения (какэто подразумевается в определении обычной сложности по времени), обычнаясложность по времени служит хорошей мерой.
А в системах, где большинствосообщений поступают по истечении некоторой «средней» задержки и лишь малаяих доля задерживается на гораздо больший срок, предпочтение отдается цепнойсложности по времени.6.6. Упражнения к главе 66. 6.1Упражнение 6.1. Приведите пример PIF-алгоритма для систем с синхронным обменом сообщениями, который не позволяет проводить вычисление точныхнижних граней (так, как это указано в теоремах 6.7 и 6.12).
Этот пример можетбыть пригоден только для топологии специального вида.Упражнение 6.2. Элемент b частично упорядоченного множества (X , Д) называется нижней точкой, если для всякого с € X выполняется неравенство b Д с.Доказательство теоремы 6.11 опирается на тот факт, что в частично упорядоченном множестве (X , Д) отсутствует нижняя точка. В каком месте доказательстваиспользуется этот факт?Можно ли привести пример алгоритма, который не является волновым и приэтом вычисляет точную нижнюю грань в частично упорядоченном множестве,обладающим нижней точкой?Упражнение 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) дляпроизвольной сети за 0(N) единиц времени с использованием 2|£| сообщений.Можно ли построить алгоритм, который вычислял бы схему разметки за время0(D)? (Здесь D обозначает диаметр сети.)6.6. Упражнения к главе 6237Упражнение 6.7. Покажите, что взаимосвязь, которая проявляется в лемме 6.19, сохраняется и в том случае, когда сообщения могут утеряны в каналеpq, но не сохраняется, когда сообщения могут дублироваться. Какой из этаповдоказательства утратит силу, если сообщения могут дублироваться?Упражнение 6.8.
Примените конструкцию из теоремы 6.12 к фазовому алгоритму для построения алгоритма вычисления максимума на множестве целочисленных входных данных всех процессов.Какова битовая сложность, а также сложность по времени и числу обменов сообщениями построенного алгоритма?Упражнение 6.9. Предположим, что есть желание использовать волновойалгоритм в сети, в которой возможно дублирование сообщений.1) Какие изменения нужно внести в алгоритм эха?2) Какие изменения нужно внести в алгоритм Финна?6.6.3Упражнение 6.10. Полным двудольным графом называется граф G = (V , Е),в котором V = V\ U 1/2, причем V\ П V 2 = 0 и Е = V\ х V 2 .Приведите пример алгоритма 2х-обхода для полного двудольного графа.Упражнение 6.11.
В работе [67] было показано, что обходи широковещательное распространение сообщений возможны в гиперкубе и при отсутствиивосприятия направления. При каком значении / такой алгоритм будет алгоритмом/-обхода?6.6.4Упражнение 6.12. Приведите пример вычисления алгоритма Тарри, в котором построенное дерево Т не является D FS-деревом.Упражнение 6.13. Напишите алгоритм, реализующий поиск в глубину с разметкой интервалов (см. § 4.4.2) для произвольной связной сети.Может ли этот алгоритм провести поиск за О(М) единиц времени? Может лиэтот алгоритм провести поиск с использованием O(N) обменов сообщениями?Упражнение 6.14. Предположим, что алгоритм поиска в глубину с учетомсведений о соседях используется в системе, в которой каждый процесс не толькорасполагает сведениями об отличительных признаках соседей, но имеет такжедоступ к множеству отличительных признаков всех процессов системы (Р).
Покажите, что в этом случае можно обойтись сообщениями, состоящими из N битовкаждое.6.6.5Упражнение 6.15. Адаптируйте алгоритм эха (алгоритм 6.4) для вычислениясуммы входных данных всех процессов.Упражнение 6.16. Допустим, что все процессы сетей, изображенных на рис. 6.20,обладают индивидуальными отличительными признаками и на вход каждого процесса подано целое число. Промоделируйте на обеих сетях вычисление фазовогоалгоритма, вычисляющего множество S = {(р, j p) : р € Р}, а также сумму всехвходных данных.238Гл.
6.Волновые алгоритмы и алгоритмы обходаУпражнение 6.17. Какова цепная сложность по времени фазового алгоритма на кликах (алгоритм 6.7)?ГЛАВА7АЛГОРИТМЫ ИЗБРАНИЯ ЛИДЕРАВ этой главе будет обсуждаться задача о выборах, которую называют такжезадачей избрания лидера. Впервые задачу о выборах сформулировал Ле-Ланнв работе [131], и он же предложил первое ее решение (см. §7.2.1). Проблемасостоит в том, чтобы исходя из конфигурации, в которой все процессы пребываютв одном и том же состоянии, достичь такой конфигурации, в которой ровно одинпроцесс будет находиться в состоянии leader, тогда как все остальные процессыбудут пребывать в состоянии lost.Выборы лидера среди процессов должны быть проведены, когда требуетсявыполнить какой-нибудь централизованный алгоритм и при этом нет заранее заданного кандидата, который мог бы выступить инициатором этого алгоритма.
Такое может произойти, например, в том случае, когда процедура инициализациивыполняется в начале работы или после выхода системы из строя. Посколькумножество активных процессов может быть заранее неизвестно, нельзя назначить раз и навсегда один из процессов на роль лидера.Существует великое множество результатов (алгоритмов и более общих теорем), касающихся задачи о выборах. При отборе результатов, включенных в настоящую главу, мы придерживались следующих критериев.1. Синхронные системы, анонимные процессы и отказоустойчивые алгоритмы рассматриваются в других главах. В этой главе всегда подразумевается, чтопроцессы и каналы надежны, система вполне асинхронна и все процессы можноопознать по индивидуальным отличительным признакам.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
