Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 52
Текст из файла (страница 52)
Достаточно взглянуть на пример, изображенный на рис. 5.6. Предположим, что в узле u берет начало бесконечный поток пакетов, которые нужноотправить в узел v, и всякий раз, когда буфер в узле w освобождается, очередному пакету из узла u разрешается совершить продвижение. В узле s имеется пакет,адресованный узлу t, и этот пакет не заблокирован, потому что всякий раз, когда190Гл. 5.
Неблокируемая коммутация пакетовбуфер в узле w освобождается, существует такое возможное продолжение вычисления, по ходу которого этому самому пакету будет разрешено продвинутьсяв узел w и затем достичь узла t. Хотя такое продолжение вычисления являетсявозможным, оно не является неизбежным, и пакет может навеки остаться в узле.Ситуацию такого рода принято называть активным тупиком.5.4. Прочие вопросы191ющем пустой буфер nb(p, b) в бесконечном множестве конфигураций, происходитпродвижение пакета p.F3. Если пакет p в конфигурации достиг своего узла-адресата, то в каждомбесконечном вычислении, начинающемся конфигурацией , происходит поглощение пакета p.Лемма 5.24.
Если соблюдаются допущения справедливости F2 и F3,то в любом бесконечном вычислении под управлением контроллера bgcкаждый буфер оказывается свободным бесконечно часто.? ?- tswД о к а з а т е л ь с т в о. Доказательство проводится с использованием нисходящей индукции по классам буферов. Как и в доказательстве теоремы 5.7,обозначим символом R наибольший класс буферов.
Напоминаем, что в конфигурациях, которые можно достичь под управлением контроллера bgc, все пакетыпомещаются в подходящие буферы.Случай r = R. Буфер класса R не имеет исходящих дуг в буферном графе,и поэтому пакет, помещенный в такой буфер, уже достиг своего узла-адресата.Следовательно, согласно допущению F3 после каждой конфигурации, в которойэтот буфер занят, рано или поздно будет достигнута конфигурация, в которойэтот буфер пуст. Это означает, что буфер свободен бесконечно часто.Случай r < R. Рассмотрим конфигурацию , в которой буфер b класса r << R занят пакетом p. Если p уже достиг предназначенного узла, то согласнодопущению F3 позднее будет достигнута конфигурация, в которой буфер b освободится. В противном случае пакет p должен быть переправлен в буфер nb(p, b),который имеет буферный класс r0 > r.
По индуктивному предположению в каждом бесконечном вычислениии, которое начинается конфигурацией , этот буферосвобождается бесконечно часто. В силу допущения F2 отсюда следует, что пакетp будет продвигаться бесконечно часто, и, значит, после конфигурации будетдостигнута конфигурация, в которой буфер b будет пустым.u?vРис. 5.6. Пример активного тупикаВозможности тех контроллеров, которые мы изучили в этой главе, можно такрасширить, чтобы они могли предотвращать также и активные тупики.Определение 5.23.
Пусть задана некоторая сеть, контроллер con и конфигурация . Тогда пакет p считается оставленным без внимания, если существует бесконечная последовательность действий, применимых к конфигурации, при выполнении которых пакет p не будет поглощен.Конфигурация называется активной тупиковой конфтигурацией, если в этойконфигурации есть хоть один пакет, оставленный без внимания.Говорят, что контроллер избегает активных тупиков, из конфигурации, в которой нет никаких пакетов, нельзя достичь ни одной активной тупиковой конфигурации.Далее в этом параграфе мы докажем, что контроллеры с буферным графомизбегают активных тупиков.
В самом конце мы вкратце обсудим, как поступитьс неструктурированными решениями.Контроллер с буферным графом. Можно показать, что все контроллеры,описанные в § 5.5.2, избегают активных тупиков без всякой модификации их действий, если на бесконечных вычислениях соблюдаются допущения строгой справедливости F1 и F2, а также допущение слабой справедливости F3.F1. Если непрерывно предпринимаются попытки сформировать пакет p, токаждое бесконечное вычисление, в котором буфер fb(p) оказывается свободнымв бесконечном множестве конфигураций, обязательно содержит пакет p.F2. Если в конфигурации пакет p должен быть отправлен из узла u в узелw, то в каждом бесконечном вычислении, начинающемся конфигурацией и име-Теорема 5.25.
Если соблюдаются допущения справедливости F1, F2 и F3,то в любом бесконечном вычислении под управлением контроллера bgcкаждый пакет, который может возникнуть в сети, будет поглощен всоответствующем узле-адресате.Д о к а з а т е л ь с т в о. По лемме 5.24 все буферы оказываются пустымив бесконечно многих конфигурациях. Согласно допущению F1 это означает, чтокаждый пакет, который пытаются ввести в сеть бесконечно часто, рано или поздно будет сформирован. Согласно допущению F2 он будет продвигаться, до техпор пока не достигнет своего узла-адресата. Согласно допущению F3 он будетпоглощен в узле-адресате.Можно предполагать, что механизм недетерминированного выбора в распределенных системах просто обеспечивает выполнимость трех упомянутых допущений. В противном случае соблюдение этих допущений может быть навязанопутем встраивания в контроллер специальной процедуры, которая в случае освобождения буфера будет отдавать приоритет тем пакетам, которые имеют болеепродолжительный возраст.192Гл.
5. Неблокируемая коммутация пакетовНеструктурированные решения. Чтобы контроллеры, описанные в § 5.5.3,могли избегать активных тупиков, их нужно модифицировать. В этом можно убедиться, построив бесконечное вычисление, в котором непрерывный поток пакетовможет привести к тому, что контроллер запретит продвижение какого-то другогопакета.
Туэг в работе [195] привел пример такого вычисления для контроллераFC и представил такую модификацию контроллера FS (аналогичную рассмотренной нами модификации контроллеров с буферным графом), которая позволяетизбегать активных тупиков.5.5. Упражнения к главе 55.5.1Упражнение 5.1. Покажите, что не существует беступиковых контроллеров,которые используют только по одному буферу в каждом узле и разрешают каждому узлу отправлять пакет в какой-то другой узел.5.5.2Упражнение 5.2. Покажите, что контроллер dest не будет являться беступиковым, если маршрутизация пакетов проводится так, как показано на рис. 5.2.Упражнение 5.3.
(Схема предстоящих шагов) Опишите устройство буферного графа, а также функции fb и nb для контроллера, использующего буферbu [i] для хранения пакетов, которым предстоит совершить i продвижений, чтобыдостичь своих узлов-адресатов.Как определить буферный класс для bu [i] ? Должен ли каждый пакет вести учетсделанных шагов?Упражнение 5.4. Завершите доказательство утверждения о том, что графBGa (определенный в доказательстве теоремы 5.13) действительно является буферным графом, т.
е. для каждого пути P ∈ P существует гарантированный путь,образом которого является P. Покажите, что функции fb и nb действительно, какутверждается в доказательстве теоремы, описывают путь в буферном графе BG a .Курсовая работа 5.5. Докажите, что существует такой беступиковый контроллер, который осуществляет коммутацию пакетов в гиперкубе, используя приэтом только два буфера в каждом узле и разрешая проводить маршрутизациюпакетов по путям с наименьшим числом звеньев.Можно ли получить совокупность используемых путей при помощи интервального алгоритма маршрутизации (см. § 4.4.2)? Можно ли воспользоваться для этогосхемами разметки линейными интервалами?5.5.3Упражнение 5.6. Докажите, что контроллеры BC и BS являются беступиковыми.Упражнение 5.7.
Докажите, что всякое действие, разрешенное контроллером BC, будет также разрешено контроллером FC.ГЛАВА 6ВОЛНОВЫЕ АЛГОРИТМЫ И АЛГОРИТМЫ ОБХОДАПри проектировании распределенных алгоритмов для разных приложений некоторые общие проблемы, относящиеся к сетевым процессам, часто становятсяпромежуточными задачами. К таким элементарным задачам относятся широковещательное распространение информация (например, сообщения о начале илизавершении вычисления), установление глобальной синхронизации между процессами, запуск выполнения некоторого действия в каждом процессе, вычисление функции при условии, что каждый из процессов содержит только часть входных данных. Эти задачи всегда решаются путем обмена сообщениями согласнонекоторой предписанной схеме, которая зависит от топологии сети и позволяетзадействовать все процессы.
И действительно, как будет видно читателю в последующих главах, эти проблемы являются настолько основополагающими, чторешения более сложных задач, таких как избрание лидера (гл. 7), определение завершения вычисления (гл. 8), обеспечение взаимно исключенного доступа, можнопредставить так, чтобы взаимосвязь между процессами проводилась только в соответствие с указанными схемами обмена сообщениями.Схемы обмена сообщениями, которые в дальнейшем будем называть волновыми алгоритмами, настолько важны, что мы исследуем их отдельно, независимо откакого-либо конкретного прикладного алгоритма, в который встроены эти схемы.В этой главе приводится формальное определение волновых алгоритмов (§ 6.1.1)и обосновываются некоторые общие результаты, относящиеся к этому понятию(§ 6.1.2). Мы дадим строгую формулировку замечания о том, что одни и те жеалгоритмы можно использовать во всех перечисленных выше основополагающих задачах, к числу которых относится широковещательное распространениесообщений, синхронизация и вычисление глобальных функций (§§ 6.1.3 - 6.1.5).В § 6.6.2 приведены некоторые наиболее употребительные волновые алгоритмы.В § 6.6.3 рассматриваются алгоритмы обхода, которые являются не чем иным,как волновыми алгоритмами, обладающими тем дополнительным свойством, чтовсе события в каждом вычисления алгоритма линейно упорядочены по отношению причинно-следственной зависимости.
В § 6.6.4 приведен ряд алгоритмов дляраспределенного поиска в глубину.Рассматривать волновые алгоритмы в виде отдельной темы, несмотря на точто они обычно применяются в качестве процедур, входящих в состав болеесложных алгоритмов, имеет смысл по двум причинам. Во-первых, введение этогопонятия облегчает последующее изучение более сложных алгоритмов, посколькусвойства процедур, используемых в этих алгоритмах, будут уже усвоены. Вовторых, некоторые проблемы распределенных вычислений могут быть решены194Гл. 6.6.1. Определение и применение волновых алгоритмовВолновые алгоритмы и алгоритмы обходапри помощи конструкций общего вида, которые дают требуемый алгоритм решения, стоит лишь выбрать в качестве их параметра нужный волновой алгоритм.Одну и ту же конструкцию можно затем применять для получения алгоритмовпри различных топологиях сетей или при различных допущениях, касающихсяпервоначальных сведений о процессах.6.1.
Определение и применение волновых алгоритмовДалее в этой главе мы будем полагать, если только не будет оговорено противное, что сеть имеет фиксированную топологию (никаких изменений топологии непроисходит), является неориентированной (по каждому каналу сообщения могутпередаваться в обоих направлениях) и связной (между любыми двумя процессами пролегает путь). Множество всех процессов обозначим P, а множество всехканалов обозначим E. Как и в предшествующих главах, мы будем считать, чтов системе используется асинхронный обмен сообщениями и отсутствуют понятияглобального времени и вещественных часов. Все алгоритмы, приведенные в настоящей главе, можно использовать и при наличии синхронного обмена сообщениями (возможно, с некоторыми видоизменениями во избежание блокировки) илис глобальными часами, если таковые доступны.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
