МЕНЮ


Фестивали и конкурсы
Семинары
Издания
О МОДНТ
Приглашения
Поздравляем

НАУЧНЫЕ РАБОТЫ


  • Инновационный менеджмент
  • Инвестиции
  • ИГП
  • Земельное право
  • Журналистика
  • Жилищное право
  • Радиоэлектроника
  • Психология
  • Программирование и комп-ры
  • Предпринимательство
  • Право
  • Политология
  • Полиграфия
  • Педагогика
  • Оккультизм и уфология
  • Начертательная геометрия
  • Бухучет управленчучет
  • Биология
  • Бизнес-план
  • Безопасность жизнедеятельности
  • Банковское дело
  • АХД экпред финансы предприятий
  • Аудит
  • Ветеринария
  • Валютные отношения
  • Бухгалтерский учет и аудит
  • Ботаника и сельское хозяйство
  • Биржевое дело
  • Банковское дело
  • Астрономия
  • Архитектура
  • Арбитражный процесс
  • Безопасность жизнедеятельности
  • Административное право
  • Авиация и космонавтика
  • Кулинария
  • Наука и техника
  • Криминология
  • Криминалистика
  • Косметология
  • Коммуникации и связь
  • Кибернетика
  • Исторические личности
  • Информатика
  • Инвестиции
  • по Зоология
  • Журналистика
  • Карта сайта
  • Распределенные алгоритмы

    оправдывает их рассмотрение отдельно от конкретного прикладного алгоритма,

    в который они могут быть включены. В этой главе формально определяются

    волновые алгоритмы (Подраздел 6.1.1) и доказываются некоторые общие

    результаты о них (Подраздел 6.1.2). Замечание о том, что те же самые

    алгоритмы могут использоваться для всех основных задач, изложенных выше,

    т.е. широковещание, синхронизация и вычисление глобальных функций, будет

    формализовано (Подразделы 6.1.3-5). В Разделе 6.2 представлены некоторые

    широко используемые волновые алгоритмы. В Разделе 6.3 рассматриваются

    алгоритмы обхода; это волновые алгоритмы, в которых все события вычисления

    алгоритма совершенно упорядочены каузальным отношением. В Разделе 6.4

    представлены несколько алгоритмов для распределенного поиска в глубину.

    Несмотря на то, что волновые алгоритмы обычно используются как подзадачи в

    более сложных алгоритмах, их полезно рассматривать отдельно. Во-первых,

    введение новых понятий облегчает последующее рассмотрение более сложных

    алгоритмов, т.к. свойства их подзадач уже изучены. Во-вторых, определенные

    задачи в распределенных вычислениях могут быть решены с помощью

    универсальных конструкций, в качестве параметров которых могут

    использоваться конкретные волновые алгоритмы. Тот же метод может

    использоваться для получения алгоритмов для различных сетевых топологий или

    для различных предположений о начальном знании процессов. Эта глава

    основана на [Tel91b, Раздел 4.2], где понятие волновых алгоритмов изучается

    под названием общие алгоритмы.

    6.1 Определение и использование волновых алгоритмов

    В пределах этой главы считается, если не указано обратное, что сетевая

    топология фиксирована (не происходит топологических перемен), не

    ориентирована (каждый канал передает сообщения в обоих направлениях) и

    связна (существует путь между любыми двумя процессами). Множество всех

    процессов обозначено через P, а множество каналов - через E. Как и в

    предыдущих главах, предполагается, что система использует асинхронную

    передачу сообщений и не существует понятия глобального или реального

    времени. Алгоритмы из этой главы также могут быть использованы в случае

    синхронной передачи сообщений (возможно с некоторыми изменениями во

    избежание тупиков) или с часами глобального времени, если они доступны.

    Однако некоторые более общие теоремы в этих случаях неверны; см. Упражнение

    6.1.

    6.1.1 Определение волновых алгоритмов

    Как отмечалось в Главе 2, распределенные алгоритмы обычно допускают большой

    набор возможных вычислений благодаря недетерминированности как в процессах,

    так и в подсистеме передачи. Вычисление - это набор событий, частично

    упорядоченных отношением каузального (причинно-следственного)

    предшествования ?; см. Определение 2.20. Количество событий в вычислении C

    обозначается через |C|, а подмножество событий, происходящих в процессе p,

    обозначается через Cp. Считается, что существует особый тип внутренних

    событий, называемый decide (принять решение); в алгоритмах этой главы такое

    событие представляется просто утверждением decide. Волновой алгоритм

    обменивается конечным числом сообщений и затем принимает решение, которое

    каузально зависит от некоторого события в каждом процессе.

    Определение 6.1 Волновой алгоритм - это распределенный алгоритм, который

    удовлетворяет следующим трем требованиям:

    Завершение. Каждое вычисление конечно:

    ? C : |C| < ?

    Принятие решения. Каждое вычисление содержит хотя бы одно событие decide:

    ? C : ? e ? C : e - событие decide.

    Зависимость. В каждом вычислении каждому событию decide каузально

    предшествует какое-либо событие в каждом процессе:

    ? C : ? e ? C : ( e - событие decide ? ? q ? P ? f ? Cq : f ? e).

    Вычисление волнового алгоритма называется волной. Кроме того, в вычислении

    алгоритма различаются инициаторы, также называемые стартерами, и не-

    инициаторы, называемые последователями. Процесс является инициатором, если

    он начинает выполнение своего локального алгоритма самопроизвольно, т.е.

    при выполнении некоторого условия, внутреннего по отношению к процессу. Не-

    инициатор включается в алгоритм только когда прибывает сообщение и вызывает

    выполнение локального алгоритма процесса. Начальное событие инициатора -

    внутреннее событие или событие посылки сообщения, начальное событие не-

    инициатора - событие получения сообщения.

    Существует множество волновых алгоритмов, так как они могут различаться во

    многих отношениях. Для обоснования большого количества алгоритмов в этой

    главе и в качестве помощи в выборе одного из них для конкретной цели здесь

    приведен список аспектов, которые отличают волновые алгоритмы друг от

    друга; см. также Таблицу 6.19.

    Централизация. Алгоритм называется централизованным, если в каждом

    вычислении должен быть ровно один инициатор, и децентрализованным, если

    алгоритм может быть запущен произвольным подмножеством процессов.

    Централизованные алгоритмы также называют алгоритмами одного источника, а

    децентрализованные - алгоритмами многих источников. Как видно из Таблицы

    6.20, централизация существенно влияет на сложность волновых алгоритмов.

    Топология. Алгоритм может быть разработан для конкретной топологии, такой

    как кольцо, дерево, клика и т.д.; см. Подраздел 2.4.1 и Раздел B.2.

    Начальное знание. Алгоритм может предполагать доступность различных типов

    начального знания в процессах; см. Подраздел 2.4.4. Примеры требуемых

    заранее знаний:

    (a) Идентификация процессов. Каждому процессу изначально известно свое

    собственное уникальное имя.

    (b) Идентификация соседей. Каждому процессу изначально известны имена его

    соседей.

    (c) Чувство направления (sense of direction). См. Раздел B.3.

    Число решений. Во всех волновых алгоритмах этой главы в каждом процессе

    происходит не более одного решения. Количество процессов, которые выполняют

    событие decide, может быть различным; в некоторых алгоритмах решение

    принимает только один процесс, в других - все процессы. В древовидном

    алгоритме (Подраздел 6.2.2) решают ровно два процесса.

    Сложность. Меры сложности, рассматриваемые в этой главе, это количество

    передаваемых сообщений (message complexity), количество передаваемых бит

    (bit complexity) и время, необходимое для одного вычисления (определено в

    Разделе 6.4). См. также Подраздел 2.4.5.

    Каждый волновой алгоритм в этой главе будет дан вместе с используемыми

    переменными и, в случае необходимости, с информацией, передаваемой в

    сообщениях. Большинство этих алгоритмов посылают «пустые сообщения», без

    какой-либо реальной информации: сообщения передают причинную связь, а не

    информацию. Алгоритмы 6.9, 6.11, 6.12 и 6.18 используют сообщения для

    передачи нетривиальной информации. Алгоритмы 6.15 и 6.16/6.17 используют

    различные типы сообщений; при этом требуется, чтобы каждое сообщение

    содержало 1-2 бита для указания типа сообщения.

    Обычно при применении волновых алгоритмов в сообщение могут быть включены

    дополнительные переменные и другая информация. Многие приложения используют

    одновременное или последовательное распространение нескольких волн; в этом

    случае в сообщение должна быть включена информация о волне, которой оно

    принадлежит. Кроме того, процесс может хранить дополнительные переменные

    для управления волной, или волнами, в которых он в настоящее время активен.

    Важный подкласс волновых алгоритмов составляют централизованные волновые

    алгоритмы, обладающие двумя дополнительными качествами: инициатор является

    единственным процессом, который принимает решение; и все события совершенно

    упорядочены каузальными отношениями. Такие волновые алгоритмы называются

    алгоритмами обхода и рассматриваются в Разделе 6.3.

    6.1.2 Элементарные результаты о волновых алгоритмах

    В этом подразделе доказываются некоторые леммы, которые помогают лучше

    понять структуру волновых вычислений, и приведены две тривиальные нижние

    границы сложности сообщений волновых алгоритмов.

    Структурные свойства волн. Во-первых, каждому событию в вычислении

    предшествует событие в инициаторе.

    Лемма 6.2 Для любого события e ? C существует инициатор p и событие f в Cp

    такое, что f ? e.

    Доказательство. Выберем в качестве f минимальный элемент в предыстории e,

    т.е. такой, что f ? e и не существует f' ? f. Такое f существует, поскольку

    предыстория каждого события конечна. Остается показать, что процесс p, в

    котором находится f, является инициатором. Для начала, заметим, что f - это

    первое событие p, иначе более раннее событие p предшествовало бы f. Первое

    событие не-инициатора - это событие получения сообщения, которому

    предшествовало бы соответствующее событие посылки сообщения, что

    противоречит минимальности f. Следовательно, p является инициатором.

    Волна с одним инициатором определяет остовное дерево сети, где для каждого

    не-инициатора выбирается канал, через который будет получено первое

    сообщение.

    Лемма 6.3 Пусть C - волна с одним инициатором p; и пусть для каждого не-

    инициатора q fatherq - это сосед q, от которого q получает сообщение в

    своем первом событии. Тогда граф T = (P, ET), где ET = {qr: q ? p & r =

    fatherq } - остовное дерево, направленное к p.

    Доказательство. Т.к. количество вершин T превышает количество ребер на 1,

    достаточно показать, что T не содержит циклов. Это выполняется, т.к. если

    eq - первое событие в q, из того, что qr ? ET следует, что er ? eq, а ? -

    отношение частичного порядка.

    В качестве события f в пункте (3) Определения 6.1 может быть выбрано

    событие посылки сообщения всеми процессами q, кроме того, где происходит

    событие decide.

    Лемма 6.4 Пусть C - волна, а dp ? C - событие decide в процессе p. Тогда

    ? q ? p: ? f ? Cq: ( f ? dp & f - событие send)

    Доказательство. Т.к. C - это волна, существует событие f ?Cq, которое

    каузально предшествует dp; выберем в качестве f последнее событие Cq,

    которое предшествует dp. Чтобы показать, что f - событие send, отметим, что

    из определения каузальности (Определение 2.20) следует, что существует

    последовательность (каузальная цепочка)

    f = e0, e1, ..., ek = dp,

    такая, что для любого i < k, ei и ei+1 - либо последовательные события в

    одном процессе, либо пара соответствующих событий send-receive. Т.к. f -

    последнее событие в q, которое предшествует dp, e1 происходит в процессе,

    отличном от q, следовательно f - событие send.

    [pic]

    Рис.6.1 Включение процесса в неиспользуемый канал.

    Нижние границы сложности волн. Из леммы 6.4 непосредственно следует, что

    нижняя граница количества сообщений, которые передаются в волне, равна N-1.

    Если событие decide происходит в единственном инициаторе волны (что

    выполняется всегда в случае алгоритмов обхода), граница равна N сообщениям,

    а волновые алгоритмы для сетей произвольной топологии используют не менее

    |E| сообщений.

    Теорема 6.5 Пусть C - волна с одним инициатором p, причем событие decide

    dp происходит в p. Тогда в C передается не менее N сообщений.

    Доказательство. По лемме 6.2 каждому событию в C предшествует событие в p,

    и, используя каузальную последовательность, как в доказательстве леммы 6.4,

    нетрудно показать, что в p происходит хотя бы одно событие send. По лемме

    6.4 событие send также происходит во всех других процессах, откуда

    количество посылаемых сообщений составляет не меньше N.

    Теорема 6.6 Пусть A - волновой алгоритм для сетей произвольной топологии

    без начального знания об идентификации соседей. Тогда A передает не менее

    |E| сообщений в каждом вычислении.

    Доказательство. Допустим, A содержит вычисление C, в котором передается

    менее |E| сообщений; тогда существует канал xy, по которому в C не

    передаются сообщения; см. Рис.6.1. Рассмотрим сеть G', полученную путем

    включения одного узла z в канал между x и y. Т.к. узлы не имеют знания о

    соседях, начальное состояние x и y в G' совпадает с их начальным состоянием

    в G. Это верно и для всех остальных узлов G. Следовательно, все события C

    могут быть применены в том же порядке, начиная с исходной конфигурации G',

    но теперь событию decide не предшествует событие в z.

    В Главе 7 будет доказана улучшенная нижняя граница количества сообщений

    децентрализованных волновых алгоритмов для колец и сетей произвольной

    топологии без знания о соседях; см. Заключение 7.14 и 7.16.

    6.1.3 Распространение информации с обратной связью

    В этом подразделе будет продемонстрировано применение волновых алгоритмов

    для случая, когда некоторая информация должна быть передана всем процессам

    и определенные процессы должны быть оповещены о завершении передачи. Эта

    задача распространения информации с обратной связью (PIF - propagation of

    information with feedback) формулируется следующим образом [Seg83].

    Формируется подмножество процессов из тех, кому известно сообщение M (одно

    и то же для всех процессов), которое должно быть распространено, т.е. все

    процессы должны принять M. Определенные процессы должны быть оповещены о

    завершении передачи; т.е. должно быть выполнено специальное событие notify,

    причем оно может быть выполнено только когда все процессы уже получили

    сообщение M. Алгоритм должен использовать конечное количество сообщений.

    Оповещение в PIF-алгоритме можно рассматривать как событие decide.

    Теорема 6.7 Каждый PIF-алгоритм является волновым алгоритмом.

    Доказательство. Пусть P - PIF-алгоритм. Из формулировки задачи каждое

    вычисление P должно быть конечным и в каждом вычислении должно происходить

    событие оповещения (decide). Если в некотором вычислении P происходит

    оповещение dp, которому не предшествует никакое событие в процессе q, тогда

    из Теоремы 2.21 и Аксиомы 2.23 следует, что существует выполнение P, в

    котором оповещение происходит до того, как q принимает какое-либо

    сообщение, что противоречит требованиям.

    Мы должны иметь в виду, что теорема 2.21 выполняется только для систем с

    асинхронной передачей сообщений; см. Упражнение 6.1.

    Теорема 6.8 Любой волновой алгоритм может использоваться как PIF-алгоритм.

    Доказательство. Пусть A - волновой алгоритм. Чтобы использовать A как PIF-

    алгоритм, возьмем в качестве процессов, изначально знающих M, стартеры

    (инициаторы) A. Информация M добавляется к каждому сообщению A. Это

    возможно, поскольку по построению стартеры A знают M изначально, а

    последователи не посылают сообщений, пока не получат хотя бы одно

    сообщение, т.е. пока не получат M. Событию decide в волне предшествуют

    события в каждом процессе; следовательно, когда оно происходит, каждый

    процесс знает M, и событие decide можно считать требуемым событием notify в

    PIF-алгоритме.

    Построенный PIF-алгоритм имеет такую же сложность сообщений, как и алгоритм

    A и обладает всеми другими качествами A, описанными в Подразделе 6.1.1,

    кроме битовой сложности. Битовая сложность может быть уменьшена путем

    добавления M только к первому сообщению, пересылаемому через каждый канал.

    Если w - количество бит в M, битовая сложность полученного алгоритма

    превышает битовую сложность A на w*|E|.

    6.1.4 Синхронизация

    В этом разделе будет рассмотрено применение волновых алгоритмов для

    случаев, когда должна быть достигнута глобальная синхронизация процессов.

    Задача синхронизации (SYN) формулируется следующим образом [Fin79]. В

    каждом процессе q должно быть выполнено событие aq, и в некоторых процессах

    должны быть выполнены события bp, причем все события aq должны быть

    выполнены по времени раньше, чем будет выполнено какое-либо событие bp.

    Алгоритм должен использовать конечное количество сообщений.

    В SYN-алгоритмах события bp будут рассматриваться как события decide.

    Теорема 6.9 Каждый SYN-алгоритм является волновым алгоритмом.

    Доказательство. Пусть S - SYN-алгоритм. Из формулировки задачи каждое

    вычисление S должно быть конечным и в каждом вычислении должно происходить

    событие bp (decide). Если в некотором вычислении S происходит событие bp,

    которому каузально не предшествует aq, тогда (по Теореме 2.21 и Аксиоме

    2.23) существует выполнение S, в котором bp происходит ранее aq.

    Теорема 6.10 Любой волновой алгоритм может использоваться как SYN-алгоритм.

    Доказательство. Пусть A - волновой алгоритм. Чтобы преобразовать A в SYN-

    алгоритм, потребуем, чтобы каждый процесс q выполнял aq до того, как q

    пошлет сообщение в A или примет решение в A. Событие bp происходит после

    события decide в p. Из леммы 6.4, каждому событию decide каузально

    предшествует aq для любого q.

    Построенный SYN-алгоритм имеет такую же сложность сообщений, как и A, и

    обладает всеми другими свойствами A, описанными в Подразделе 6.1.1.

    6.1.5 Вычисление функций инфимума

    В этой главе будет продемонстрировано применение волновых алгоритмов для

    вычисления функций, значения которых зависят от входов каждого процесса. В

    качестве представителей таких функций будут рассмотрены алгоритмы,

    вычисляющие инфимум по всем входам, которые должны быть извлечены из

    частично упорядоченного множества.

    Если (X, ?) - частичный порядок, то c называют инфимумом a и b, если

    c ? a, c ? b, и ? d : ( d ? a & d ? b ? d ? c). Допустим, что X таково, что

    инфимум всегда существует; в этом случае инфимум является единственным и

    обозначается как a ? b. Т.к. ? - бинарный оператор, коммутативный (a ? b =

    b ? a) и ассоциативный (т.е. a ? (b ? c) = (a ? b) ? c), операция может

    быть обобщена на конечные множества:

    inf { j1, ..., j k} = j1 ? ... ? j k .

    Задача вычисления инфимума формулируется следующим образом. Каждый процесс

    q содержит вход jq, являющийся элементом частично упорядоченного множества

    X. Потребуем, чтобы определенные процессы вычисляли значение inf {jq : q ?

    P} и чтобы эти процессы знали, когда вычисление завершается. Они записывают

    результат вычисления в переменную out и после этого не могут изменять ее

    значение.

    Событие write, которое заносит значение в out, рассматривается в INF-

    алгоритме как событие decide.

    Теорема 6.11 Каждый INF-алгоритм является волновым алгоритмом.

    Доказательство. Пусть I - INF-алгоритм. Предположим, что существует

    вычисление C алгоритма I с начальной конфигурацией ?, в котором p

    записывает значение J в outp и этому событию write не предшествует никакое

    событие в q. Рассмотрим начальную конфигурацию ?', которая аналогична ? за

    исключением того, что q имеет другой вход jq', выбранный так, что jq'€< J.

    Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36


    Приглашения

    09.12.2013 - 16.12.2013

    Международный конкурс хореографического искусства в рамках Международного фестиваля искусств «РОЖДЕСТВЕНСКАЯ АНДОРРА»

    09.12.2013 - 16.12.2013

    Международный конкурс хорового искусства в АНДОРРЕ «РОЖДЕСТВЕНСКАЯ АНДОРРА»




    Copyright © 2012 г.
    При использовании материалов - ссылка на сайт обязательна.