Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 53
Текст из файла (страница 53)
Однако некоторые более общиетеоремы в этих случаях будет неверны (см. пример 6.1).6.1.1. Определение волновых алгоритмовКак было отмечено в гл. 2, в распределенном алгоритме допускается большоемногообразие возможных вычислений вследствие недетерминизма как в самихпроцессах, так и в подсистеме коммуникаций. Всякое вычисление — это множество событий, частично упорядоченных по отношению причинно-следственногопредшествования согласно определению 2.20. Количество событий в вычисленииC обозначим |C|, а подмножество событий, произошедших в процессе p, обозначим Cp .
Предполагается, что существуют внутренние события специального типа,которые называются событиями решения; в алгоритмах настоящей главы такиесобытия просто представлены оператором decide. В волновом алгоритме проводится обмен конечным числом сообщений, а затем принимается решение, котороеимеет причинно-следственную зависимость от какого-либо события в каждом изпроцессов.Определение 6.1. Волновым алгоритмом называется распределенный алгоритм, который удовлетворяет следующим трем требованиям.1.
Завершение. Каждое вычисление конечно:∀C : |C| < ∞.2. Решение. Каждое вычисление содержит хотя бы одно событие решения:∀C : ∃e ∈ C : e является событием решения decide.3. Зависимость. В любом вычислении всякому событию решения предшествует в причинно-следственном отношении хотя бы одно событие в каждом из195процессов:∀C : ∀e ∈ C : (e — событие решения decide ⇒ ∀q ∈ C : ∃f ∈ Cq : f e).Вычисление волнового алгоритма называется волной. Еще одно обозначение:при выполнении алгоритма проводится различие между инициаторами, которые также называются стартовыми процессам, и неинициаторами, которыетакже называются последователями. Процесс является инициатором, если онзапускает выполнение своего локального алгоритма самопроизвольно, т. е. алгоритм запускается по некоторому условию внутри процесса.
Неинициатор становится вовлеченным в распределенный алгоритм, только когда по ходу вычисленияпоступает сообщение, которое запускает выполнение алгоритма процесса. Первое событие инициатора — это внутреннее событие или отправление сообщения,а первое событие неинициатора — это событие приема сообщения.Своим разнообразием волновые алгоритмы обязаны тому, что они могут отличаться во многих отношениях. Чтобы сделать осмысленным изучение в этойглаве большого числа алгоритмов и чтобы облегчить выбор того или иного алгоритма для конкретных целей, мы приводим здесь список тех аспектов, в которыхволновые алгоритмы отличаются друг от друга (см. также таблицу 6.18).1. Централизация.
Алгоритм называется централизованным, если у каждого вычисления есть в точности один инициализатор, и децентрализованным,если алгоритм может быть запущен спонтанно некоторым произвольным подмножеством процессов. Централизованные алгоритмы также называются алгоритмами с одним источником, а децентрализованные — алгоритмами со многими источниками. Как видно из таблицы 6.19, централизация оказывает заметное влияние на сложность волновых алгоритмов.2. Топология. Алгоритм может быть спроектирован в расчете на специальную топологию, наподобие кольца, дерева, клики и т.п.
(см. § 2.4.1 и § Б.4.2).3. Первоначальные сведения. Алгоритм может исходить из предположенияо том, что процессам изначально доступны сведения того или иного рода (см.§ 2.4.4). Примерами таких сведений могут служитьа) самоидентификация: каждый процесс изначально знает свое собственное уникальное имя;б) идентификация соседей: каждый процесс изначально знает имена своихсоседей;в) восприятие направления: см. § Б.4.3.4. Число решений. Во всех волновых алгоритмах, рассматриваемых в этойглаве, в каждом процессе принимается не более одного решения.
Число процессов, в которых выполняется событие решения, может варьироваться; в однихалгоритмах решение принимает только один процесс, в других это могут делатьвсе процессы. В древесном алгоритме (см. § 6.2.2) в точности два процесса принимают решение.5. Сложность. В настоящей главе мерами сложности служат количествообменов сообщениями, число битов информации, отправленных при обмене сообщениями, и время, затрачиваемое одним вычислением (согласно определениюиз § 6.6.4).
См. также § 2.4.5.196Гл. 6.Волновые алгоритмы и алгоритмы обходаВ этой главе в описании каждого волнового алгоритма указываются используемые переменные и, при необходимости, та информация, которая содержитсяв сообщениях. В большинстве таких алгоритмов отправляются «пустые» сообщения, не содержащие какой-то реальной информации; такие сообщения передаютпричинно-следственную обусловленность, а не информацию. В алгоритмах 6.8,6.10, 6.11, и 6.17 сообщения используются для передачи содержательной информации. В алгоритмах 6.14 и 6.15/6.16 задействованы сообщения различныхтипов; здесь требуется, чтобы каждое сообщение содержало один или два битадля различения типов сообщений.Когда применяется волновой алгоритм, то, вообще говоря, в нем используется большее число переменных, а в сообщения может быть включена и другаяинформация.
Во многих приложениях происходит совместное или последовательное распространение нескольких волн; в таких случаях в сообщение должна бытьвключена информация о той волне, к которой это сообщение относится. Крометого, во всяком процессе могут быть задействованы дополнительные переменныедля управления волной или волнами, в которых этот процесс принимает активноеучастие.Важный подкласс волновых алгоритмов представляют централизованные волновые алгоритмы, наделенные следующими двумя дополнительными свойствами:единственным процессом, принимающим решения, является инициатор, и все события линейно упорядочены по отношению причинно-следственной зависимости.Волновые алгоритмы такого рода называются алгоритмами обхода и рассматриваются в § 6.6.3.6.1.2.
Основные свойства волновых алгоритмовВ этом параграфе мы докажем несколько лемм, которые позволят лучше понять устройство волнового вычисления, а также установим две простые нижниеоценки сложности волновых алгоритмов по числу обменов сообщениями.Структурные свойства волн. Во-первых, каждому событию в вычислениипредшествует некоторое событие в инициаторе.Лемма 6.2. Для каждого события e ∈ C существуют такой инициатор p и такое событие f в Cp , что f e.Д о к а з а т е л ь с т в о. Выберем в качестве f минимальный элемент в истории события e, т. е. такой элемент, для которого f e и нет события f 0 ≺ f.Указанный элемент f существует, поскольку история каждого события конечна.
Остается показать, что процесс p, в котором происходит событие f, являетсяинициатором. Прежде всего отметим, что f — это первое событие процесса p, ибоиначе более ранние события p предшествовали бы f. Первое событие неинициатора — это событие приема, которому должно предшествовать соответствующеесобытие отправления, что противоречит минимальности f. Значит, p — инициатор.6.1. Определение и применение волновых алгоритмов197Волна с одним инициатором определяет остовное дерево сети, если для каждого неинициатора выделить канал, по которому он получает первое сообщение.Лемма 6.3. Пусть C — волна с одним инициатором p.
Для каждогонеинициатора q обозначим символом fatherq того соседа процесса q, откоторого q получил первое сообщение. Тогда граф T = (P, ET), где ET == {qr : q 6= p ∧ r = fatherq }, является остовным деревом, направленнымк p.Д о к а з а т е л ь с т в о. Поскольку число вершин в T превосходит число дугна единицу, достаточно показать, что T не содержит циклов. И это действительнотак, поскольку для eq , первого события в q, наличие дуги qr ∈ ET влечет er eq ,а отношение является частичным порядком.В качестве события f, упомянутого в третьем пункте определения 6.1, можновыбрать событие отправления сообщения для всех процессов q за исключениемтого процесса, в котором происходит событие decide.Лемма 6.4. Пусть C — волна и dp ∈ C — событие решения в процессе p.Тогда∀q 6= p : ∃f ∈ Cq : (f dp ∧ f — событие отправления сообщения).Д о к а з а т е л ь с т в о. Так как C — волна, существует событие f ∈ Cq , которое является причинно-следственным предшественником события dp .
Выберемв качестве f последнее событие в Cq , предшествующее dp . Чтобы показать, чтоf — это событие отправления сообщения, заметим, что из определения причинноследственной зависимости (определение 2.20) вытекает существование такой последовательности (причинно-следственной цепочки)f = e 0 , e 1 , . . . , e k = dp ,что для каждого i < k события ei и ei+1 являются либо последовательнымисобытиями в одном и том же процессе, либо парой соответствующих событийотправления-приема сообщения. Поскольку f — последнее событие в процессе q,предшествующее событию dp , событие e1 происходит в процессе, отличном от q.Значит, f — событие отправления сообщения.Нижние оценки сложности волн. Из леммы 6.4 немедленно вытекает нижняя оценка N − 1 для числа сообщений, которыми обмениваются процессы припрохождении волны.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
