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

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

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

Мы дадим строгую формулировку замечания о том, что одни и те жеалгоритмы можно использовать во всех перечисленных выше основополагаю­щих задачах, к числу которых относится широковещательное распространениесообщений, синхронизация и вычисление глобальных функций (§§6.1.3 - 6.1.5).В §6.6.2 приведены некоторые наиболее употребительные волновые алгоритмы.В §6.6.3 рассматриваются алгоритмы обхода, которые являются не чем иным,как волновыми алгоритмами, обладающими тем дополнительным свойством, чтовсе события в каждом вычисления алгоритма линейно упорядочены по отноше­нию причинно-следственной зависимости. В §6.6.4 приведен ряд алгоритмов дляраспределенного поиска в глубину.Рассматривать волновые алгоритмы в виде отдельной темы, несмотря на точто они обычно применяются в качестве процедур, входящих в состав болеесложных алгоритмов, имеет смысл по двум причинам.

Во-первых, введение этогопонятия облегчает последующее изучение более сложных алгоритмов, посколькусвойства процедур, используемых в этих алгоритмах, будут уже усвоены. Вовторых, некоторые проблемы распределенных вычислений могут быть решены194Гл. 6.Волновые алгоритмы и алгоритмы обходапри помощи конструкций общего вида, которые дают требуемый алгоритм реше­ния, стоит лишь выбрать в качестве их параметра нужный волновой алгоритм.Одну и ту же конструкцию можно затем применять для получения алгоритмовпри различных топологиях сетей или при различных допущениях, касающихсяпервоначальных сведений о процессах.6.1. Определение и применение волновых алгоритмовДалее в этой главе мы будем полагать, если только не будет оговорено против­ное, что сеть имеет фиксированную топологию (никаких изменений топологии непроисходит), является неориентированной (по каждому каналу сообщения могутпередаваться в обоих направлениях) и связной (между любыми двумя процесса­ми пролегает путь).

Множество всех процессов обозначим Р, а множество всехканалов обозначим Е. Как и в предшествующих главах, мы будем считать, чтов системе используется асинхронный обмен сообщениями и отсутствуют понятияглобального времени и вещественных часов. Все алгоритмы, приведенные в на­стоящей главе, можно использовать и при наличии синхронного обмена сообще­ниями (возможно, с некоторыми видоизменениями во избежание блокировки) илис глобальными часами, если таковые доступны.

Однако некоторые более общиетеоремы в этих случаях будет неверны (см. пример 6.1).6.1.1. Определение волновых алгоритмовКак было отмечено в гл. 2, в распределенном алгоритме допускается большоемногообразие возможных вычислений вследствие недетерминизма как в самихпроцессах, так и в подсистеме коммуникаций. Всякое вычисление — это множе­ство событий, частично упорядоченных по отношению Д причинно-следственногопредшествования согласно определению 2.20.

Количество событий в вычисленииС обозначим |С|, а подмножество событий, произошедших в процессе р, обозна­чим Ср. Предполагается, что существуют внутренние события специального типа,которые называются событиями решения ; в алгоритмах настоящей главы такиесобытия просто представлены оператором decide. В волновом алгоритме прово­дится обмен конечным числом сообщений, а затем принимается решение, котороеимеет причинно-следственную зависимость от какого-либо события в каждом изпроцессов.Определение 6.1. Волновым алгоритмом называется распределенный ал­горитм, который удовлетворяет следующим трем требованиям.1.

Завершение. Каждое вычисление конечно:VC : \С\ < оо.2. Решение. Каждое вычисление содержит хотя бы одно событие решения:VC : Зе е С : е является событием решения decide.3. Зависимость. В любом вычислении всякому событию решения предше­ствует в причинно-следственном отношении хотя бы одно событие в каждом из6.1. Определение и применение волновых алгоритмов195процессов:VC : Ve € С : (е — событие решения decide =>• dq е С : 3/ е Cq : / ■<е).Вычисление волнового алгоритма называется волной.

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

Чтобы сделать осмысленным изучение в этойглаве большого числа алгоритмов и чтобы облегчить выбор того или иного алго­ритма для конкретных целей, мы приводим здесь список тех аспектов, в которыхволновые алгоритмы отличаются друг от друга (см. также таблицу 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. Для каждого события е е С существуют такой инициа­тор р и такое событие / в Ср, что / ■<е.Д о к а з а т е л ь с т в о .

Выберем в качестве / минимальный элемент в ис­тории события с, т. е. такой элемент, для которого / ■< е и нет события /' -< /.Указанный элемент / существует, поскольку история каждого события конеч­на. Остается показать, что процесс р, в котором происходит событие /, являетсяинициатором. Прежде всего отметим, что / — это первое событие процесса р, ибоиначе более ранние события р предшествовали бы /. Первое событие неинициатора — это событие приема, которому должно предшествовать соответствующеесобытие отправления, что противоречит минимальности /. Значит, р — инициа­тор.□6.1.

Определение и применение волновых алгоритмов197Волна с одним инициатором определяет остовное дерево сети, если для каж­дого неинициатора выделить канал, по которому он получает первое сообщение.Лемма 6.3. Пусть С — волна с одним инициатором р. Для каждогонеинициатора q обозначим символом fatherq того соседа процесса q, откоторого q получил первое сообщение.

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

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