Реферат: Распределенные алгоритмы
Контроллер буферного графа. Можно продемонстрировать, что контроллеры Раздела 5.2 лайфлок-свободны без каких-либо модификаций, если их передвижения в бесконечной последовательности удовлетворяют ряду справедливых предположений. Fl и F2 - сильные предположеня и F3 - слабое предположение.
Fl. Если порождение пакета p предпринимается непрерывно, то каждое бесконечное вычисление, в котором fb (p) свободен в бесконечно большом количестве конфигураций, содержит порождение p.
F2. Если в конфигурации g пакет p должен быть послан от u до w, то каждое бесконечное вычисление, начинающееся в g, в котором nb (p, b) является свободным в бесконечно большом количестве конфигураций, содержит пересылку p.
F3. Если пакет p находится в своем пункте назначения в конфигурации g, то каждое бесконечное вычисление, начинающееся в g, содержит выведение p.
Лемма 5.24 Если справедливые предположения F2 и F3 удовлетворяются в каждом бесконечном вычислении bgc, то каждый буфер свободен бесконечно часто.
Доказательство. Доказывать будем индукцией сверху вниз по классам буферов. Как в доказательстве Теоремы 5.7, пусть R - наибольший буферный класс. Напомним, что в конфигурациях, достижимых под управлением bgc, все пакеты располагаются в подходящих буферах.
Случай r = R: Буфер класса R не имеет исходящих ребер, и, следовательно, пакет из такого буфера достигает пункта назначения. Следовательно, по предположению F3, после каждой конфигурации, в которой такой буфер занят, будет конфигурация, в которой буфер свободен. Отсюда следует, что он пуст в бесконечно большом количестве конфигураций.
Случай r < R: Пусть g - конфигурация, в которой буфер b класса r < R занят пакетом p. Если p достиг своего пункта назначения, то позже будет конфигурация, в которой b будет пустым из F3. Иначе, p должен быть продвинут в буфер nb(p, b) класса r' > r. По индукции, в каждом бесконечном вычислении, начинающемся в g, этот буфер пуст бесконечно часто. Из этого следует (по F2), что p будет передан и, следовательно, будет конфигурация g, после которой b будет пуст.
Теорема 5.25 Если справедливые предположения F1, F2 и F3 удовлетворяются, то в каждом бесконечном вычислении каждый пакет, предлагаемый сети, будет выведен из своего пункта назначения.
Доказательство. По Лемме 5.24 все буферы пусты в бесконечно большом количестве конфигураций. Значит (по Fl) каждый паке, который продолжает предлагаться сети, будет сгенерирован. По F2 он будет продвигаться, пока не достигнет своего пункта назначения. ð
Легко предположить, что механизм недетерминированного выбора в распределенной системе гарантирует, что эти три предположения удовлетворяются. Альтернативно, предположения могут быть введены добавлением к контроллеру механизма, который гарантирует, что, когда буфер становится пустым, более старым пакетам позволяется входить с большими приоритетами.
Неструктурированные решения. Контроллеры Раздела 5.3 нужно модифицировать, чтобы они стали лайфлок-свободными. Это может быть показано моделированием бесконечного вычисления, в котором непрерывный поток пакетов заставляет контроллер запрещать пересылку некоторого пакета. Toueg [TouSOb] представляет такое вычисление (для FC) и представляет модификацию FS (подобную представленной здесь для контроллеров буферных графов), которая является лайфлок-свободной.
Упражнение 5.1 Покажите, что не существует беступикового контроллера, который использует только один буфер на вершину и позволяет каждой вершине посылать пакеты по крайней мере одной другой вершине.
Упражнение 5.2 Покажите, что dest не является беступиковым, если маршрутизация пакетов осуществляется как на Рисунке 5.2.
Упражнение 5.3 (Схема сколько-будет-переходов) Дайте буферный граф и функции fb и nb для контроллера, который использует буфер bu[i] для хранения пакетов, которым нужно сделать еще i переходов по направлению к своим пунктам назначения. Каков буферный класс bu [i] ? Нужно ли хранить счетчик переходов в каждом пакете?
Упражнение 5.4 Закончите доказательство того, что граф BGa (определенный в доказательстве Теоремы 5.13)- в самом деле буферный граф, т.е., для каждого пути P Î P существует гарантированный путь с образом P. Покажите, что, как утверждалось, fb и nb в самом деле описывают путь в BGa.
Проект 5.5 Докажите, что существует беступиковый контроллер, для коммутации пакетов в гиперкубе, который использует всего два буфера на вершину и позволяет маршрутизировать пакеты через минимальные пути. Можно ли получить набор используемых путей посредством алгоритма интервальной маршрутизации (Подраздел 4.4.2)? Можно ли использовать схему линейной интервальной разметки?
Упражнение 5.6 Докажите, что BC и BS - беступиковые контроллеры.
Упражнение 5.7 Докажите, каждое передвижение, позволяемое BC, также позволяется FC.
Часть 2 Фундаментальные алгоритмы
6 Волновые алгоритмы и алгоритмы обхода
При разработке распределенных алгоритмов для различных приложений часто в качестве подзадач возникает несколько общих проблем для сетей процессов. Эти элементарные задачи включают в себя широковещательную рассылку информации - broadcasting (например, посылка начального или заключительного сообщения), достижение глобальной синхронизации между процессами, запуск выполнения некоторого события в каждом процессе, или вычисление функции, входные данные которой распределены между процессами. Эти задачи всегда решаются путем пересылки сообщений согласно некоторой, зависящей от топологии схеме, которая гарантирует участие всех процессов. Эти задачи настолько фундаментальны, что можно дать решения более сложных задач, таких как выбор (Глава 7), обнаружение завершения (Глава 8), или взаимное исключение, в которых связь между процессами осуществляется только через эти схемы передачи сообщений.
Важность схем передачи сообщений, называемых далее волновыми алгоритмами, оправдывает их рассмотрение отдельно от конкретного прикладного алгоритма, в который они могут быть включены. В этой главе формально определяются волновые алгоритмы (Подраздел 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, распределенные алгоритмы обычно допускают большой набор возможных вычислений благодаря недетерминированности как в процессах, так и в подсистеме передачи. Вычисление - это набор событий, частично упорядоченных отношением каузального (причинно-следственного) предшествования p; см. Определение 2.20. Количество событий в вычислении C обозначается через |C|, а подмножество событий, происходящих в процессе p, обозначается через Cp. Считается, что существует особый тип внутренних событий, называемый decide (принять решение); в алгоритмах этой главы такое событие представляется просто утверждением decide. Волновой алгоритм обменивается конечным числом сообщений и затем принимает решение, которое каузально зависит от некоторого события в каждом процессе.
Определение 6.1 Волновой алгоритм - это распределенный алгоритм, который удовлетворяет следующим трем требованиям:
a) Завершение. Каждое вычисление конечно:
" C : |C| < ¥
b) Принятие решения. Каждое вычисление содержит хотя бы одно событие decide:
" C : $ e Î C : e - событие decide.
c) Зависимость. В каждом вычислении каждому событию decide каузально предшествует какое-либо событие в каждом процессе:
" C : " e Î C : ( e - событие decide Þ " q Î P $ f Î Cq : f p e).
Вычисление волнового алгоритма называется волной. Кроме того, в вычислении алгоритма различаются инициаторы, также называемые стартерами, и не-инициаторы, называемые последователями. Процесс является инициатором, если он начинает выполнение своего локального алгоритма самопроизвольно, т.е. при выполнении некоторого условия, внутреннего по отношению к процессу. Не-инициатор включается в алгоритм только когда прибывает сообщение и вызывает выполнение локального алгоритма процесса. Начальное событие инициатора - внутреннее событие или событие посылки сообщения, начальное событие не-инициатора - событие получения сообщения.
Существует множество волновых алгоритмов, так как они могут различаться во многих отношениях. Для обоснования большого количества алгоритмов в этой главе и в качестве помощи в выборе одного из них для конкретной цели здесь приведен список аспектов, которые отличают волновые алгоритмы друг от друга; см. также Таблицу 6.19.
1) Централизация. Алгоритм называется централизованным, если в каждом вычислении должен быть ровно один инициатор, и децентрализованным, если алгоритм может быть запущен произвольным подмножеством процессов. Централизованные алгоритмы также называют алгоритмами одного источника, а децентрализованные - алгоритмами многих источников. Как видно из Таблицы 6.20, централизация существенно влияет на сложность волновых алгоритмов.
2) Топология. Алгоритм может быть разработан для конкретной топологии, такой как кольцо, дерево, клика и т.д.; см. Подраздел 2.4.1 и Раздел B.2.
3) Начальное знание. Алгоритм может предполагать доступность различных типов начального знания в процессах; см. Подраздел 2.4.4. Примеры требуемых заранее знаний:
(a) Идентификация процессов. Каждому процессу изначально известно свое собственное уникальное имя.
(b) Идентификация соседей. Каждому процессу изначально известны имена его соседей.
(c) Чувство направления (sense of direction). См. Раздел B.3.
4) Число решений. Во всех волновых алгоритмах этой главы в каждом процессе происходит не более одного решения. Количество процессов, которые выполняют событие decide, может быть различным; в некоторых алгоритмах решение принимает только один процесс, в других - все процессы. В древовидном алгоритме (Подраздел 6.2.2) решают ровно два процесса.
5) Сложность. Меры сложности, рассматриваемые в этой главе, это количество передаваемых сообщений (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 бита для указания типа сообщения.
Обычно при применении волновых алгоритмов в сообщение могут быть включены дополнительные переменные и другая информация.[AK1] Многие приложения используют одновременное или последовательное распространение нескольких волн; в этом случае в сообщение должна быть включена информация о волне, которой оно принадлежит. Кроме того, процесс может хранить дополнительные переменные для управления волной, или волнами, в которых он в настоящее время активен.
Важный подкласс волновых алгоритмов составляют централизованные волновые алгоритмы, обладающие двумя дополнительными качествами: инициатор является единственным процессом, который принимает решение; и все события совершенно упорядочены каузальными отношениями. Такие волновые алгоритмы называются алгоритмами обхода и рассматриваются в Разделе 6.3.
6.1.2 Элементарные результаты о волновых алгоритмах
В этом подразделе доказываются некоторые леммы, которые помогают лучше понять структуру волновых вычислений, и приведены две тривиальные нижние границы сложности сообщений волновых алгоритмов.
Структурные свойства волн. Во-первых, каждому событию в вычислении предшествует событие в инициаторе.
Лемма 6.2 Для любого события e Î C существует инициатор p и событие f в Cp такое, что f p e.
Доказательство. Выберем в качестве f минимальный элемент в предыстории e, т.е. такой, что f p e и не существует f¢ p f. Такое f существует, поскольку предыстория каждого события конечна. Остается показать, что процесс p, в котором находится f, является инициатором. Для начала, заметим, что f - это первое событие p, иначе более раннее событие p предшествовало бы f. Первое событие не-инициатора - это событие получения сообщения, которому предшествовало бы соответствующее событие посылки сообщения, что противоречит минимальности f. Следовательно, p является инициатором.
Страницы: 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, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62
