Пролог 6
1 Введение: распределенные системы 7
1.1 Что такое распределенная система? 7
1.1.1 Мотивация 8
1.1.2 Компьютерные сети 10
1.1.3 Глобальные сети 11
1.1.4 Локальные сети 13
1.1.5 Многопроцессорные компьютеры 16
1.1.6 Взаимодействующие процессы 19
1.2 Архитектура и Языки 22
1.2.1 Архитектура 22
1.2.2 Ссылочная Модель
OSI 24
1.2.3 OSI Модель в локальных
сетях: IEEE Стандарты 26
1.2.4 Поддержка Языка 27
1.3 Распределенные
Алгоритмы 29
1.3.1 Распределенный
против Централизованных Алгоритмов 30
1.3.2 Пример: Связь с
одиночным сообщением 32
1.3.3 Область исследования 37
1.3.4 Иерархическая
структура книги 37
2 Модель 40
2.1 Системы перехода и алгоритмы 41
2.1.1 Системы переходов 42
2.1.2 Системы с асинхронной передачей сообщений 43
2.1.3 Системы с синхронной передачей сообщений 45
2.1.4 Справедливость 47
2.2 Доказательство свойств систем перехода 47
2.2.1 Свойства безопасности 48
2.2.2 Свойства живости 50
2.3 Каузальный порядок событий и логические часы 51
2.3.1 Независимость и зависимость событий 52
2.3.2 Эквивалентность исполнений: вычисления 54
2.3.3 Логические часы 57
2.4 Дополнительные допущения, сложность 60
2.4.2 Свойства каналов 62
2.4.3 Допущения реального времени 64
2.4.4 Знания процессов 64
2.4.5 Сложность распределенных алгоритмов 66
3 Протоколы Связи 66
3.1 Сбалансированный протокол скользящего окна 68
3.1.1 Представление протокола 68
3.1.2 Доказательство правильности протокола 71
3.1.3 Обсуждение протокола 73
3.2 Протокол, основанный на таймере 75
3.2.1 Представление Протокола 78
3.2.2 Доказательство корректности
протокола 81
3.2.3 Обсуждение протокола 85
Упражнения к главе 3 88
Раздел 3.1 88
Раздел 3.2 89
4 Алгоритмы маршрутизации 89
4.1 Адресат-основанная маршрутизация 91
4.2 Проблема кротчайших путей всех пар 95
4.2.1 Алгоритм Флойда-Уошала 95
4.2.2 Алгоритм кротчайшего пути.(Toueg) 98
4.2.3 Обсуждение и Дополнительные Алгоритмы 102
4.3 Алгоритм Netchange 106
4.3.1 Описание алгоритма 107
4.3.2 Корректность алгоритма Netchange 112
4.3.3 Обсуждение алгоритма 113
4.4 Маршрутизация с Компактными Таблицами маршрутизации 114
4.4.1 Схема разметки деревьев 115
4.4.2 Интервальная маршрутизация 118
4.4.3 Префиксная маршрутизация 125
4.5 Иерархическая маршрутизация 127
4.5.1 Уменьшение количества решений маршрутизации 128
Упражнения к Части 4 130
Раздел 4.1 130
Раздел 4.2 131
Раздел 4.3 131
Раздел 4.4 131
Раздел 4.5 132
5 Беступиковая коммутация пакетов 132
5.1 Введение 133
5.2 Структурированные решения 134
5.2.1 Буферные Графы 135
5.2.2 Ориентации G 138
5.3 Неструктурированные решения 141
5.3.1 Контроллеры с прямым и обратным счетом 141
5.3.2 Контроллеры с опережающим и отстающим состоянием 142
5.4 Дальнейшие проблемы 144
5.4.1 Топологические изменения 145
5.4.2 Другие виды тупиков 146
5.4.3 Лайфлок (livelock) 147
Упражнения к Главе 5 149
Раздел 5.1 149
Раздел 5.2 149
Раздел 5.3 149
6 Волновые алгоритмы и алгоритмы обхода 149
6.1 Определение и использование волновых алгоритмов 150
6.1.1 Определение волновых алгоритмов 151
6.1.2 Элементарные результаты о волновых алгоритмах 153
6.1.3 Распространение информации с обратной связью 155
6.1.4 Синхронизация 156
6.1.5 Вычисление функций инфимума 156
6.2 Волновые алгоритмы 158
6.2.1 Кольцевой алгоритм 158
6.2.2 Древовидный алгоритм 159
6.2.3 Эхо-алгоритм 161
6.2.4 Алгоритм опроса 163
6.2.5 Фазовый алгоритм 164
6.2.6 Алгоритм Финна 167
6.3 Алгоритмы обхода 169
6.3.1 Обход клик 170
6.3.2 Обход торов 171
6.3.3 Обход гиперкубов 172
6.3.4 Обход связных сетей 173
6.4 Временная сложность: поиск в глубину 175
6.4.1 Распределенный поиск в глубину 176
6.4.2 Алгоритмы поиска в глубину за линейное время 177
6.4.3 Поиск в глубину со знанием соседей 182
6.5 Остальные вопросы 182
6.5.1 Обзор волновых алгоритмов 182
6.5.2 Вычисление сумм 184
6.5.3 Альтернативные определения временной сложности 186
Упражнения к Главе 6 188
Раздел 6.1 188
Раздел 6.2 189
Раздел 6.3 190
Раздел 6.4 190
Раздел 6.5 190
7 Алгоритмы выбора 190
7.1 Введение 191
7.1.1 Предположения, используемые в этой главе 192
7.1.2 Выбор и волны 193
7.2 Кольцевые сети 196
7.2.1 Алгоритмы ЛеЛанна и Чанга-Робертса 196
7.2.2 Алгоритм Petersen / Dolev-Klawe-Rodeh 200
7.2.3 Вывод нижней границы 203
7.3 Произвольные Сети 207
7.3.1 Вырождение и Быстрый
Алгоритм 208
7.3.2 Алгоритм
Gallager-Humblet-Spira 210
7.3.3 Глобальное Описание
GHS Алгоритма. 212
7.3.4 Детальное описания
GHS алгоритма 215
7.3.5 Обсуждения и
Варианты GHS Алгоритма 219
7.4 Алгоритм
Korach-Kutten-Moran 220
7.4.1 Модульное
Строительство 221
7.4.2 Применения Алгоритма
KKM 225
Упражнения к Главе 7 225
Раздел 7.1 225
Раздел 7.2 226
Раздел 7.3 226
Раздел 7.4 226
8 Обнаружение завершения 227
8.1 Предварительные
замечания 228
8.1.1 Определения 228
8.1.2 Две нижних границы 231
8.1.3 Завершение Процессов 233
8.2.2 Алгоритм
Shavit-Francez 237
8.3 Решения, основанные на
волнах 241
8.3.1 Алгоритм
Dijkstra-Feijen-Van Gasteren 242
8.3.2 Подсчет Основных Сообщений:
Алгоритм Сафра 245
8.3.3 Использование
Подтверждений 249
8.3.4 Обнаружение
завершения с помощью волн 252
8.4 Другие Решения 254
8.4.1 Алгоритм
восстановления кредита 254
8.4.2 Решения,
использующие временные пометки 256
Упражнения к Главе 8 259
Раздел 8.1 259
Раздел 8.2 259
Раздел 8.3 259
Раздел 8.4 260
13 Отказоустойчивость в Асинхронных Системах 260
13.1 Невозможность согласия 260
13.1.1 Обозначения, Определения, Элементарные Результаты 260
13.1.2 Доказательство невозможности 262
13.1.3 Обсуждение 264
13.2 Изначально-мертвые Процессы 265
13.3 Детерминированно Достижимые Случаи 268
13.3.1 Разрешимая Проблема: Переименование 269
13.3.2 Расширение Результатов Невозможности 273
13.4 Вероятностные
Алгоритмы Согласия 275
13.4.1 Аварийно-устойчивые Протоколы Согласия 276
13.4.2 Византийско-устойчивые Протоколы Согласия 280
13.5 Слабое Завершение 285
Упражнения к Главе 13 289
Раздел 13.1 289
Раздел 13.2 289
Раздел 13.3 289
Раздел 13.4 290
Раздел 13.5 291
14 Отказоустойчивость в Синхронных Системах 291
14.1 Синхронные Протоколы Решения 292
14.1.1 Граница Способности восстановления 293
14.1.2 Алгоритм Византийского вещания 295
14.1.3 Полиномиальный Алгоритм Вещания 298
14.2 Протоколы с Установлением Подлинности 303
14.2.1 Протокол Высокой Степени Восстановления 304
14.2.2 Реализация Цифровых Подписей 307
14.2.3 Схема Подписи ЭльГамаля 308
14.2.4 Схема Подписи RSA 310
14.2.5 Схема Подписи Фиата-Шамира 310
14.2.6 Резюме и Обсуждение 313
14.3 Синхронизация Часов 315
14.3.1 Чтение Удаленных Часов 316
14.3.2 Распределенная Синхронизация Часов 318
Пролог
Распределенные
системы и обработка распределенной информации получили значительное внимание в
последние несколько лет, и почти каждый университет предлагает, по крайней
мере, один курс по разработке распределенных алгоритмов. Существует большое
число книг о принципах распределенных систем; см. например Tanenbaum [Tan88]
или Sloman and Kramer [SK87], хотя они концентрируются в основном на
архитектурных аспектах, а не на алгоритмах.
Было замечено, что алгоритмы – это основа любого
применения компьютеров. Поэтому кажется оправданным посвятить эту книгу
полностью распределенным алгоритмам. Эта книга направлена на то, чтобы
представить большую часть теории распределенных алгоритмов, которые развивались
в течение последних 15 лет. Эта книга может быть использована как учебник для
одно- или двух-семестрового курса по распределенным алгоритмам. Преподаватель
одно-семестрового курса может выбирать темы по своему усмотрению.
Эта книга также
обеспечит полезную вспомогательную и ссылочную информацию для профессиональных
инженеров и исследователей, работающих с распределенными системами.
Упражнения.
Каждая глава (за исключением глав 1 и 12) оканчивается списком упражнений и маленьких
проектов. Проекты обычно требуют, чтобы читатель разработал маленькое, но
нетривиальное расширение или практическое решение по материалу главы, и в
большинстве случаев у автора нет решения. Если читатель добьется успеха в
разработке этих маленьких проектов, то мне бы хотелось иметь копию результата.
Список ответов
(иногда частичных) у большинству упражнений доступен для преподавателей. Он
может быть получен у автора или по анонимному ftp.
Исправления
и предложения. Если читатель найдет ошибки и пропуски в этой книге, то
пусть информирует автора (предпочтительно по электронной почте). Вся
конструктивная критика, включая предложения по упражнения, очень
приветствуется.
1 Введение: распределенные системы
Эта глава
представляет причины для изучения распределенных алгоритмов, кратко описывая
типы аппаратных и программных систем, для которых развивались распределенные
алгоритмы. Под распределенной системой мы понимаем все компьютерные системы,
где несколько компьютеров или процессоров кооперируются некоторым образом. Это
определение включает глобальные компьютерные сети, локальные сети,
мультипроцессорные компьютеры, в которых каждый процессор имеет свой
собственный управляющий блок, а также системы со взаимодействующими процессами.
Различные типы
распределенных систем и причины использования распределенных систем обсуждаются
в разделе 1.1. Приводятся некоторые примеры существующих систем. Главная тема
этой книги, однако, не то, как эти системы выглядят, или как они используются,
но как заставить их работать. Более того, как заставить работать распределенные
алгоритмы в этих системах.
Конечно,
целиком структуру и функционирование распределенной системы нельзя полностью
понять изучением только алгоритмов самих по себе. Чтобы понять такую систему
полностью нужно также изучить ее архитектуру и программное обеспечение, то
есть, разбиение цельной функциональности по модулям. Также, есть много важных
вопросов, относящихся к свойствам языков программирования, используемых для
разработки программного обеспечения распределенных систем. Эти вопросы будут
обсуждаться в разделе 1.2.
Однако сейчас
существует много превосходных книг по распределенным системам, касающихся архитектурных
и языковых аспектов. Смотрите Tanenbaum [Tan88], Sloman and Kramer [SK87], Bal
[Bal90], Coulouris [CD88], Goscinski [Gos91]. Как уже говорилось, настоящий
труд делает упор на алгоритмы распределенных систем. Раздел 1.3 объясняет,
почему разработка распределенных алгоритмов отличается от разработки
централизованных алгоритмов, там также делается краткий обзор текущего
состояния дел в исследованиях и дается описание остальной части книги.
1.1 Что такое распределенная система?
В этой главе мы
будем использовать термин «распределенная система», подразумевая взаимосвязанный
набор автономных компьютеров, процессов или процессоров. Компьютеры, процессы
или процессоры упоминаются как узлы распределенной системы. (В последующих
главах мы будем использовать более техническое понятие, см. определение 2.6.)
Будучи определенными как «автономные», узлы должны быть, по крайней мере,
оборудованы своим собственным блоком управления. Таким образом, параллельный компьютер
с одним потоком управления и несколькими потоками данных (SIMD) не подпадает
под определение распределенной системы. Чтобы быть определенными как «взаимосвязанными»,
узлы должны иметь возможность обмениваться информацией.
Так как
процессы могут играть роль узлов системы, определение включает программные
системы, построенные как набор взаимодействующих процессов, даже если они
выполняются на одной аппаратной платформе. В большинстве случаев, однако,
распределенная система будет, по крайней мере, содержать несколько процессоров,
соединенный коммутирующей аппаратурой.
Более
ограничивающие определения распределенных систем могут быть также найдены в
литературе. Tanenbaum [Tan88], например, называет систему распределенной,
только если существуют автономные узлы прозрачные для пользователей системы.
Система распределенная в этом смысле ведет себя как виртуальная самостоятельная
компьютерная система, но реализация этой прозрачности требует разработки
замысловатых алгоритмов распределенного управления.
1.1.1 Мотивация
Распределенные
компьютерные системы могут получить предпочтение среди ряда систем или их использования
бывает просто не избежать, в силу многих причин, некоторые из которых
обсуждаются ниже. Этот список не исчерпывающий. Выбор распределенной системы
может быть мотивирован более чем одним аргументов приведенным ниже. И некоторые
из преимуществ могут быть получены как полезный побочный эффект при выборе
других причин. Характеристики распределенных систем могут также варьироваться,
в зависимости от причины их существования, но об этом мы поговорим более
детально в разделах с 1.1.2 по 1.1.6.
(1) Обмен
информацией. Необходимость обмена данными между различными компьютерами
возросла в шестидесятых, когда большинство основных университетов и компаний
начали пользоваться своими собственными майнфреймами. Взаимодействие между
людьми из различных организаций облегчилось благодаря обмену данными между
компьютерами этих организаций, и это дало рост развитию так называемых глобальных
сетей (WAN). Компьютерная система соединенная в глобальную сеть обычно
снабжалась всем что необходимо пользователю: резервными хранилищами данных,
дисками, многими прикладными программами и принтерами.
Позже компьютеры стали меньше и дешевле, и сегодня одна организация
может иметь множество компьютеров, иногда даже один компьютер на одного
работника (рабочую станцию). В этом случае также требуется чтобы эти компьютеры
были соединены для электронного обмена информацией между персоналом компании.
(2) Разделение
ресурсов. Хотя с приходом более дешевых компьютеров стало возможно снабжать
каждого сотрудника организации личным компьютером, это же нельзя сделать для
периферии (принтеры, резервные хранилища, блоки дисков). В этом меньшем
масштабе каждый компьютер может положиться на специальные серверы, которые
снабжают его компиляторами и другими прикладными программами. Также, памяти
любого компьютера обычно недостаточно, чтобы хранить большой набор прикладных
программ, требуемых для каждого пользователя. Кроме того, компьютеры могут
использовать специальные узлы для служб печати и хранения данных. Сеть, соединяющая
компьютеры в масштабе предприятия называется локальной вычислительной сетью(LAN).
Причины, по которым организация устанавливает сеть небольших компьютеров,
а не майнфреймы – снижение стоимости и расширяемость. Во-первых, меньшие
компьютеры имеют лучше соотношение цена-производительность, чем большие
компьютеры. Типичный майнфрейм может совершать операции в 50 раз быстрее, чем
персональный компьютер, но иметь стоимость в 500 раз большую. Во-вторых, если
мощности системы больше не достаточно, то сеть может быть расширена добавлением
других машин (файловых серверов, принтеров и рабочих станций). Если мощность
монолитной системы больше неудовлетворительна, остается только полная замена.
(3) Большая
надежность благодаря репликации. Распределенные системы имеют потенциал
надежности больший, чем монолитные системы благодаря свойству их частичного
выхода из строя. Это значит, что некоторые узлы системы могут выйти из строя, в
то время как другие по прежнему функционируют и могут взять на себя задачи
испорченных компонентов. Выход из строя монолитного компьютера действует на всю
систему целиком и нет возможности продолжать вычисления в этом случае. По этой
причине распределенные архитектуры представляют интерес при разработке высоко надежных
компьютерных систем.
Высоко надежная система обычно состоит из двух, трех или четырех
репликационных унипроцессоров, которые исполняют прикладную программу и
поддерживаются механизмом голосования, чтобы отфильтровывать результаты машин.
Правильное функционирование распределенной системы при наличии поврежденных
компонент требует довольно сложной алгоритмической поддержки.
(4) Большая
производительность благодаря распараллеливанию. Наличие многих процессоров
в распределенной системе открывает возможность снижения дополнительного времени
для интенсивной работы с помощью разделения работы среди нескольких
процессоров.
Параллельные компьютеры разработаны специально для этой цели, но
пользователи локальных сетей также могут получить пользу от параллелизма,
перекладывая задачи на другие рабочие станции.
(5) Упрощение
разработки благодаря специализации. Разработка компьютерной системы может
быть сложной, особенно если требуется значительная функциональность. Разработка
может быть зачастую упрощена разбитием системы на модули, каждый из которых
отвечает за часть функциональности и коммутируется с другими модулями.
На уровне одной программы модульность достигается определением
абстрактных типов данных и процедур для различных задач. Большая система может
быть определена как набор кооперирующих процессов. В обоих случаях, модули
могут быть исполнены в рамках одного компьютера. Но также возможно иметь
локальную сеть с различными типами компьютеров: один снабжен специальным оборудованием
для вычислений, другой – графическим оборудованием, третий – дисками и т.д.
1.1.2 Компьютерные сети
Под компьютерной сетью мы
понимаем набор компьютеров, соединенных коммуникационными средствами, с помощью
которых компьютеры могут обмениваться информацией. Этот обмен имеет место при
посылке и получении сообщений. Компьютерные сети удовлетворяют нашему
определению распределенных систем. В зависимости от расстояния между
компьютерами и их принадлежностью, компьютерные сети называются либо глобальными,
либо локальными.
Глобальная сеть обычно соединяет
компьютеры, принадлежащие различным организациям (предприятия, университеты и
т.д.). Физическое расстояние между узлами обычно составляет 10 километров и
более. Каждый узел такой сети – это законченная компьютерная система,
включающая всю периферию и значительное количество прикладного программного
обеспечения. Главная задача глобальной сети – это обмен информацией между
пользователями различными узлов.
Локальная сеть обычно соединяет
компьютеры, принадлежащие одной организации. Физическое расстояние между узлами
обычно 10 километров и менее. Узел такой сети – это обычно рабочая станция,
файловый сервер или сервер печати, т.е. относительно маленькая станция,
специализирующаяся на особых функциях внутри организации. Главная задача
локальной сети – это обычный обмен информацией и разделение ресурсов.
Граница между двумя типами сетей
не может быть всегда четко очерчена, и обычно различие не столь важно с
алгоритмической точки зрения, потому что во всех компьютерных сетях встречаются
схожие проблемы. Релевантные отличия, относящиеся к развитию алгоритмов,
следующие:
(1) Параметры
надежности. В глобальных сетях вероятность, что что-то пойдет не так в
течение предачи сообщения никода не может быть игнорирована. Распределенные
алгоритмы для глобальных сетей обычно разрабатываются так, чтобы справляться с
возможными неполадками. Локальные сети более надежные, и алгоритмы для них
могут быть разработаны в предположении абсолютной надежности коммуникаций. В
этом случае, однако, невероятное событие, что что-то произойдет не так может
быть пропущено, что обусловит неправильную работу системы.
(2) Время коммуникации.
Времена передачи сообщений в глобальных сетях на порядки больше, чем времена
передачи в локальных сетях. В глобальных сетях время необходимое для обработки
сообщения почти всегда может быть игнорировано по стравнению со временем передачи
сообщения.
(3) Гомогенность.
Даже хотя в локальных сетях не все узлы обязательно равны, обычно возможно
принять единое программное обеспечение и протоколы для использования в рамках
одной организации. В глобальных сетях используется множество различных
протоколов, которые поднимают проблему преобразования между различными
протоколами и разработки программного обеспечения, которое совместимо с
различными стандартами.
(4) Взаимное доверие.
Внутри одной организации можно доверять всем пользователям, но в глобальной
сети это определенно не так. Глобальная сеть требует развития безопасных
алгоритмов, защищающих узлы от аггресивных пользователей.
Раздел 1.1.3 посвящен краткому
обсуждлению глобальных сетей, локальные сети обсуждаются в разделе 1.1.4.
1.1.3 Глобальные сети
Историческое развитие.
Большая часть первооткрывательской работы в развитии глобальных компьютерных
сетей было проделано в проектах агентства ARPA министерства обороны США. Сеть ARPANET
начала работать в 1969, и соединяла в то время 4 узла. Эта сеть выросла до
нескольких сотен узлов, и другие сети были установлены с использованием
подобной технологии (MILNET, CYRPRESS). ARPANET содержит специальные узлы
(называемые процессорами интерфейса сообщений (IMP)), которые предназначены
только для обработки потока сообщений.
Когда UNIX системы стали широко
использоваться, было признана необходимость информационного обмена между
различными UNIX машинами, для чего была написана программа uucp (Unix-to-Unix
CoPy). С помощью этой программы можно обмениваться файлами по телефонным
каналам и сетям с пользователями UNIX – эта программа дала название
быстрорастущим UUCP сетям. Также другая большая сеть, BITNET, была
разработана в восьмидесятые, так как ARPANET принадлежала министерству обороны
и только несколько организаций могли к ней подключаться.
Сегодня все эти сети соединены
между собой с помощью узлов, которые принадлежат двум сетям (называемые
шлюзами) и позволяющих обмениваться информацией узлам различных сетей. Введение
унифицированного адресного пространства превратило все сети в одну виртуальную
сеть, известную как Internet. Электронный адрес автора (gerard@cs.ruu.nl)
обеспечивает информацию о сети, к которой подключен его департамент.
Алгоритмические проблемы и
проблемы организации. Глобальные сети всегда организованы как сети типа точка-точка.
Это означает, что коммуникация между парой узлов осуществляется при помощи
механизма особенного по отношению к этим двум узлам. Такой механизм может быть
телефонной линией, оптоволокном или спутниковой связью и т.д. Структура
соединений в сетях точка-точка может быть хорошо изображена, если нарисовать
каждый узел как окружность и связи между ними как линии, если линия
коммуникация существует между этими двумя узлами, см. рис. 1.1. Говоря
техническим языком, структура представляется графом, грани которого
представляют собой линии коммуникации в сети. Сводка по терминологии теории
графов приведена в Дополнении Б.
Рис. 1.1 Пример сети
точка-точка
Основное назначение глобальных
сетей – это обмен информацией, например, в форме электронной почты, досок
объявлений, и удаленных файлов. Разработка приемлемой системы коммнуникаций для
этих целей требует решения следующих алгоритмических проблем, некоторые из
которых обсуждаются в Части 1 этой книги.
(1) Надежность обмена
данными по типу точка-точка (глава 3). Два узла соединенные линией,
обмениваются данными по этой линии, но они должны как-то справляться с
потенциальной ненадежностью линии. Из-за атмосферных явлений, падения
напряжения и других физических обстоятельств, сообщение, посланное через линию
может быть получено с частично искаженным или даже утерянным. Эти нарушения при
передаче должен быть распознаны и исправлены.
Эта проблема встречается не только для двух напрямую соединенных
узлов, но также для узлов, не соединенных напрямую, а связанных посредством
промежуточных узлов. В этом случае проблема даже более сложна, потому что ко
всему прочему сообщения могут доставляться в порядке, отличном от того, в
котором они были посланы, а также сообщения могут прибывать с большим опозданием
или продублированные.
(2) Выбор путей
коммуникации. (глава 4). В сети точка-точка обычно слишком дорого
обеспечивать связь между каждой парой узлов. Следовательно, некоторые пары
узлов должны положиться на другие узлы для того, чтобы взаимодействовать.
Проблема маршрутизации касается выбора пути (или путей) между узлами, которые
хотят взаимодействовать. Алгоритм, используемый для выбора пути, связан со
схемой, по которой узлы именуются, т.е. форматом адреса, который узел должен
использовать, чтобы послать сообщение другому узлу. Выбор пути в промежуточных
узлах производится с использованием адреса, и выбор может быть сделан эффективно,
если в адресе кодируется в адресах.
(3) Контроль
перегрузок. Пропускная способность коммутируемой сети может сильно падать,
если много сообщений передается одновременно. Поэтому генерирование сообщений
различными узлами должно управляться и должно зависеть от свободных мощностей сети.
Некоторые методы предотвращения перегрузок обсуждаются в [Tann88, раздел 5.3].
(4) Предотвращение
тупиков. (глава 5). Сети типа точка-точка иногда называются сетями типа сохранить-и-передать,
потому что сообщение, которое посылается через несколько промежуточных узлов
должно сохраняться в каждом из этих узлов, а затем форвардиться к следующему узлу.
Так как пространство памяти, доступное для этой цели в промежуточных узлах
ограничено, то память должна тщательно управляться для того, чтобы
предотвратить тупиковые ситуации. В таких ситуациях существует набор сообщений,
ни одно из которых не может быть отфорвардено, потому что память следующего
узла в маршруте полностью занято другими сообщениями.
(5) Безопасность.
Сети, соединяют компьютеры с различными пользователями, некоторые из которых
могут попытаться злоупотребить или даже испортить системы других. Так как
возможно зарегистрироваться в компьютерной системе из любой точки мира, то
требуются надежные методы для аутентификации пользователей, криптографические
методы, сканирование входящей информации. Криптографические методы могут быть
использованы, чтобы шифровать данные для безопасности от несанкционированного
чтения и чтобы ставить электронные подписи против несанкционированного написания.
1.1.4 Локальные сети
Локальная сеть используется организацией для
соединения набора компьютеров, которые ей принадлежат. Обычно, основное
назначение этих компьютеров заключается в разделении ресурсов (как файлов, так
и аппаратной перефирии) и для облегчения обмена информацией между сотрудниками.
Иногда сети также используются для повышения скорости вычислений
(перекладыванием задач на другие узлы) и чтобы позволить некоторым узлам быть
для других запасными в случае их повреждения.
Узлы
Рис.
1.2 Сеть с шинной организацией
Примеры и
организация. В первой половинек 1970-х локальная сеть Ethernet была
разработана Xerox. В то время как имена глобальных сетей ARPANET, BITNET, и
т.д. происходят от конкретных сетей, имена локальных сетей – это обычно имена
производителей. Есть одна ARPANET, одна BITNET, и одна UUCP сеть, каждая
компания может установить свою собственную Ethernet, Token Ring или SNA сеть.
В отличие от
глобальных сетей, ethernet организована с использованием шинной структуры, т.е.
сообщение между узлами имеет место посредством единственного механизма, к
которому все узлы подключены; см. рис. 1.2. Шинная организация стала
повсеместной для локальных сетей, хотя могут быть различия в том как выглядит
механизм или как он используется.
Устройство
Ethernet разрешает передачу только одного сообщения в каждый момент времени;
другие разработки, такие как токен ринг (разработанный в лаборатории Цюрих
IBM), допускает пространственное использование, которое означает, что
несколько сообщений могут передаваться через механизм коммуникации
одновременно. Шинная организация требует немного аппаратуры и поэтому дешевая,
но имеет тот недостаток, что эта организация не очень хорошо масштабируется.
Это означает, что существует очень жесткий потолок числа узлов, которые могут
быть соединены одной шиной. Большие компании со многими компьютерами должны
соединять их несколькими шинами, и использовать мосты для соединения шин
друг с другом, создавая иерархию всей сети организации.
Не все
локальные сети используют шинную организацию. IBM разработала точка-точка
сетевой продукт называемый SNA для того, чтобы позволить покупателям соединять
их разнообразные продукты IBM. Разработка SNA усложнялась требованием ее
совместимости с почти каждым сетевым продуктом, уже предлагаемым IBM.
Алгоритмические
проблемы. Внедрение локальных сетей требует решения некоторых, но не всех,
проблем, рассмотренных в предыдущем подразделе по глобальным сетям. Надежный
обмен данными не такая большая проблема, потому что шины обычно очень надежны и
быстры. Проблема маршрутизации не встает в шинных сетях, потому что каждое
назначение может быть адресовано прямо по сети. В кольцевых сетях все сообщения
обычно посылаются в одном направлении вдоль кольца и удаляются либо получателем,
либо отправителем, что также делает проблему маршрутизации исчерпанной. В шине
нет перегрузки благодаря тому, что каждое сообщение принимается (берется с
шины) немедленно после его отправки, но все равно необходимо ограничивать
нагрузку от сообщений, ожидающих в узлах выхода на шину. Раз сообщения не
сохраняются в промежуточных вершинах, то и не возникает тупика типа
сохрани-и-передай. Нет необходимости в механизмах безопасности помимо той
обычной защиты, предлагаемой операционной системой, если компьютерами владеет одна
компания, которая доверяет своим сотрудникам.
Использование
локальных сетей для распределенного выполнения прикладных программ (набора
процессов, распространенных по узлам сети) требует решения следующих проблем
распределенного управления, некоторые из которых обсуждаются в части 2.
(1) Широковещание
и синхронизация (глава 6). Если информация должна быть доступна всем процессам,
или все процессы должны ждать выполнения некоторого глобального условия,
необходимо иметь схему передачи сообщений, которая каким-либо образом
«дозванивается» до всех процессов.
(2) Выборность
(глава 7). Некоторые задачи должны быть осуществлены точно одним процессом из
множества, например, генерирование вывода или инициализация структуры данных.
Если, как иногда желательно или необходимо, нет процесса предназначенного для
этого заранее, то распределенный алгоритм должен выбрать одни из процессов для
выполнения задачи.
(3) Обнаружение
завершения (глава 8). Не всегда есть возможность для процессов в
распределенной системе замечать напрямую, что распределенные вычисления, в
которые они вовлечены, завершены. Поэтому обнаружение необходимо для того,
чтобы сделать вычисляемые результаты окончательными.
(4) Распределение
ресурсов. Узел может потребовать доступ к некоторым ресурсам, которые доступны,
где-либо в сети, но не знает, где этот ресурс находится. Поддержка таблицы,
которая показывает местоположение каждого ресурса не всегда адекватна, потому
что число потенциальных ресурсов может быть слишком большим для этого, или
ресурсы могут мигрировать от одного узла к другому. В этом случае, запрашивающий
узел может опрашивать все или некоторые узлы на предмет доступности ресурса,
например, используя широковещательный механизм. Алгоритмы для этой проблемы
могут базироваться на волновых механизмах, описанных в главе 6, см., например
Баратц и другие [BGS87].
(5) Взаимное
исключение. Проблема взаимного исключения встает, если процессы могут
полагаться на общий ресурс, который может быть использован только одним
ресурсом в каждый момент времени. Таким ресурсом может быть принтер или файл,
который должен быть перезаписан. Распределенному алгоритму в этом случае
необходимо определить, если требуют процессы доступа одновременно, какому из
них разрешить использовать ресурс первым. Также удостовериться в том, что
следующий процесс начнет использовать ресурс, только после того, как предыдущий
процесс закончит его использовать.
(6) Обнаружение
тупиков и их разрешение. Если процессы должны ждать друг друга (как в
случае, если они разделяют ресурсы, и также, если их вычисления полагаются на
данные, обеспечиваемые другими процессами), может возникнуть циклическое
ожидание, при котором не будет возможно дальнейших вычислений. Эти тупиковые
ситуации должны определяться и правильные действия должны предприниматься для того,
чтобы перезапустить или продолжить вычисления.
(7) Распределенная
поддержка файлов. Когда узлы помещают запросы на чтение и запись удаленного
файла, эти запросы, могут обрабатываться в произвольном порядке, и отсюда
должна быть предусмотрена мера для уверенности в том, что каждый узел наблюдает
целостный вид файла или файлов. Обычно это производится временным штампованием
запросов, также как и информации в файлах и упорядочивание входящих запросов по
их временным отметкам; см., например, [LL86].
1.1.5 Многопроцессорные компьютеры
Многопроцессорный
компьютер это вычислительная система, состоящая из нескольких процессоров в
маленьком масштабе, обычно внутри одной большой коробки. Этот тип компьютерной
системы отличается от локальных сетей по следующему критерию. Его процессоры
гомогенны, т.е. они идентичны по аппаратуре. Географический масштаб машины
очень маленький, обычно порядка метра или менее. Процессоры предназначены для
совместного использования в одном вычислении (либо чтобы повысить скорость,
либо для повышения надежности). Если основное назначение многопроцессорного
компьютера это повышение скорости вычислений, то он часто называется
параллельным компьютером. Если его основное назначение – повышение надежности,
то он часто называется система репликации.
Параллельные
компьютеры подразделяются на одно-командные много-поточные по данным (или SIMD)
и много-командные много-поточные по данным (или MIMD) машины.
Рис. 1.3
Транспьютер и микросхема маршрутизатора
SIMD машины
имеют один интерпретатор инструкций, но команды выполняются большим числом
арифметических блоков. Ясно, что эти блоки имеют недостаток автономности,
которая требуется в нашем определении распределенных систем, и поэтому SIMD
компьютеры не будут рассматриваться в этой книге. MIMD машины состоят из
нескольких независимых процессоров и они классифицируются как распределенные
системы.
Процессоры
обычно оборудуются специальной аппаратурой для коммуникации с другими процессорами.
Коммуникация между процессорами может иметь место либо через шину, либо через
соединения точка-точка. Если выбрана шинная организация, то архитектура
масштабируема только до определенного уровня.
Очень
популярным процессором для разработки многопроцессорных компьютеров является
транспьютер, разработанный Inmos; см. рис. 1.3. Транспьютер состоит из
центрального процессора (CPU), специального блока с плавающей точкой (FPU),
локальной памяти, и четырех специальных процессоров. Чипы очень хорошо подходят
для построения сетей степени 4 (т.е. каждый узел соединен с четырьмя другими узлами).
Inmos также производит специальные чипы для коммуникации, называемые
маршрутизаторами. Каждый маршрутизатор может одновременно обрабатывать трафик
32 транспьютерных соединений. Каждое входящее сообщение просматривается на
предмет того, по какой связи оно может быть перенаправлено; затем оно
направляется по это связи.
Другой пример
параллельного компьютера это система Connection Machine CM-5, разработанная
Thinking Machines Corporation [LAD92]. Каждый узел машины состоит из быстрого
процессора и обрабатывающих блоков, таким образом, предлагая внутренний
параллелизм в добавление параллелизму, происходящему благодаря наличию
нескольких узлов. Так как каждый узел имеет потенциальную производительность 128
миллионов операций в секунду, и одна машина может содержать 16384 узлов, полная
машина может выполнять свыше 1012 операций в секунду. (Максимальная
машина из 16384 процессоров занимает комнату 900 м2 и скорее всего
очень дорогая.) Узлы СМ-5 соединены тремя точка-точка коммуникационными сетями.
Сеть данных, с топологией толстого дерева, используется для обмена данными по
технологии точка-точка между процессорами. Сеть управления, с технологией
бинарного дерева, осуществляет специальные операции, такие как глобальная
синхронизация и комбинирование ввода. Диагностическая сеть невидима для
программиста и используется для распространения информации о вышедших из строя
компонентах.. Компьютер может быть запрограммирован как в режиме SIMD, так и в
(синхронном) MIMD режиме.
В параллельном
компьютере вычисления поделены на подвычисления, каждое осуществляется одноим
из узлов. В репликационной системе каждый узел проводит вычисление целиком,
после чего результаты сравниваются для того, чтобы обнаружить и скорректировать
ошибки.
Построение
многопроцессорных компьютеров требует решения нескольких алгоритмических проблем,
некоторые из которых подобны проблемам в компьютерных сетях. Некоторые из этих
проблем обсуждаются в этой книге.
(1) Разработка
системы передачи сообщений. Если многопроцессорный компьютер организован
как сеть точка-точка, то должна быть разработана коммуникационная система. Это
обладает проблемами подобными тем, которые возникают в разработке компьютерных
сетей, таким как управление передачей, маршрутизация, и предотвращение тупиков
и перегрузок. Решения этих проблем часто проще, чем в общем случае компьютерных
сетей. Проблема маршрутизации, например, очень упрощена регулярностью сетевой
топологии (например, кольцо или сетка) и надежностью узлов.
Inmos
С104 маршрутизаторы используют очень простой алгоритм маршрутизации, называемый
внутренней маршрутизацией, которая обсуждается в подразделе 4.4.2, он не может
быть использован в сетях с произвольной топологией. Это поднимает вопрос могут
ли использоваться решения для проблем, например, предотвращение тупиков, в
комбинации с механизмом маршрутизации (см. проект 5.5).
(2) Разработка
виртуальной разделяемой памяти. Многие параллельные алгоритмы разработаны
для так называемой модели параллельной памяти с произвольным доступом (PRAM), в
которой каждый процессор имеет доступ к разделяемой памяти. Архитектуры с
памятью, которая разделяется физически, не масштабируются; здесь имеет место
жесткий предел числа процессоров, которые могут быть обслужены одним чипом
памяти.
Поэтому исследования направлены на архитектуры,
которые имеют несколько узлов памяти, подсоединенных к процессорам через
интерсеть. Такая интерсеть может быть построена, например, из траспьютеров.
(3) Балансировка
загрузки. Вычислительная мощь параллельного компьютера эксплуатируется
только, если рабочая нагрузка вычислений распределена равномерно по
процессорам; концентрация работы на одном узле понижает производительность до
производительности одного узла. Если все шаги вычислений могут быть определены
во время компиляции, то возможно распределить их статически. Более трудный
случай возникает, когда блоки работы создаются динамически во время вычисления;
в этом случае требуются сложные методы. Очереди задач процессоров должны регулярно
сравниваться, после чего задачи должны мигрировать от одной к другой. Для
обзора некоторых методов и алгоритмов для балансировки загрузки см. Гочинский
[Gos91, глава 9] или Харгет и Джонсон [HJ90].
(4) Робастость
против необнаруживаемых сбоев (часть 3). В репликационной системе должен
быть механизм для преодоления сбоев в одном или нескольких процессорах.
Конечно, компьютерные сети должны также продолжать их функционирование,
несмотря на сбои узла, но обычно предполагается, что такой сбой может быть
обнаружен другими узлами (см., например, алгоритм сетевого обмена в разделе
4.3). Предположения, при которых репликационные системы должны оставаться
правильными, более строгие, т.к. процессор может производить ошибочный ответ, и
то же время кооперироваться с другими при помощи протоколов как правильно
работающий процессор. Должен быть внедрен механизм голосования, чтобы
отфильтровывать результаты процессоров, так, что только правильные ответы
передаются во все время, пока большинство процессоров работает правильно.
1.1.6 Взаимодействующие процессы
Разработка
сложных программных систем может быть зачастую упрощена организацией программы
как набора (последовательных) процессов, каждый с хорошо определенной, простой
задачей.
Классический
пример для иллюстрации этого упрощения это преобразование записей Конвея. Проблема
состоит в том, чтобы читать 80 символьные записи и записывать ту же информацию
в 125 символьные записи. После каждой входной записи должен вставляться
дополнительный пробел, и каждая пара звездочек («**») должна заменяться на восклицательный
знак («!»). Каждая выходная запись должна завершаться символов конца записи
(EOR). Преобразование может быть проведено одной программой, но написание этой
программы очень сложно. Все функции, т.е. замена «**» на «!», вставка пробелов,
и вставка символов EOR, должны осуществляться за один цикл.
Программу лучше
структурировать как два взаимодействующих процесса. Первый процесс, скажем р1,
читает входные карты и конвертирует входной поток в поток печатных символов, не
разбивая на записи. Второй процесс, скажем р2, получает поток символов и
вставляет EOR после 125 символов. Структура программы как набор двух процессов
обычно предполагается для операционных систем, телефонных переключающих
центров, и, как мы увидим в подразделе 1.2.1, для коммуникационных программ в
компьютерных сетях.
Набор
кооперирующих процессов становится причиной того, что приложение становится локально
распределенным, но абсолютно возможно выполнять процессы на одном компьютере, в
этом случае приложение не является физически распределенным. Конечно, в этом
случае достигнуть физической распределенности легче именно для систем, которые
логически распределены. Операционная система компьютерной системы должна
управлять конкурентным выполнением процессов и обеспечить средства коммуникации
и синхронизации между процессами.
Процессы,
которые выполняются на одном компьютере, имеют доступ к одной физической
памяти, отсюда – естественно использование этой памяти для коммуникации. Один
процесс пишет в определенное место памяти, и другой процесс читает из этого
места. Эта модель конкурирующих процессов была использована Дейкстрой [Dij68] и
Овицким и Грайсом [OG76]. Проблемы, которые рассматривались в этом контексте,
включают следующие.
(1) Атомичность
операций с памятью. Часто предполагается, что чтение и запись одного слова
памяти атомичны, т.е. чтение и запись выполняемые процессом завершается перед
тем как другая операция чтения или записи начнется. Если структуры большие,
больше чем одно слово обновляется, операции должны быть аккуратно синхронизированы,
чтобы избежать чтения частично обновленной структуры. Это может быть
осуществлено, например, применением взаимного исключения [Dij68] в структуре:
пока один процесс имеет доступ к структуре, ни один другой процесс не может
начать чтение или запись. Применение взаимного исключения с использованием
разделяемых переменных усложнено из-за возможности нескольких процессов искать
поле в этой структуре в это же время.
Условия ожидания, налагаемые доступом со взаимным исключением к
разделяемым данным, могут понизить производительность процессов, например, если
«быстрый» процесс должен ждать данные, в настоящее время используемые
«медленным» процессом. В недавние годы внимание концентрировалось на применении
разделяемых переменных, которые являются wait-free, что значит, что процесс
может читать или писать данные без ожидания любых других процессов. Чтение и
запись могут перекрываться, но только при тщательной проработке алгоритмов
чтения и записи, которые должны обеспечить атомичность. Для обзора алгоритмов
для wait-free атомичных разделяемых переменных см. Киросис и Кранакис [KK89].
(2) Проблема
производитель-потребитель. Два процесса, один из которых пишет в
разделяемый буфер и другой и которых читает из буфера, должны быть
скоординированы, чтобы предупредить первый процесс от записи, когда буфер полон
и второй процесс от чтения, когда буфер пуст. Проблема
производитель-потребитель возникает, когда решение проблемы преобразования
Конвея выработано; р1 производит промежуточный поток
символов, и р2 потребляет его.
(3) Сборка
мусора. Приложение, которое запрограммировано с использованием динамических
структур данных может производить недоступные ячейки памяти, называемые мусором.
Формально, приложение должно бы прерваться, когда у системы памяти кончается
свободное место, для того чтобы позволить специальной программе, называемой сборщиком
мусора, идентифицировать и вернуть недоступную память. Дейкстра и другие
[DLM78] предложили сборщик мусора на-лету, который может работать как отдельный
процесс, параллельно с приложением.
Требуется сложное взаимодействие между приложением и сборщиком, т.к.
приложение может модифицировать структуры указателей в памяти, в то время как
сборщик решает какие ячейки являются недоступными. Алгоритм должен быть
тщательно проанализирован, чтобы показать, что модификации не обусловят
ошибочный возврат доступным ячеек. Алгоритм для сбора мусора на-лету с
упрощенным доказательством правильности был предложен Бен-Ари [BA84].
Решения
проблем, перечисленных здесь, демонстрируют, что могут быть решены очень
трудные проблемы взаимодействия процессов для процессов, которые сообщаются
посредством разделяемой памяти. Однако, решения часто исключительно усложнены и
иногда очень незначительное перемешивание шагов различных процессов дает
ошибочные результаты для решений, которые кажутся правильными на первый и даже
на второй взгляд. Поэтому, операционные системы и языки программирования
предлагают примитивы для более структурной организации межпроцессовых
коммуникаций.
(1)
Семафоры. Семафор [Dij68] это неотрицательная переменная, чье
значение может быть прочитано и записано за одну атомичную операцию. V операция
приращает ее значение, а Р операция уменьшает ее значение, когда оно
положительно ( и подвешивает выполнение процесса на этой операции, пока значение
переменной нулевое).
Семафоры – подходящее средство для применения взаимного исключения над
разделяемой структурой данных: семафор инициализируется в 1, и доступ к
структуре предваряется операцией Р и завершается операцией V. Семафоры
накладывают большую ответственность на каждый процесс за правильное
использование; целостность разделяемых данных нарушается, если процесс
манипулирует данными неправильно или не выполняет требуемых Р и V операций.
(2)
Мониторы. Монитор [Hoa74] состоит из структуры данных и набора
процедур, которые могут выполняться над этими данными, с помощью их вызова
процессами способом, использующим взаимное исключение. Т.к. к данным доступ
осуществляется полностью через процедуры, объявленные в мониторе, гарантируется
правильное использование данных, если монитор объявлен корректно. Монитор, таким
образом, предотвращает не позволенный доступ к данным и синхронизирует доступ
различных процессов.
(3)
Каналы. Канал [Bou83] это механизм, который передает поток данных
от одного процесса к другому и синхронизирует два коммутирующих процесса; это
заранее запрограммированное решение проблемы производитель-потребитель.
Канал это основной механизм коммуникаций в операционной системе UNIX.
Если программа р1 выполняет процесс р1
преобразования Конвея и р2 выполняет р2 ,
команда UNIX р1 | р2 вызывает две программы
и соединяет их каналом. Вывод р1 буферизируется и становится
вводом р2 ; р1 подвешивается, когда буфер
полон, и р2 подвешивается, когда буфер пуст.
(4)
Передача сообщений. Некоторые языки программирования, такие как
OCCAM и ADA, обеспечивают передачу сообщений, как механизм для межпроцессовой
коммуникации. Проблемы синхронизации относительно легко решаются с
использованием передачи сообщений; т.к. сообщение не может быть получено до его
передачи, возникает временное отношение между событиями благодаря обмену сообщениями.
Передача сообщений может быть выполнена с использованием мониторов или
каналов, и это естественные средства для систем коммуникации, которые
используются в аппаратуре распределенных систем (без разделяемой памяти). В
самом деле, языки OCCAM и ADA были разработаны с идеей использования их для
физически распределенных приложений.
Рис 1.4 Слоеная сетевая
архитектура
1.2 Архитектура и
Языки
Программное обеспечение для
выполнения компьютерных сетей связей очень усложнено. В этом разделе объяснено,
как это программное обеспечение обычно структурируется в ациклически зависимых
модулях названных уровнями (Подраздел 1.2.1). Мы обсуждаем два стандарта с
сетевой архитектурой, а именно, модель МЕЖДУНАРОДНОЙ ОРГАНИЗАЦИИ ПО
СТАНДАРТИЗАЦИИ Соединения Открытых систем, стандарт для глобальных сетей, и
дополнительного стандарта IEEE для локальных сетей (Подразделы, 1.2.2 и 1.2.3).
Также языки, используемые для программирования распределили системы, кратко обсуждены
(Подраздел 1.2.4).
1.2.1 Архитектура
Сложность задач, выполняемых подсистемой связи
распределенной системы требует, чтобы эта подсистема была разработана высоко
структурированным способом. К этому моменту, сети всегда организовываются как
совокупность модулей, каждое выполнение очень специфическая функция и основывающаяся
на услугах, предлагаемых другими модулями. В сетевых организациях имеется
всегда строгая иерархия между этими модулями, потому что каждый модуль
исключительно использует услуги, предлагаемые предыдущим модулем. Модули
названы уровнями или уровнями в контексте сетевой реализации; см. 1.4 Рисунок.
Каждый уровень осуществляет часть функциональных возможностей, требуемых для
реализации сети и полагается на уровень только ниже этого. Услуги, предлагаемые
i уровнем i + 1 уровню точно описаны в интерфейсе i уровня и i + 1 уровня
(кратко, i / (i + 1) интерфейс). При проектировании сети, в первую очередь,
нужно определить число уровней и интерфейсов между последующими уровнями.
Функциональные возможности каждого уровня должны
быть выполнены распределенным алгоритмом, таким, что алгоритм для i уровня
решает "проблему", определенную i / (i + 1) интерфейсом, согласно
"предположениям", определенным в (i — l) /i интерфейсе. Например, (i
— 1) /i интерфейс может определять, что сообщения транспортируются из узла p к
узлу q, но некоторые сообщения могут быть потеряны, в то время как i / (i + 1)
интерфейс определяет, что сообщения передаются от p до q надежно.
Алгоритмическая проблема для i уровня затем - выполнить надежное прохождение
сообщения, используя ненадежное прохождение сообщения, что обычно делается с
использованием подтверждения и перепередачи потерянных сообщений (см.
Подраздел, 1.3.1 и Главу 3). Решение этой проблемы определяет тип сообщений,
обменянных процессами i уровня и значение этих сообщений, т.е., как процессы
должны реагировать на эти сообщения. Правила и соглашения, используемые в
"сеансе связи" между процессами i уровня упоминаются как layer-i
протокол. Самый низкий уровень иерархии (уровень 0 на Рисунке 1.4) - всегда
аппаратный уровень. Интерфейс 0/1 описывает процедуры, которыми уровень i может передать необработанную информацию через соединяющие провода, и
описание уровня непосредственно определяет то, какие типы провода используются,
сколько вольт представляют единицу или ноль, и т.д. Важное наблюдение - то, что
изменение в реализации уровня 0 (замена проводов другими проводами или
спутниковыми подключениями) не требует, чтобы интерфейс 0/1 был изменен. Те же
самые условия в более высоких уровнях: интерфейсы уровня служат экраном от
реализация уровня для других уровней, и реализация может быть изменена без
того, чтобы воздействовать на другие уровни. Под сетевой архитектурой мы
понимаем совокупность уровней и сопровождающих описаний всех интерфейсов и
протоколов. Поскольку сеть может содержать узлы, произведенные различными изготовителями,
программируемые программным обеспечением, написанным различными компаниями,
важно, чтобы изделия различных компаний являлись совместимыми. Важность совместимости
была признана во всем мире и следовательно стандартные сетевые архитектуры были
разработаны. В следующем подразделе два стандарта обсуждаются, что получило
"официальное" статус, потому что они приняты влиятельными организациями
(МЕЖДУНАРОДНАЯ ОРГАНИЗАЦИЯ ПО СТАНДАРТИЗАЦИИ, и Институт Электрических и Электронных
Инженеров, IEEE). Протокол управления передачей / internet протокол (TCP/IP) -
совокупность протоколов, используемых в Internet. TCP/IP - не официальный
стандарт, но используется настолько широко, что стал фактическим стандартом.
Семейство протоколов TCP/IP (см. Davidson [Dav88] для введения) структурирован
согласно уровням OSI модели, обсужденной в следующем подразделе, но протоколы
могут использоваться в глобальных сетях также как в локальных сетях.
Более высокие уровни содержат протоколы для
электронной почты (простой протокол передачи почты - SMTP), передача файлов
(протокол передачи файлов, FTP), и двунаправленная связь для удаленного входа в
систему (Telnet).
1.2.2 Ссылочная
Модель OSI
МЕЖДУНАРОДНАЯ ОРГАНИЗАЦИЯ ПО СТАНДАРТИЗАЦИИ
установила стандарт для компьютерных изделий(программ) для работы с сетями типа
тех, которые используются (главным образом) в глобальных сетях. Их стандарт для
сетевой архитектуры назван Соединением открытых систем (OSI) ссылочной моделью,
и будет описан кратко в этом подразделе. Потому что стандарт не полностью
соответствующий для использования в локальных сетях, дополнительные стандарты
IEEE для локальных сетей обсуждены в следующем подразделе. Модель ссылки OSI
состоит из семи уровней, а именно физического, связи данных, сети, транспорта,
сеанса, представления, и уровней прикладной программы. Ссылочная модель
определяет интерфейсы между уровнями и обеспечивает, для каждого уровня, один
или большее количество стандартных протоколов (распределенные алгоритмы, чтобы
выполнить уровень).
Физический (1) уровень. Цель физического уровня состоит в том, чтобы
передать последовательности битов по каналу связи. Поскольку имя уровня
предполагает, что эта цель достигнута посредством физического подключения между
двумя узлами, типа телефонной линии, волоконно-оптического подключения, или
спутникового подключения. Проект уровня непосредственно - вполне вопрос для
инженеров - электриков, в то время как интерфейс 1/2 определяет процедуры,
которыми следующий уровень вызывает услуги физического уровня. Обслуживание
физического уровня не надежно; поток битов может быть попорчен в течение передачи.
Канальный уровень (2). Цель канального уровня состоит в том, чтобы
маскировать ненадежность физического уровня, то есть обеспечивать надежную
связь с более высокими уровнями. Уровень связи данных только осуществляет
надежное подключение между узлами, которые непосредственно связаны физической
связью, потому что он сформирован непосредственно над физическим уровнем.
(Связь между несмежными узлами выполнена в сетевом уровне.) Чтобы достигнуть
цели, уровень делит поток битов на части фиксированной длины, названные кадрами.
Приемник кадра может проверять(отмечать), был ли кадр получен правильно,
проверяя контрольную сумму, которая является некоторой избыточной информацией,
добавленной к каждому кадру. Имеется обратная связь от приемника до
отправителя, чтобы сообщить отправителю относительно правильно или неправильно
полученного кадра; эта обратная связь происходит посредством сообщений
подтверждения.
Отправитель пошлет кадр снова, если оказалось,
что он получен неправильно или полностью потерян. Общие принципы, объясненные в
предыдущем параграфе могут быть усовершенствованы к ряду различных протоколов
связи данных. Например, сообщение подтверждения может быть послано для кадров,
которые получены (положительные подтверждения) или для кадров, которые
отсутствуют из совокупности полученных кадров (отрицательные подтверждения).
Окончательная ответственность за правильную передачу всех кадров может быть на
отправителе или стороне приемника. Подтверждения могут быть посланы для
одиночных кадров или блоков кадров, кадры могут иметь числа последовательности
или не иметь, и т.д.
Сетевой уровень (3). Цель сетевого уровня состоит в том, чтобы обеспечить
средства связи между всеми парами узлов, не только связанных физическим
каналом. Этот уровень должен выбрать маршруты через сеть, используемую для
связи между не-смежными узлами и должен управлять загрузкой движения в каждом
узле и канале. Выбор маршрутов обычно основан на информации относительно
сетевой топологии, содержащейся в маршрутизации таблиц, сохраненных в каждом
узле. Сетевой уровень содержит алгоритмы, чтобы модифицировать таблицы
маршрутизации, если топология сети изменилась (вследствие сбоя канала или
восстановления). Такой сбой или восстановление обнаруживается канальным уровнем
связи. Хотя канальный уровень обеспечивает надежное обслуживание у сетевого
уровня, обслуживание, предлагаемое сетевым уровнем не надежно. Сообщения
(названные пакетами в этом уровне) посланные от одного узла до другого могут
следовать различными путями, вызывая опасность, что одно сообщение настигнет
другое. Вследствие сбоев узла сообщения могут быть потеряны (узел может
накрыться во время хранения cообщения), и вследствие лишних сообщений
перепередач могут даже быть дублированы. Уровень может гарантировать
ограниченному пакету срок службы; то есть, существует константа c такая, что
каждый пакет или передается в узел адресата в течение с секунд, или теряется.
Транспортный уровень (4). Цель транспортного уровня состоит в том, чтобы
маскировать ненадежность, представленную сетевым уровнем, то есть, обеспечивать
надежную связь между любыми двумя узлами. Проблема была бы подобна той решенной
канальным уровнем, но это еще усложнено возможностью дублирования и
переупорядочения сообщений. Это делает невозможным использовать циклические
числа последовательности, если ограничение на срок службы пакета не гарантируется
сетевым уровнем.
Алгоритмы, используемые для управления передачи
в транспортном уровне используют подобные методы для алгоритмов в канальном
уровне: числа последовательности, обратная связь через подтверждения, и
перепередачи.
Уровень сеанса (5). Цель уровня сеанса состоит в том, чтобы
обеспечить средства для поддержания подключений между процессами в различных
узлах. Подключение может быть открыто и закрыто и между открытием, и закрытием
подключение может использоваться для обмена данных, используя адрес сеанса
скорее, чем повторение адреса удаленного процесса с каждым сообщением. Уровень
сеанса использует надежную непрерывную связь, предлагаемую транспортным
уровнем, но структурирует передаваемые сообщения в сеансы. Сеанс может
использоваться для передачи файла или удаленного входа в систему. Уровень
сеанса может обеспечивать механизмы для восстановления, если узел терпит крах в
течение сеанса и для взаимного исключения, если критические операции не могут
выполняться на обоих концах одновременно.
Уровень представления (6). Цель уровня представления состоит в том, чтобы
выполнить преобразование данных, где представление информации в одном узле
отличается от представления в другом узле или не подходящее для передачи. Ниже
этого уровня (то есть, при интерфейсе 5/6) данные находятся в передавабельной и
стандартизированной форме, в то время как выше этого уровня (то есть, при
интерфейсе 6/7) данные находятся в пользовательско - или компьютерно -
специфической форме. Уровень выполняет сжатие данных и декомпрессию, чтобы
уменьшить количество данных, переданных через более низкие уровни. Уровень
выполняет шифрование данных и расшифровку, чтобы гарантировать
конфиденциальность и целостность в присутствии злонамеренных сторон, которые
стремятся получать или разрушать переданные данные.
Уровень прикладной программы (7). Цель уровня прикладной программы состоит в том,
чтобы выполнять конкретные требования пользователя типа передачи файла,
электронной почты, информационных табло, или виртуальных терминалов. Широкое
разнообразие возможных прикладных программ делает невозможным стандартизировать
полные функциональные возможности этого уровня, но для некоторых из прикладных
программ, перечисленных здесь, стандарты были предложены.
1.2.3 OSI Модель в
локальных сетях: IEEE Стандарты
На проект ссылочной модели OSI влияют в большой
степени архитектуры существующих глобальных сетей. Технология, используемая в
локальных сетях налагает различные программные требования, и из-за этих
требований некоторые из уровней могут почти совсем отсутствовать в локальных
сетях. Если сетевая организация полагается на общую шину, общедоступную всеми
узлам (см. Подраздел 1.1.4), то сетевой уровень почти пуст, потому что каждая
пара узлов связана непосредственно через шину. Проект транспортного уровня
очень упрощен ограниченным количеством недетерминизма представленного шиной, по
сравнению с промежуточной двухточечной сетью. Напротив, канальный уровень
усложнен фактом, что к той же самой физической среде обращается потенциально
большое количество узлов. В ответе на эти проблемы IEEE одобрил дополнительные
стандарты, покрывая только более низкие уровни OSI иерархии, для использования
в локальных сетях (или, если быть более точным, во всех сетях, которые являются
структурированными шиной скорее, чем двухточечными соединениями). Потому что
никакой одиночный стандарт не мог бы быть достаточно общий, чтобы охватить все
сети уже широко использующиеся, IEEE одобрил три различных, несовместимых
стандарта, а именно МНОЖЕСТВЕННЫЙ ДОСТУП С ОПРОСОМ НЕСУЩЕЙ И РАЗРЕШЕНИЕМ
КОНФЛИКТОВ, маркерную шину , и эстафетное кольцо. Канальный уровень заменен
двумя подуровнями, а именно управление доступом к среде и подуровни управления
логическим соединением.
Физический (1) уровень. Цель физического уровня в стандартах IEEE подобна
таковому первоначального стандарта МЕЖДУНАРОДНОЙ ОРГАНИЗАЦИИ ПО СТАНДАРТИЗАЦИИ,
а именно передавать последовательности битов. Фактические стандартные описания
(тип монтажа и т.д.), однако, радикально различны, вследствие того, что вся связь
происходит через общедоступную среду, а не через двухточечные подключения.
Medium-access-control подуровень (2a). Цель этого подуровня состоит в том, чтобы
решить конфликты, которые возникают между узлами, которые хотят использовать
общедоступную среду связи. Статичный подход раз и навсегда планировал бы
интервалы времени, в течение которых каждому узлу позволяют использовать среду.
Этот метод теряет много пропускной способности, однако, если только несколько
узлов имеют данные, чтобы передавать, и все другие узлы тихи, среда остается в
простое в течение времен, планируемых для тихих узлов. В шинах маркера и
эстафетных кольцах доступ к среде находится по карусельному принципу: узлы
циркулируют привилегию, названную маркером, среди них, и узлу, задерживающему
этот маркер, позволяют использовать среду. Если узел, задерживающий маркер, не
имеет никаких данных, чтобы передать, он передает маркер к следующему узлу. В
эстафетном кольце циклический порядок, в котором узлы получают их право хода,
определен физической топологией подключения (который, действительно, кольцо),
в то время как в шине маркера, циклический порядок определен динамически
основываясь на порядке адресов узлов. В стандарте МНОЖЕСТВЕННОГО ДОСТУПА С
ОПРОСОМ НЕСУЩЕЙ И РАЗРЕШЕНИЕМ КОНФЛИКТОВ узлы наблюдают, когда среда неактивна,
и если так, то им позволяют послать. Если два или больше узла запускают посылку
(приблизительно) одновременно, имеется проверка на пересечение, которое обнаруживается,
что заставляет каждый узел прерывать передачу и пытаться снова в более позднее
время.
Logical-link-control подуровень (2b). Цель этого уровня сравнима с целью канального
уровня в OSI модели, а именно: управлять обменом данными между узлами. Уровень
обеспечивает управление ошибками и управление потоком данных, используя методы,
подобные тем использованных в OSI протоколах, а именно числа последовательности
и подтверждения. Видящийся с точки зрения более высоких уровней,
logical-link-control подуровень появляется подобно сетевому уровню OSI модели.
Действительно, связь между любой парой узлов происходит без того, чтобы
использовать промежуточные узлы, и может быть обработана непосредственно
logical-link-control подуровнем. Отдельный сетевой уровень не следовало бы
выполнять в локальных сетях; вместо этого, транспортный уровень сформирован
непосредственно на верхней части logical-link-control подуровня.
1.2.4 Поддержка Языка
Реализация одного из программных уровней сети
связей или распределенной прикладной программы требует, чтобы распределенный
алгоритм, используемый в том уровне или прикладной программе был кодирован на
языке программирования. На фактическое кодирование конечно высоко влияет язык
и особенно примитивы, которые он предлагает. Так как в этой книге мы концентрируемся
на алгоритмах и не на их кодировании как программа, наша базисная модель
процессов основана на состояниях процесса и переходах состояния (см. Подраздел
2.1.2), а не на выполнении команд, принимаемых из предписанного набора.
Конечно, неизбежно, чтобы там, где мы представили алгоритмы, требовалась
некоторая формальная запись; запись программирования, используемая в этой книге
обеспечена в Приложении A. В этом подразделе мы описываем некоторые из
конструкций, которые можно наблюдать в фактических языках программирования,
разработанных для распределенных систем. Мы ограничиваемся здесь кратким
описанием этих конструкций; Для большего количества деталей и примеров
фактических языков, которые используют различные конструкции, см., например,
Bal [Bal90]. Язык для программирования распределенных прикладных программ,
должен обеспечить средства, чтобы выразить параллелизм, обрабатывать
взаимодействие, и недетерминизм. Параллелизм, конечно, требуется для
программирования различных узлов системы таким способом, которым узлы выполнят
их часть программы одновременно. Связь между узлами должна также быть
поддержана в соответствии с языком программирования. Недетерминизм необходим,
потому что узел должен иногда быть способен получить сообщение от различных
узлов, или быть способным либо посылать, либо получать сообщение.
Параллелизм. Наиболее соответствующая степень параллелизма в распределенной
прикладной программе зависит от отношения(коэффициента) между стоимостью связи
и стоимостью вычисления. Меньшая степень параллелизма учитывает более быстрое
выполнение, но также и требует большего количества связи, так, если связь
дорога, усиление в быстродействии вычисления может быть потеряно в
дополнительной стоимости связи. Параллелизм обычно выражается, определением
нескольких процессов, где каждый процесс является последовательным объектом с
собственным пространством состояния. Язык может или предлагать возможность
статического определения совокупности процессов или позволять динамическое создание
и завершение процессов. Также возможно выразить параллелизм посредством
параллельных инструкций или в функциональном языке программирования.
Параллелизм не всегда явен в языке; выделение разделов кода в параллельные
процессы может выполняться сложным транслятором.
Связь. Связь между процессами свойственна распределенным системам: если
процессы не связываются, каждый процесс функционирует в изоляции от других
процессов и должен изучаться в изоляции, a не как часть распределенной системы.
Когда процессы сотрудничают в вычислении, связь необходима, если один процесс
нуждается в промежуточном результате, произведенном другим процессом. Также,
синхронизация необходима, потому что вышеупомянутый процесс должен быть
приостановлен, пока результат не доступен. Прохождение cообщения затрагивает, и
связь и синхронизацию; общедоступная память затрагивает только связь:
дополнительная осторожность должна быть предусмотрена для синхронизации процессов,
которые сообщаются c использованием общедоступной памяти. В языках, которые
обеспечивают передачу сообщения, доступны операции "посылать" и
"получать". Связь происходит выполнением посылающейся операции в
одном процессе (следовательно названным процессом отправителя) и получающейся
операцией в другом процессе (процесс приемника). Параметры посылающей операции
- адрес приемника и дополнительные данные, формирующие содержание сообщения.
Эти дополнительные данные становятся доступными приемнику, когда получающая
инструкция выполнена, то есть, таким образом осуществляет связь. Получающая
операция может быть завершена только после того, как посылающая операция была выполнена,
что и осуществляет синхронизацию. В некоторых языках получающая операция не
доступна явно; вместо этого, процедура или операция активизируется неявно,
когда сообщение получено. Язык может обеспечивать синхронное прохождение
сообщения, когда посылающая операция завершена только после выполнения
получающей операции.
Другими словами, отправитель блокирован, пока
сообщение не было получено, и имеет место двухсторонняя синхронизация между
результатами приемника и отправителем. Сообщения могут быть посланы
двухточечно, то есть, от одного отправителя на один приемник, или
широковещательно, когда то же самое сообщение получено всеми приемниками.
Термин мультиприведение также используется, чтобы обратиться к сообщениям,
которые посланы совокупности (не обязательно всех) процессов. Несколько более
структурированный примитив связи - удаленный вызов процедуры (RPC). Чтобы
связываться с процессом b, процедура a обращается к процедуре, представленной в
процессе b, посылая параметры процедуры в сообщении; а приостанавливается,
пока результат процедуры не будет возвращен в другом сообщении. Вариант для прохождения
сообщения - использование общедоступной памяти для связи; один процесс пишет
значение переменной, и другой процесс читает значение. Синхронизация между
процессами тяжелее, чтобы ее достигнуть, потому что чтение переменной может
быть использовано прежде, чем переменная была записана. При использовании
примитивов синхронизации типа семафоров [Dij68] или мониторов [Hoa78], возможно
выполнить передачу сообщения, в среде общедоступных переменных. И наоборот,
также возможно выполнить (виртуальную) общедоступную память в передающей
сообщения среде, но это очень неэффективно.
Недетерменизм. В многих точках в выполнении процесс может быть способен продолжиться
различными способами. Получающая операция часто недетерминирована, потому что
это позволяет получение сообщений от различных отправителей. Дополнительные
способы выражать недетерменизм основаны на охраняемых командах. Охраняемая команда
в наиболее общей форме - список инструкций, каждый предшествованный булевым
выражением (его защитником). Процесс может продолжать выполнение с любой из
инструкций, для которых соответствующая защита оценивается истиной. Защита
может содержать получающую операцию, когда она оценивается истиной, если
имеется сообщение, доступное, чтобы быть полученным.
1.3 Распределенные
Алгоритмы
Предыдущие разделы дали причины для использования
распределенных компьютерных систем и объяснили характер этих систем; потребность
программировать эти системы возникает как следствие. Программирование распределенных
систем должно быть основано на использовании правильных, гибких, и эффективных
алгоритмов. В этом разделе обсуждается, что разработка распределенных
алгоритмов - ремесло, совершенно различное по характеру от ремесла,
используемого в разработке централизованных алгоритмов. Распределенные и
централизованные системы отличаются по ряду существенных отношений, обрабатываемых
в Подразделе 1.3.1 и иллюстрируемых в 1.3.2 Подразделе. Распределенное
исследование алгоритмов следовательно развилось как независимое поле научного
исследования; см. 1.3.3 Подраздел. Эта книга предназначена, чтобы представить
читателю это поле исследования. Цели книги и выбора результатов, включенных в
книгу установлены в Подразделе 1.3.4.
1.3.1 Распределенный
против Централизованных Алгоритмов
Распределенные системы отличаются от
централизованных компьютерных систем по трем существенным отношениям, которые
мы теперь обсуждаем.
(1) Недостаток знания глобального состояния.
В централизованных решениях управление алгоритмом может быть сделано основанным
на наблюдениях состояния системы. Даже при том, что к всему состоянию обычно
нельзя обращаться в одиночной машинной операции, программа может осматривать
переменные один за другим, и принимать решение, в конце концов релевантная
информация будет расценена. Никакие данные не изменяются между проверкой и
решением, и это гарантирует целостность решения. Узлы в распределенной системе
имеют доступ только к их собственному состоянию и не к глобальному состоянию
всей системы. Следовательно, не возможно делать решение управления основанным
на глобальном состоянии. Это имеет место тот факт, что узел может получать
информацию относительно состояния других узлов и базировать решения управления
на этой информации. В отличие от централизованных систем, факт, что полученная
информация является старой, может стать причиной получения недопустимой
информации, потому что состояние другого узла, возможно, изменилось между посылкой
информации состояния и решения, основанного на этом. Состояние подсистемы связи
(то есть, какие сообщения находятся в транзите в некоторый момент) никогда
непосредственно не наблюдается узлами. Эта информация может только быть
выведена косвенно, сравнивая информацию относительно сообщений, посланных и
полученных узлами. Недостаток глобального кадра времени. События,
составляющие выполнение централизованного алгоритма полностью упорядочиваются
естественным способом их временным появлением; для каждой пары событий, каждое
происходит ранее или позже чем другое. Временное отношение, вызванное на
событиях, составляющих выполнение распределенного алгоритма - не общее
количество; Для некоторых пар событий может иметься причина для решения, что
каждое происходит перед другим, но для других пар имеет место, что ни одно из
событий не происходит перед другим [Lam78]. Взаимное исключение может быть
достигнуто в централизованной системе требующих его, если доступ процесса p к
ресурсу начинается позже чем доступ процесса q, то доступ процесса p начался
после того, как доступ процесса q закончился. Действительно, все такие события
(старт и окончание доступа процессов p и q) полностью упорядочиваются отношением
временного предшествования; в распределенной системе они - не упорядочиваются,
и та же самая стратегия не достаточна. Процессы p и q могут начать обращаться к
ресурсу, в то время как начало одного не предшествует началу другой.
(3) Недетерменизм. Централизованная
программа может описывать вычисления, поскольку они разворачиваются из
некоторого ввода недвусмысленно; имея данную программу и ввод, только одиночное
вычисление возможно. Напротив, выполнение распределенной системы обычно не
-детерминировано, из-за возможных различий в быстродействии выполнения компонентов
системы.
Рассмотрим ситуацию, где процесс сервера может
получать запросы из неизвестного числа процессов пользователя. Сервер не может
приостановить обработку запросов, пока все запросы не были получены, потому что
не известно, сколько сообщений прибудет. Следовательно, каждый запрос должен
быть обработан немедленно, и порядок обработки - порядок, в который запросы прибывают.
Порядок, в котором клиентура посылает их запросы, может быть известен, но
поскольку задержки передачи не известны, запросы могут прибывать в различном
порядке.
Комбинация недостатка знания относительно
глобального состояния, недостаток глобального кадра времени, и недетерменизм
делает проект распределенных алгоритмов запутанным ремеслом, потому что три
аспекта вмешиваются несколькими способами. Понятия времени и состояния очень
связаны; в централизованных системах понятие времени может быть определено,
рассматривая последовательность состояний, принятых системой в течение
выполнения. Даже при том, что в распределенной системе глобальное состояние
может быть определено, и выполнение может рассматриваться как
последовательность глобальных состояний (Определение 2.2), это представление
имеет ограниченное использование, так как выполнение может также быть описано
другими последовательностями глобальных состояний (Теорема 2.21). Те
альтернативные последовательности обычно состоят из различных глобальных
состояний; это придает утверждению "система, принимала это или то
состояние в течение выполнения " очень сомнительное значение. Недостаток
знания относительно глобального состояния мог бы компенсироваться, если было возможно
предсказать это глобальное состояние из алгоритма, который выполняется. К
сожалению, это не возможно из-за свойственного недетерменизма в выполнении
распределенных систем.
Рис. 1.5 Упрощенная сетевая архитектура
1.3.2 Пример: Связь с
одиночным сообщением
Мы проиллюстрируем трудности, налагаемые
недостатком знания относительно глобального состояния и недостатка глобального
кадра, с помощью примера, обсужденного Beisnes [Bel76l, а именно надежный обмен
информацией через ненадежную среду. Рассмотрим два процесса a и b, связанных
сетью передачи данных, которая передает сообщения от одного процесса до
другого. Сообщение может быть получено в произвольно длительное время после
того, как оно послано, оно может также быть потеряно в целом в сети. Надежность
связи увеличивается при использовании сетевых процедур управления (NCPs), через
который a и b обращаются к сети. Процесс a инициализирует связь, передавая
информационный модуль m к NCP A. Взаимодействие между NCPs (через
сеть передачи данных, DN) должно гарантировать, что информация m
передана в процесс b (NCP B), после которого a уведомляется относительно
доставки (через NCP A). Структура связи изображена в Рисунке 1.5. Даже если
только одиночный информационный модуль должен транспортироваться от a до b,
ненадежность сети вынуждает NCP A и NCP B вовлекаться в сеанс связи, состоящий
из нескольких сообщений. Они поддерживают информацию состояния относительно
этого сеанса связи, но потому что число возможных партнеров сеанса связи для
каждого процесса большое, то требуется, чтобы информация состояния была
отброшена после того, как обмен сообщениями завершен. Инициализация информации
состояния называется открытие, и ее отбрасывание называется закрытием
сеанса связи. Заметьте, что после закрытия сеанса связи, NGP находится в точно
том же самом состоянии как и перед открытием его; это называется закрытым
состоянием. Информационный модуль m., говорят, потерян, если a
получил уведомление от b, но модуль фактически не был никогда передан к b.
Модуль m, говорят, дублирован если он был передан дважды.
Надежные механизмы связи предотвращают и потери и дублирования. Принимается,
что NCPs могут терпеть неудачу, после которой они перезапускаются в закрытом
состоянии (действительно теряя всю информацию относительно открытого в настоящее
время сеанса связи).
Никакая надежная связь не достижима. Как первое наблюдение, может быть показано, что
независимо от того, как запутанно NCPs разработаны, не возможно достигнуть
полностью надежной связи. Это наблюдение может быть сделано независимо от
проекта сети передачи данных или NCPs и только полагается на предположение, что
NCP может терять информацию относительно активного сеанса связи. Чтобы видеть
это, предположим, что после того, как инициализация связи a, NCP и NCP В
запускает разговор(сеанс связи), в течение которого NCP В доставляет м. b после
получения сообщения М. из NCP A. Рассмотрите случай где NCP В сбоями и
перезапущен в закрытом состоянии после того, как NCP послал сообщение, м. В
этой ситуации, ни NCP ни NCP В не может сообщать, был ли м. уже поставлен,
когда NCP В потерпел крах; NCP, потому что это не может наблюдать события в
NCP В (недостаток знания относительно глобального состояния) и NCP В, потому
что это потерпело крах и было перезапущено в закрытом состоянии. Независимо от
того, как NCPs продолжают их разговор(сеанс связи), ошибку можно представлять.
Если NCP посылает сообщение NCP В, снова и NCP В доставляет сообщение, дублирование
может возникать. Если сообщение к дано без поставки, потеря может возникать. Мы
теперь оценим несколько возможных проектов NCPs относительно возможности потери
или дублирования сообщений. Мы пробуем разрабатывать протоколы таким способом,
которым потерь избегают в любом случае.
Cеанс связи с одним сообщением. В самом простом возможном проекте, NCP А посылает
данные, неизменные через сеть, сообщает об этом a, и закрывается, в одиночном
действии после инициализации. NCP В всегда доставляет сообщение, которое
он получает, к b и закрывается после каждой доставки. Этот протокол
представляет потерю всякий раз, когда сеть отказывается доставлять сообщение,
но не имеется никакой возможности введения дублирований.
Cеанс связи с двумя сообщениями. Ограниченная защита против потери сообщений
предлагается добавлением подтверждений к протоколу. В нормальном сеансе связи,
NCP А посылает сообщение данных (данные, m) и ждет получения
сообщения подтверждения (ack) из NCP B. Когда это сообщение получено,
NCP А закрывает сеанс связи. NCP B, после получения сообщения (данные,
m), доставляет m к b, отвечает сообщением (ack), и закрывается. Подводя
итоги, можно сказать, что свободный от ошибок сеанс связи состоит из трех
событий.
1. NCP А send (данные, m)
2. NCP B receive (данные, m),
deliver m., send (ack), close
3. NCP А receive (ack), notify,
close.
Возможность потери сообщения данных вынуждает
NCP А посылать (данные, m) снова, если подтверждение не получено
после некоторого времени. (Из-за недостатка знания относительно глобального
состояния, NCP А не может наблюдать, были ли (данные, m)
потеряны, (ack) был потерян, или NCP B потерпел крах между
получением (данные, m) и посылкой (ack).) К этому моменту, NCP A
ждет получения подтверждения в течение ограниченного количества времени, и
если никакое такое сообщение не получено, таймер переполняется и происходит
таймаут. Может быть легко замечено, что эта опция перепередачи представляет
возможность дубликата, а именно, если не первоначальное сообщение данных, а
подтверждение было потеряно, как в следующем сценарии:
1. NCP A send ( data, m)
2. NCP B receive (data,
m), deliver m, send (ack), close
3. DN ( ack ) is lost
4. NCP A timeout, send (
data, m)
5. NCP B receive (data, m),
deliver m, send (ack), close
6. NCP A receive (ack), notify,
close
Но подтверждения представляют не только
возможность дубликатов, они также терпят неудачу, чтобы уберечь против потерь,
как следующий сценарий показывает. Процесс а предлагает два информационных
модуля, m1 и m2, для передачи.
1. NCP A send ( данные,
m1 )
2. NCP B receive (данные,
m1), deliver m1, send (ack), close
3. NCP A timeout, send (
данные, m1 )
4. NCP B receive (данные,
m1), deliver m1, send (ack), close
5. NCP A receive (ack),
notify, close
6. NCP A send ( данные,
m2)
7. DN ( данные, m2 )
is lost
8. NCP A receive (ack)
(step 2), notify, close
Сообщение m1 дублировано как в предыдущем
сценарии, но первое подтверждение было доставлено медленно, а не потеряно,
вызывая потерю более позднего информационного модуля. Медленная доставка не
обнаружена из-за недостатка глобального времени. Проблема надежной связи между
процессами может быть решена более легко, если принято слабое понятие
глобального времени, а именно, существует верхняя граница T задержки передачи
любого сообщения, посланного через сеть. Это называется глобальным предположением
синхронизации, потому что это порождает временное отношение между событиями в
различных узлах (а именно, посылка NCP А и получение NCP B). Получение
сообщений от более ранних сеансов связи может быть предотвращено в этом
протоколе закрытием сеанса связи в NCP А только через 2T после посылки
последнего сообщения.
Cеанс связи с тремя сообщениями. Поскольку протокол с двумя сообщениями теряет
или дублирует информационный модуль, когда подтверждение потеряно или
отсрочено, можно рассматривать добавление третьего сообщения к сеансу связи для
информирования NCP В, что NCP А получил подтверждение. Нормальный сеанс
связи затем состоит из следующих событий.
1. NCP A send (data, m)
2. NCP B receive (data,
m), deliver m, send (ack)
3. NCP A receive (ack),
notify, send (close), close
4. NCP B receive (close),
close
Потеря сообщения (данные, m) вызывает
таймаут в NCP A, когда NCP A повторно передает сообщение. Потеря
сообщения (ack) также вызывает перепередачу (данные, m), но это
не ведет к дублированию, потому что NCP В имеет открытый сеанс связи и
распознает сообщение, которое он уже получил.
К сожалению, протокол может все еще терять и
дублировать информацию. Потому что NCP В должен быть способен закрыться даже,
когда сообщение (close) потеряно, NCP В должен повторно передать (ack)
сообщение, если он не получает никакого сообщения (close). NCP A
отвечает, говоря, что он не имеет никакого сеанса связи ( сообщение (nocon)),
после которого NCP В закрывается. Перепередача (ack) может прибывать,
однако, в следующем сеансе связи NCP A и интерпретироваться как
подтверждение в том сеансе связи, вызывая тот факт, что следующий
информационный модуль будет потерян, как в следующем сценарии.
1. NCP A send ( data, m1
)
2. NCP B receive (data,
m1), deliver m1, send (ack)
3. NCP A receive (ack),
notify, send (close), close
4. DN ( close ) is lost
5. NCP A send ( data, m2
)
6. DN ( data, m2) is lost
7. NCP B retransmit (ack)
(step 2)
8. NCP A receive (ack),
notify, send (close), close
9. NCP B receive (close),
close
Снова проблема возникла, потому что сообщения
одного сеанса связи сталкивались с другим сеансом связи. Это может быть
исключено выбором пары новых чисел идентификации сеанса связи для каждого
нового сеанса связи, одно для NCP A и одно для NCP B. Выбранные
числа включены во все сообщения сеанса связи, и используются, чтобы проверить,
что полученное сообщение действительно принадлежит текущему сеансу связи.
Нормальный сеанс связи протокола с тремя сообщениями следующий.
1. NCP A send ( data, m,
x)
2. NCP B receive (
data, m, x), deliver m, send ( ack, x, у )
3. NCP A receive (ack, x,
y), notify, send (close, x, y), close
4. NCP B receive ( close,
x, y ), close
Эта модификация протокола с тремя сообщениями
исключает ошибочный сеанс связи, данный ранее, потому что сообщение, полученное
NCP A в шаге 8 не принято как подтверждение для сообщения данных,
посланного в шаге 5. Однако, NCP B не проверяет проверку правильности (данные,
m, x) перед доставкой m (в шаге 2), что легко ведет к дублированию информации.
Если сообщение, посланное в шаге 1 отсрочено и перетранслировано, позже
прибывающее сообщение (данные, m, x) заставляет NCP B доставлять информацию
m снова. Конечно, NCP B должен также проверять правильность сообщений, которые
он получает, перед доставкой данных. Мы рассматриваем модификацию сеанса связи
с тремя сообщениями, в котором NCP B доставляет данные в шаге 4, a не в шаге 2.
Уведомление теперь передается от NCP A перед доставкой от NCP B,
но потому что NCP B уже получил информацию, это кажется оправданным. Должно
быть обеспечено, тем не менее, что NCP B теперь доставит данные в любом случае;
в частности когда сообщение (close, x, y) потеряно. NCP B повторяет сообщение
(ack, x, y) , на которое NCP А отвечает с сообщением (nocon, x, y) , заставляя
NCP B доставить и закрыться, как в следующем сценарии.
1. NCP A send (data,m,x)
2. NCP B receive ( data, m,
x ), send ( ack, x, y )
3. NCP A receive (ack,x,y),
notify, send (close, x, y), close
4. DN ( close, x, y )
is lost
5. NCP B timeout, retransmit ( ack,
x, y )
6. NCP A receive (ack, x,
y), reply (nocon, x, y)
7. NCP B receive (nocon,
x, y), deliver m, close
Оказалось, чтобы избегать потери информации NCP B
должен доставлять данные, даже если NCP А не подтверждает, что имеет
подключение с идентификаторами x и y. Это делает механизм проверки правильности
бесполезным для NCP B, ведя к возможности дублирования информации как в
следующем сценарии.
1. NCP A send (data, m, x
)
2. NCP A timeout, retransmit (
data, m, x)
3. NCP B receive ( data, m, a:)
(sent in step 2), send (ack, x,y1 )
4. NCP A receive ( ack, x,
y1 ), notify, send { close, x, y1 ), close
5. NCP B receive (close, x,
yi ), deliver m, close
6. NCP B receive (data, m,
x ) (sent in step 1), send ( ack, x, у2)
7. NCP A receive ( ack, x,
y2), reply { nocon, x, y2)
8. NCP B receive ( nocon,
x,y2) in reply to ( ack, x, y2 ), deliver m, close
Сеанс связи с четырьмя сообщениями. Доставки информации из старых сеансов связи
можно избегать при наличии NCPs, взаимно согласующих их числа идентификации
сеанса связи прежде, чем любые данные будут поставлены, как в следующем сеансе
связи.
1. NCP A send ( data, m, x )
2. NCP B receive ( data, m, x
), send ( open, x, у )
3. NCP A receive ( open, x, у
), send ( agree, x, у )
4. NCP B receive (agree, x,
y), deliver m, send (ack, x, y), close
5. NCP A receive (ack, x, y),
notify, close
Возможность аварийного отказа NCP В вынуждает
обработку ошибок быть такой, что дубликат может все еще происходить, даже,
когда никакой NCP фактически не терпит крах. Сообщение об ошибках (nocon, x, y)
послано NCP В когда сообщение (agree, x, y) получено, и никакой сеанс связи не
открыт. Предположим, что NCP A не получает сообщение (ack, x, y), даже после
несколько перепередач {agree, x, y) ; только сообщения (nocon, x, y) получены.
Так как возможно, что NCP В потерпел крах прежде, чем он получил (agree, x, y),
NCP вынужден запустить новый сеанс связи (посылая {data, m, x}) чтобы
предотвратить потерю m! Но также возможно, что NCP В уже доставил m, и
сообщение (ack, x, y) было потеряно, тогда появляется дубликат. Возможно
изменить протокол таким образом, что NCP A уведомляет и закрывается после
получения сообщения {nocon, x, y); это предотвращает дубликаты, но может
представлять потерю, которая рассматривается даже менее желательной.
Сеанс связи c пятью сообщениями и сравнение. Beisnes [Bel76] дает протокол с пятью сообщениями,
который не теряет информацию, и это представляет дубликаты только, если NCP
фактически терпит крах. Следовательно, это - самый лучший возможный протокол,
рассматриваемый в свете того наблюдения, что никакая надежная связь не является
возможной, ранее в этом подразделе. Из-за чрезмерных накладных расходов (пять
сообщений проходят через NCPs, чтобы передать один информационный модуль),
должно быть подвергнуто сомнению, должен ли протокол с пятью сообщениями
действительно быть предпочтен намного более простому протоколу с двумя
сообщениями. Действительно, потому что даже протокол с пятью сообщениями может
представлять дубликаты (когда сбоят NCP), уровень процесса должны иметь дело с
ними так или иначе. Так получается, что протокол c двумя сообщениями, который
может представлять дубликаты, но может быть сделан свободным от потерь, если
идентификации сеанса связи добавлены, как мы делали для протокола с тремя
сообщениями, можем также использоваться.
1.3.3 Область
исследования
Имелось продолжающееся исследование в
распределенных алгоритмах в течение последнего двух десятилетий, и значительный
прогресс был сделаны особенно в течение 80-x. В предыдущих разделах мы указали
на некоторые технические достижения, которые стимулировали исследование в
распределенных алгоритмах, а именно, разработка компьютерных сетей (и
глобальных и локальных) и многопроцессорные компьютеры. Первоначально
исследование было очень нацелено к прикладному применению алгоритмов в
глобальных сетях, но в настоящее время разработаны четкие математические
модели, позволяющие прикладное применение результатов и методов к более широким
классам распределенных сред. Однако, исследование поддерживает плотные связи с
достижениями техники в методах связи, потому что результаты в алгоритмах часто
чувствительны к изменениям в сетевой модели. Например, доступность дешевых микропроцессоров
сделала возможным создать системы с многими идентичными процессорами, которые
стимулировали изучение " анонимных сети " (см. Главу 9).
Имеются несколько журналов и ежегодных
конференций, которые специализируются на результатах распределенных алгоритмов
и распределенных вычислений. Некоторые другие журналы и конференции не
специализируются исключительно по этому предмету, но тем не менее содержат
много публикаций в этой области. Ежегодный симпозиум по Принципам
распределенного вычисления (PoDC) организовывался каждый год начиная с 1982 до
времени записи в Северной Америке, и слушания изданы Ассоциацией для Вычисления
Машин. Международные Симпозиумы по распределенным алгоритмам (WDAG) были проведены
в Оттаве (1985), Амстердаме (1987), Ницце (1989), Bari (1990), Delphi (1991),
Хайфе (1992), Lausanne (1993), и Terschelling (1994). С 1989, симпозиумы
проводились ежегодно и слушания были изданы Springer-Verlag в сериях Примечания
по лекциям по информатике. Ежегодные симпозиумы на теории вычисления (SToC) и
основ информатики (FoCS) покрывают все фундаментальные области информатики, и
часто несут статьи об распределенном вычислении. Слушания SToC встреч изданы
Ассоциацией для Вычисления Машин, и таковых FoCS встреч институтом IEEE. Журнал
Параллельного и Распределенного Вычисления (JPDC) и Распределенного Вычисления
издает распределенные алгоритмы регулярно, и делает Письма по обработке информации
(IPL).
1.3.4 Иерархическая
структура книги
Эта книга была написана со следующими тремя
целями в памяти.
(1) Сделать читателя знакомым с методами, которые
могут использоваться, чтобы исследовать свойства данного распределенного
алгоритма, анализировать и решать проблему которая возникает в контексте
распределенных систем, или оценивать качества специфической сетевой модели.
(2) чтобы обеспечить понимание в свойственных
возможностях и невозможности нескольких моделей системы. Воздействие
доступности глобального кадра времени изучается в Разделе 3.2 и в Главах 11 и
14. Воздействие знания процессами их идентичности изучается в Главе 9.
Воздействие требования завершения процесса изучается в Главе 8. Воздействие
сбоев процесса изучается в части 3.
(3) Представлять совокупность недавнего
современного состояния распределенных алгоритмов, вместе с их проверкой и
анализом их сложности.
Где предмет не может обрабатываться в полных
подробностях, ссылки к релевантной научной литературе даны. Материал, собранный
в книге разделен в три части: Протоколы, Фундаментальные Алгоритмы, и
Отказоустойчивость.
Часть 1: Протоколы. Эта часть имеет дело с протоколами связи, используемыми
в реализации компьютерных сетей связи и также представляет методы, используемые
в более поздних частях. В Главе 2 модель, которая будет использоваться в
большинстве более поздних глав, представляется. Модель является, и достаточно
общей, чтобы быть подходящей для разработки и проверки алгоритмов и достаточно
плотной для доказательства результатов невозможности. Это основано на понятии
систем перехода, для которых правила доказательства свойств безопасности и
живости могут быть даны легко. Понятие причинной связи как частичного порядока
на событиях вычисления представляется, и определены логические часы.
В Главе 3 проблема передачи сообщения между
двумя узлами рассматривается. Сначала семейство протоколов для обмена пакетами
над одиночной связью обеспечено, и доказательство правильности, по Schoone,
дано. Также, протокол по Fletcher и Watson рассматривается, правильность
которого полагается на правильное использование таймеров. Обработка этого
протокола показывается, как метод проверки может применяться к протоколам,
основанным на использовании таймеров. Глава 4 рассматривает проблему
маршрутизации в компьютерных сетях. Она сначала представляет некоторую общую
теорию относительно маршрутизации и алгоритма Toueg для вычисления
маршрутизации таблиц. Также обрабатываемый - Netchange алгоритм Tajibnapis и
доказательства правильности для этого алгоритма, данного Lamport. Эта глава
заканчивается компактными алгоритмами маршрутизации, включая интервал и
префиксную маршрутизацию. Эти алгоритмы названы компактными алгоритмами маршрутизации,
потому что они требуют только маленького количества памяти в каждом узле сети.
Обсуждение протоколов для компьютерных сетей заканчивается некоторыми
стратегиями для ухода от тупиков с промежуточным накоплением в компьютерных
сетях с коммутацией пакетов в Главе 5. стратегии основаны при определении
свободных от циклов направленных графов на буферах в узлах сети, и показано,
как такой граф может быть создан, используя только скромное количество буферов
в каждом узле.
Часть 2: Фундаментальные Алгоритмы. Эта часть представляет ряд алгоритмических
"строительных блоков", которые используются как процедуры во многих
распределенных прикладных программах, и разрабатывает теорию относительно
вычислительной мощности различных сетевых предложений. Глава 6 определяет
понятие " волновой алгоритм ", который является обобщенной схемой
посещения всех узлов сети. Волновые алгоритмы используются, чтобы распространить
информацию через сеть, синхронизировать узлы, или вычислять функцию, которая
зависит от распространения информации над всеми узлами. Поскольку это соберется
в более поздних главах, много проблем распределенного управления могут быть
решены в соответствии с очень общими алгоритмическими схемами, в которых
волновой алгоритм используется как компонент. Эта глава также определяет
сложность времени распределенных алгоритмов и исследует время и сложность
сообщения ряда распределенных алгоритмов поиска в глубину.
Фундаментальная проблема в распределенных
системах - выбор: Выбор одиночного процесса, который должен запустить
различаемую роль в последующем вычислении. Эта проблема изучается в Главе 7.
Сначала проблема изучается для кольцевых сетей, где показано, что сложность
сообщения проблемы - O (NlogN) сообщений (на кольце N процессоров). Проблема
также изучается для общих сетей, и некоторые конструкции показываются, к
которым алгоритмы выбора могут быть получены из волновых алгоритмов и
алгоритмов обхода. Эта глава также обсуждает алгоритм для конструкции охвата
дерева Gallager и другие.
Вторая фундаментальная проблема - обнаружение
завершения, распознавание (процессами непосредственно) того, что
распределенное вычисление завершено. Эта проблема изучается в Главе 8. Нижняя
граница сложности решения этой проблемы доказана, и несколько алгоритмов
обсуждены подробно. Глава включает некоторые классические алгоритмы
(например., Dijkstra, Feijen, и Van Gasteren и Dijkstra и Scholten) и снова
конструкция дана для получения алгоритмов для этой проблемы из волновых
алгоритмов.
Глава 9 изучает вычислительную мощность систем,
где процессы не различаются уникальными идентификаторами. Как показал Angluin,
что в этом случае много вычислений не могут быть выполнены детерминированным
алгоритмом. Глава представляет вероятностные алгоритмы, и мы исследуем какие проблемы,
могут быть решены этими алгоритмами.
Глава 10 объясняет, как процессы системы могут
вычислять глобальное "изображение", снимок состояния системы. Такой
кадр полезен для определения свойств вычисления, типа того, произошел ли тупик,
или как далеко вычисление прогрессировало.
В Главе 11 эффект доступности понятия
глобального времени будет изучаться. Несколько степеней синхронизма будут
определены, и будет показано, что полностью асинхронные системы могут моделировать
полностью синхронные довольно тривиальными алгоритмами. Таким образом замечено,
что предположения относительно синхронизма не влияют на совокупность функций, которые
являются вычислимыми распределенной системой. Будет впоследствии показываться,
однако, что имеется влияние на сложность связи многих проблем: чем лучше синхронизм
сети, тем ниже сложность алгоритмов для этих проблем.
Часть 3: Отказоустойчивость. В практических распределенных системах
возможность сбоя в компоненте не может игнорироваться, и следовательно важно
изучить, как хорошо алгоритм ведет себя, если компоненты терпят неудачу. Этот
предмет будет обрабатываться в последней части книги; короткое введение в
предмет дано в Главе 12. Отказоустойчивость асинхронных систем изучается в
Главе 13. Результат Fischer и других обеспечен; показывается, что детерминированные
асинхронные алгоритмы не могут справляться с даже очень скромным типом сбоя,
аварийным отказом одиночного процесса. Будет также показано, что с более
слабыми типами неисправностей можно иметь дело, и что некоторые задачи являются
разрешимыми несмотря на сбой типа аварийного отказа. Алгоритмы Bracha и Toueg
будут обеспечены: оказывается, напротив, рандомизированные асинхронные
системы, способны справиться с приемлемо большим количеством сбоев. Таким
образом замечено, что имеет место для надежных систем (см. Главу 9), рандомизированные
алгоритмы предлагают большее количество возможностей чем детерминированные алгоритмы.
В Главе 14 отказоустойчивость синхронных
алгоритмов будет изучаться. Алгоритмы Lamport и другие показали, что детерминированные
синхронные алгоритмы могут допустить нетривиальные сбои. Таким образом
замечено, что, в отличие от случая надежных систем (см Главу 11), синхронные
системы предлагают большее количество возможностей чем асинхронные системы.
Даже большее число неисправностей может допускаться, если процессы способны
"подписаться" на связь к другим процессам. Следовательно, выполнение
синхронизма в ненадежной системе больше усложнено, чем в надежном случае. И
последний раздел Главы 14 будет посвящен этой проблеме.
Другой подход к надежности, а именно через
само-стабилизацию алгоритмов, сопровождается в Главе 15. Алгоритм
стабилизируется, если, независимо от начальной конфигурации, он сходится в
конечном счете к предназначенному поведению. Некоторая теория относительно
стабилизации алгоритмов будет разработана, и ряд алгоритмов стабилизации будет
обеспечен. Эти алгоритмы включают протоколы для нескольких алгоритмов графа
типа вычисления дерева поиска в глубину (как в Разделе 6.4) и вычисления таблиц
маршрутизации (как в Главе 4). Также, стабилизационные алгоритмы для передачи
данных (как в Главе 3) были предложены. Это может означать, что все
компьютерные сети могут быть выполнены, c использованием стабилизационых
алгоритмов.
Приложения. Приложение A объясняет нотацию, используемую в этой книге, чтобы
представить распределенные алгоритмы. Приложение В обеспечивает некоторые
фоновые основы из теории графов и терминологии графов. Книга заканчивается
списком ссылок и индексом терминов.
2 Модель
В изучении
распределенных алгоритмов часто используется несколько различных моделей
распределенной обработки информации. Выбор определенной модели обычно зависит
того какая проблема распределенных вычислений изучается и какой тип алгоритма
или невозможность доказательства представлена. В этой книге, хотя она и
покрывает большой диапазон распределенных алгоритмов и теории о них, сделана
попытка работать с одной, общей моделью, описанной в этой главе насколько это
возможно.
Для того чтобы
признать выводы невозможности (доказательство не существования алгоритма для
определенной задачи), модель должна быть очень точной. Вывод невозможности это
утверждение о всех возможных алгоритмах, разрешенных в системе, отсюда
модель должна быть достаточно точной, чтобы описать релевантные свойства для
всех допускаемых алгоритмов. Кроме того, вычислительная модель это более чем
детальное описание конкретной компьютерной системы или языка программирования.
Существует множество различных компьютерных систем, и мы хотим, чтобы модель
была применима к классу схожих систем, имеющих общие основные свойства,
которые делают их «распределенными». И наконец, модель должна быть приемлемо
компактной, потому что хотелось бы, чтобы в доказательствах учитывались все
аспекты модели. Подводя итог, можно сказать, что модель должна описывать точно
и кратко релевантные аспекты класса компьютерных систем.
Распределенные
вычисления обычно понимаются как набор дискретных событий, где каждое событие
это атомарное изменение в конфигурации (состояния всей системы). В разделе 2.1
это понятие включено в определение систем перехода, приводящих к понятию
достижимых конфигураций и конструктивному определению множества исполнений,
порождаемых алгоритмом. Что делает систему «распределенной»? То, что на каждый
переход влияет, и он в свою очередь оказывает влияние только на часть
конфигурации, в основном на локальное состояние одного процесса. (Или на
локальные состояния подмножества взаимодействующих процессов.)
Разделы 2.2 и
2.3 рассматривают следствия и свойства модели, описанной в разделе 2.1. Раздел
2.2 имеет дело с вопросом о том, как могут быть доказаны желаемые свойства
данного распределенного алгоритма. В разделе 2.3 обсуждается очень важное
понятие, а именно: каузальное отношение между событиями в исполнении. Это
отношение вызывает отношение эквивалентности, определенное на исполнениях; вычисление
это класс эквивалентности, порожденный этим отношением. Определены часы, и
представлены логические часы как первый распределенный алгоритм, обсуждаемый в
этой книге. И наконец, в разделе 2.4 будут обсуждаться дальнейшие допущения и
нотация, не включенные в основную модель.
2.1 Системы перехода и алгоритмы
Система, чьи
состояния изменяются дискретными шагами (переходами или событиями) может быть
обычно удобно описана с помощью понятия системы переходов. В изучении
распределенных алгоритмов это применимо к распределенной системе как целиком,
так и к индивидуальным процессам, которые сотрудничают в рамках алгоритма.
Поэтому системы перехода это очень важное понятие в изучении распределенных
алгоритмов и оно определяется в подразделе 2.1.1.
В
распределенных системах переходы влияют только на часть конфигурации
(системного глобального состояния). Каждая конфигурация сама по себе это
кортеж, и каждое состояние связано с некоторыми компонентами только из этого
кортежа. Компоненты конфигурации включают состояния каждого индивидуального
процесса. Для точного описания конфигураций должны подразделяться различные
виды распределенных систем, в зависимости от типа коммуникаций между
процессами.
Процессы в
распределенной системе сообщаются либо с помощью доступа с разделяемым
переменным либо при помощи передачи сообщений. Мы примем более
ограниченный взгляд и рассмотрим только распределенные системы, где процессы
сообщаются при помощи обмена сообщениями. Распределенные системы, где сообщение
производится посредством разделяемых переменных, будут обсуждаться в главе 15.
Читатель, интересующийся сообщением посредством разделяемых переменных, может
проконсультироваться в поворотной статье Дейкстры [Dij68] или Овицкий и Грайс
[OG76].
Сообщения в
распределенных системах могут передаваться либо синхронно, либо асинхронно.
Основной упор в этой книге делается на алгоритмы для систем, где сообщения
передаются асинхронно. Во многих случаях синхронная передача сообщений может
рассматриваться как специальный случай асинхронной передачи сообщений, как это
было продемонстрировано Чаррон-Бост и др. [CBMT92]. Подраздел 2.1.2 описывает
модель асинхронной передачи сообщений точно; в подразделе 2.1.3 модель
адаптируется к системам, использующим синхронную передачу сообщений. В
подразделе 2.1.4 кратко обсуждается справедливость.
2.1.1 Системы переходов
Система
переходов состоит из множества всех возможных состояний системы, переходов
(«ходов»), которые система совершает в этом множестве, и подмножества
состояний, в которых системе позволено стартовать. Чтобы избежать беспорядка
между состояниями отдельного процесса и состояниями алгоритма целиком
(«глобальных состояний»), последние теперь будут называться конфигурациями.
Определение
2.1 Система переходов есть тройка S = (C, ®, I), где С это множество
конфигураций, ® это бинарное отношение
перехода на C, и I это подмножество С начальных конфигураций.
Отношение
перехода это подмножество С х С. Вместо (g, d) Î ®
будет использоваться более удобная нотация g
® d.
Определение
2.2 Пусть S = (C, ®, I)
это система переходов. Исполнение S это есть максимальная последовательность
E = (g0, g1, g2,…),
где g0 Î I, и для всех i ³ 0, gi
® gi+1.
Терминальная
конфигурация это конфигурация g, для
которой не существует d такой, что g ® d. Нужно помнить, что последовательность E
= (g0, g1, g2,…)
с gi ® gi+1
для всех i максимальна, если она либо бесконечна, либо заканчивается в
терминальной конфигурации.
Определение
2.3 Конфигурация d достижима
из g, нотация g Þ
d, если существует последовательность
g = g0,
g1, g2, …, gk
= d c gi ® gi+1
для всех 0 £ i < k.
Конфигурация d достижима, если
она достижима из начального состояния.
2.1.2 Системы с асинхронной передачей сообщений
Распределенная
система состоит из набора процессов и коммуникационной подсистемы.
Каждый процесс является системой переходов сам по себе с той лишь оговоркой,
что он может взаимодействовать с коммуникационной подсистемой. Чтобы избежать
путаницы между атрибутами распределенной системы как целого и атрибутов
индивидуальных процессов, мы используем следующее соглашение. Термины «переход»
и «конфигурация» используются для атрибутов системы целиком, и (их эквиваленты)
термины «событие» и «состояние» используются для атрибутов процессов. Чтобы
взаимодействовать с коммуникационной системой процесс имеет не только обычные
события (упоминаемые как внутренние события), но также события
отправки и события получения, при которых сообщения воспроизводятся
и потребляются. Пусть M будет множеством возможных сообщений, и
обозначим набор мультимножеств с элементами из M через M(M).
Определение
2.4 Локальный алгоритм процесса есть пятерка (Z, I, ^i, ^s, ^r),
где Z это множество состояний, I это подмножество Z начальных
состояний, ^i это отношение
на Z x Z, и ^s
и ^r это отношения
на Z x M x Z. Бинарное отношение ^
на Z определяется как
c ^ d Û
(c, d) Î ^i Ú $m Î M((c, m, d) Î ^s
È ^r ).
Отношения ^i , ^s , ^r соответствуют переходам
состояния, соотносящихся с внутренними сообщениями, сообщениями отправки и
сообщениями получения, соответственно. Впоследствии мы будем обозначать
процессы через p, q, r, p1, p2 и т.д., и
обозначать множество процессов системы P. Определение 2.4 служит как
теоретическая модель для процессов; конечно, алгоритмы в этой книге не
описываются только перечислением их состояний и событий, но также средствами
удобного псевдокода (см. приложение А). Исполнения процесса есть исполнения
системы переходов (Z, ^, I).
Нас, однако, будут интересовать исполнения системы целиком, и в таком
исполнении исполнения процессов координируются через коммуникационную систему.
Чтобы описать координацию, мы определим распределенную систему как систему переходов,
где множество конфигураций, отношение перехода, и начальные состояния строятся
из соответствующих компонентов процессов.
Определение
2.5 Распределенный алгоритм для набора P = {p1,
…, pN} процессов это набор локальных алгоритмов, одного для
каждого процесса в P.
Поведение
распределенного алгоритма описывается системой переходов, как это объясняется
далее. Конфигурация состоит из состояния каждого процесса и набора сообщений в
процессе передачи; переходы это события процессов, которые влияют не только на
состояние процесса, но также оказывают влияние (или подвергаются таковому) на набор
сообщений; начальные конфигурации это конфигурации, где каждый процесс
находится в начальном состоянии и набор сообщений пуст.
Определение
2.6 Система переходов, порожденная распределенным алгоритмом для
процессов p1, …, pN при асинхронной коммуникации, (где
локальный алгоритм для процесса pi это есть (Z, I, ^i, ^s, ^r)),
это S = (C, ®, I), где
(1) C = {(cP1,
…, cPN, M) : ("p
Î P : cp
Î Zp) и M Î M(M)}.
(2) à = (ÈpÎP àp), где àp это переходы соответствующие
изменениям состояния процесса p; àPi
это множество пар
(cP1,
…, cPi, …, cPN, M1), (cP1,
…, c’Pi, …, cPN, M2),
для которых
выполняется одно из следующих трех условий:
·
(cPi , c’Pi ) Î ^iPi
и M1 = M2;
·
для некоторого m Î
M, (cPi , m, c’Pi ) Î ^sPi
и M2 = M1 È
{m};
·
для некоторого m Î
M, (cPi , m, c’Pi ) Î ^rPi
и M1 = M2 È
{m}.
(3) I = {(cP1,
…, cPN, M) : ("p
Î P : cp
Î Ip) Ù M = Æ}.
Исполнение
распределенного алгоритма это исполнение его, породившее систему переходов. События
исполнения выполняются явно с помощью следующей нотации. Пары (c, d) Î ^ip
называются (возможными) внутренними событиями процесса p, и
тройки в ^sp
и ^rp
называются событиями отправки и событиями получения процесса.
·
Внутреннее событие е заданное как е = (c, d) процесса
p называется применимым в конфигурации g = (cP1, …, cP, …, cPN,
M), если cp = c. В этом случае, e(g) определяется как конфигурация (cP1,
…, d, …, cPN, M).
·
Событие отправки e, заданное как e = (c, m, d)
процесса p называется применимым в конфигурации g = (cP1, …, cP,
…, cPN, M), если cp = c. В этом случае,
e(g) определяется как
конфигурация (cP1, …, d, …, cPN, M È {m}).
·
Событие получения e, заданное как e = (c, m, d)
процесса p называется применимым в конфигурации g = (cP1, …, cP,
…, cPN, M), если cp = c и m Î M. В этом случае, e(g) определяется как конфигурация (cP1,
…, d, …, cPN, M \ {m}).
Предполагается,
что для каждого сообщения существует уникальный процесс, который может получить
сообщение. Этот процесс называется назначением сообщения.
2.1.3 Системы с синхронной передачей сообщений
Говорят, что
передача сообщений синхронная, если событие отправки и соответствующее событие
получения скоординированы так, чтобы сформировать отдельный переход системы. То
есть, процессу не разрешается посылать сообщение, если назначение сообщения не
готово принять сообщение. Следовательно, переходы системы делятся на два типа:
одни соответствуют изменениям внутренних состояний, другие соответствуют
скомбинированным коммуникационным событиям двух процессов.
Определение
2.7 Система переходов, порожденная распределенным алгоритмом для
процессов p1, …, pN при синхронной коммуникации, это S
= (C, ®, I), где
(1) C = {(cP1,
…, cPN) : "p Î P : cp Î Zp}.
(2) à = (ÈpÎP àp) È
(Èp,qÎP:p¹q àpq),
где
·
àPi
это множество пар
(cP1,
…, cPi, …, cPN), (cP1, …,
c’Pi, …, cPN),
для которых (cPi
, c’Pi ) Î
^iPi ;
·
àPiPj
это множество пар
(…, cPi,
…, cPj , …), (…, c’Pi, …, c’Pj
, …),
для которых существует
сообщение m Î M такое, что
(cPi
, m, c’Pi ) Î
^sPi и
(cPj , m, c’Pj ) Î ^rPj
.
(3) I = {(cP1,
…, cPN) : ("p Î P : cp Î Ip)}.
Некоторые
распределенные системы допускают гибридные формы коммуникации; процессы в них
имеют коммуникационные примитивы для передачи сообщений как в синхронном так и
в асинхронном стиле. Имея две модели, определенные выше, нетрудно разработать
формальную модель для этого типа распределенных систем. Конфигурации такой
системы включают состояния процессов и набор сообщений в процессе передачи (а
именно, асинхронных сообщений). Переходы включают все типы переходов представленных
в определениях 2.6 и 2.7.
Синхронизм и
его влияние на алгоритмы. Уже было замечено, что во многих случаях
синхронная передача сообщений может рассматриваться как специальный случай
асинхронной передачи сообщений. Набор исполнений ограничен в случае синхронной
передачи сообщений исполнениями, где за каждым событием отправки немедленно
следует соответствующее событие приема [CBMT92]. Мы поэтому рассматриваем
асинхронную передачу сообщений как более общую модель, и будем разрабатывать
алгоритмы в основном для этого общего случая.
Однако, нужно
быть внимательным, когда алгоритм, разработанный для асинхронной передачи сообщений
исполняется в системе с синхронной передачей сообщений. Пониженный
недетерминизм в коммуникационной системе должен быть сбалансирован повышенным
недетерминизмом в процессах, в противном случае результатом всего этого может
стать тупик.
Мы
проиллюстрируем это элементарным примером, в котором два процесса посылают друг
другу некоторую информацию. В асинхронном случае, каждый процесс может сначала
послать сообщение и впоследствии получает сообщение от другого процесса.
Сообщения временно накапливаются в коммуникационной подсистеме между их
отправкой и посылкой. В синхронном случае, такого накапливания невозможно, и
если оба процесса должны послать их собственные сообщения перед тем как они
могут получить сообщение, то никакой передачи вообще не будет. В синхронном
случае, один из процессов должен получить сообщение перед тем как другой
процесс отправит свое собственное сообщение. Нет нужды говорить, что, если оба
процесса должны получить сообщение перед отправкой их собственных сообщений,
опять же не будет никакой передачи.
Обмен двумя
сообщениями будет иметь место в синхронном случае, только если одно из двух нижеследующих
условий выполняется.
(1) Заранее
определено, какой из двух процессов будет отправлять первым, и какой процесс
будет первым получать. Во многих случаях невозможно сделать такой выбор
заранее, потому что это потребует выполнения различных локальных алгоритмов в
процессах.
(2) Процессы
имеют право недетерминированного выбора либо отправлять сначала, потом принимать,
либо получать сначала, потом – посылать. В каждом исполнении один из возможных
порядков исполнения будет выбран для каждого процесса, т.е. симметрия
нарушается коммуникационной системой.
Когда мы
представляем алгоритм для асинхронной передачи сообщений и утверждаем, что
алгоритм может также использоваться при синхронной передаче сообщений,
добавление этого недетерминизма, который всегда возможен, предполагается
неявно.
2.1.4 Справедливость
В некоторых
случаях необходимо ограничить поведение системы так называемыми справедливыми
исполнениями. Условия справедливости вводят исполнения, где события всегда (или
бесконечно часто) применимы, но никогда не встречаются как переход (потому что
исполнение продолжается с помощью других применимых событий).
Определение
2.8 Исполнение справедливо в слабом смысле, если нет события применимого
в бесконечно многих последовательных конфигурациях без появления в исполнении.
Исполнение справедливо в сильном смысле, если нет события применимого в
бесконечно многих конфигурациях без появления в исполнении.
Возможно
включить условия справедливости в формальную модель явно, как это сделано Манна
и Пнули [MP88]. Большинство алгоритмов, с которыми мы имеем дело в этой книге,
не полагаются на эти условия; поэтому мы решили не включать их в модель, а
устанавливать эти условия явно, когда они используются для конкретного
алгоритма или проблемы. Также, существует спор, приемлемо ли включать
предположение справедливости в модели распределенных систем. Было выдвинуто
утверждение, что предположение справедливости не должны производиться, более
того алгоритмы не должны разрабатываться с учетом этих предположений.
Дискуссия по некоторым запутанным вопросам, относящимся к предположению
справедливости может быть найдена в [Fra86].
2.2 Доказательство свойств систем перехода
Рассматривая
распределенный алгоритм для некоторой проблемы, необходимо продемонстрировать,
что алгоритм есть корректное решение этой проблемы. Проблема указывает, какие
свойства требуемый алгоритм должен иметь; должно быть показано, что решение
обладает этими свойства. Вопрос проверки распределенных алгоритмов получил
значительное внимание и есть большое количество статей, обсуждающих формальные
методы проверки; см. [CM88, Fra86, Kel76, MP88]. В этом разделе обсуждаются
некоторые простые, но часто используемые методы для демонстрации правильности
распределенных алгоритмов. Эти методы полагаются только на определение системы
переходов.
Многие из
требуемых свойств распределенных алгоритмов попадают в один из двух типов:
требования безопасности и требования живости. Требования безопасности
накладывают ограничение, что определенное свойство должно выполняться для
каждого исполнения системы в каждой конфигурации, достигаемой в этом исполнении.
Требования живости определяют, что определенное свойство должно выполняться для
каждого исполнения системы в некоторых конфигурациях, достигаемых в этом
исполнении. Эти требования могут также встречаться в ослабленной форме,
например, они могут удовлетворяться с некоторой фиксированной вероятностью над
множеством возможных исполнений. Другие требования к алгоритмам могут включать
ограничения, которые основываются только на использовании некоторого данного
знания (см. подраздел 2.4.4), что они гибки по отношен ию к нарушениям в
некоторых процессах (см. часть 3), что процессы равны (см. главу 9), и т.д.
Методы
проверки, описанные в этом разделе, базируются на истинности утверждений
в конфигурациях, достигаемых в исполнении. Такие методы называются методами
проверки утверждений. Утверждение это унарное отношение на множестве
конфигураций, то есть, предикат, который принимает значение истина на одном
подмножестве конфигураций и ложь – на другом.
2.2.1 Свойства безопасности
Свойство
безопасности алгоритма это свойство в форме «Утверждение P истина в
каждой конфигурации каждого исполнения алгоритма». Неформально это
формулируется как «Утверждение Р всегда истина». Основной метод для того,
чтобы показать, что утверждение Р всегда истина, это продемонстрировать,
что Р инвариант согласно следующим определениям. Нотация P(g), где g
это конфигурация, есть булево выражение, чье значение истина, если Р
выполняется в g, и ложь в противном
случае.
Определения
зависят от данной системы переходов S = (C, à, I). Далее, мы будем писать {P} à {Q}, чтобы обозначить, что
для каждого перехода g à d
(системы S), если Р(g) то
Q(d). Таким образом {P} à {Q} означает, что, если Р
выполняется перед любым переходом, то Q выполняется после этого
перехода.
Определение
2.9 Утверждение Р инвариант системы S, если
(1) для
всех g Î I, и
(2) {P}
à {P}.
Определение
говорит, что инвариант выполняется в каждой начальной конфигурации, и
сохраняется при каждом переходе. Из этого следует, что он сохраняется в каждой
достигаемой конфигурации, как и формулируется в следующем теореме.
Теорема 2.10
Если Р это инвариант системы S, то Р выполняется для каждой конфигурации
каждого исполнения системы S.
Доказательство.
Пусть Е = (g0, g1, g2,
...) исполнение системы S. Будет показано по индукции, что Р(gi) выполняется для каждого i.
Во-первых, Р(g0) выполняется,
потому что g0 Î I и по первому предложению
определения 2.9. Во-вторых, предположим P(gi
) выполняется и gi à gi+1
есть переход, который встречается в E. По второму предложению определения 2.9
P(gi+1) выполняется, что и
завершает доказательство.
И наоборот,
утверждение, которое выполняется в каждой конфигурации каждого исполнения, есть
инвариант (см. упражнение 2.2). Отсюда не каждое свойство безопасности может
быть доказано применением теоремы 2.10. В этом случае, однако, каждое
утверждение, которое всегда истинно, включено в инвариант; отсюда может быть
показано, применением следующей теоремы, что утверждение всегда истинно. (Нужно
помнить, однако, что часто очень трудно найти подходящий инвариант Q, к
которому можно применить теорему.)
Теорема 2.11
Пусть Q будет инвариантом системы S и положим Q Þ P (для каждого g Î
С). Тогда Р выполняется в каждой конфигурации каждого исполнения системы S.
Доказательство.
По теореме 2.10, Q выполняется в каждой конфигурации, и так как Q включает P,
то P выполняется в каждой конфигурации также.
Иногда полезно
доказать сначала слабый инвариант, и впоследствии использовать его для
доказательства более сильного инварианта. Как можно сделать инвариант более
сильным демонстрируется в следующем определении и теореме.
Определение
2.12 Пусть S будет системой переходов и P, Q будут утверждениями. Р
называется Q-производным, если
(1) для
всех g Î I, Q(g) Þ Р(g); и
(2) {Q
Ù Р} à {Q Þ Р}.
Теорема 2.13 Если Q есть инвариант и Р
– Q-производное, то Q Ù P есть
инвариант.
Доказательство.
Согласно определению 2.9, должно быть показано, что
(1) для
всех g Î
I, Q(g) Ù
Р(g); и
(2) {Q Ù Р} à
{Q Ù Р}.
Т.к. Q это
инвариант, Q(g) выполняется для всех g Î
I, и т.к. для всех g Î I, Q(g) Þ Р(g), P(g)
выполняется для всех g Î I. Следовательно, Q(g) Ù
P(g) выполняется для всех g Î
I.
Предположим g à
d и Q(g)
Ù Р(g). Т.к. Q это инвариант, Q(d)
выполняется, и т.к. {Q Ù
P} à {Q Þ Р}, Q(d) Þ Р(d), откуда Р(d) вытекает. Следовательно, Q(d) Ù
Р(d) выполняется.
Примеры
доказательства безопасности, основывающиеся на материале данного раздела,
представлены в разделе 3.1.
2.2.2 Свойства живости
Свойство
живости алгоритма это свойство в форме «Утверждение Р истина в некоторой
конфигурации каждого исполнения алгоритма». Неформально это формулируется как
«Утверждение Р в конечном счете истина». Основные методы, используемые, чтобы
показать, что Р в конце концов истина – это нормирующие функции и беступиковость
(или правильное завершение). Более простой метод может быть использован
для алгоритмов, в которых разрешаются только исполнения с фиксированной,
конечной длиной.
Пусть S будет системой переходов и Р – предикат. Определим term как предикат, который истина во всех терминальных
конфигурациях и ложь во всех нетерминальных конфигурациях. Мы сначала предположим
ситуации, где исполнение достигает терминальной конфигурации. Обычно
нежелательно, чтобы такая конфигурация достигалась, в то время, как «цель» Р не
была достигнута. Говорят, что в этом случае имеет место тупик. С другой
стороны, завершение позволено, если цель была достигнута, в этом случае говорят
о правильном завершении.
Определение
2.14 Система S завершается правильно (или
без тупиков), если предикат (term Þ Р) всегда истинен в системе S.
Нормирующие
функции полагаются га математическое понятие обоснованных множеств. Это
множество с порядком <, где нет бесконечных
убывающих последовательностей.
Определение
2.15 Частичный порядок (W, <) является обоснованным, если в нем нет бесконечной
убывающей последовательности
w1 > w2 > w3 ... .
Примеры
обоснованных множеств, которые будут использоваться в этой книге – это
натуральные числа с обычным порядком, и n-кортежи
натуральных чисел с лексикографическим порядком (см. раздел 4.3). Свойство, что
обоснованное множество не имеет бесконечной убывающей последовательности, может
использоваться, чтобы показать, что утверждение Р в конечном счете истина. К
этому моменту должно быть показано, что существует функция f
из C в обоснованное множество W такая,
что в каждом переходе значение f убывает или Р
становится истиной.
Определение
2.16 Пусть даны система переходов S и
утверждение Р. Функция f из С в обоснованное
множество W называется нормирующей функцией (по
отношению к Р), если для каждого перехода g
à d , f(g) > f(d) или Р(d).
Теорема 2.17
Пусть даны система переходов S и
утверждение Р. Если S завершается правильно и
нормирующая функция f (w.r.t
Р) существует, то Р – истина в некоторой конфигурации каждого
исполнения системы S.
Доказательство.
Пусть Е = (g0, g1, g3,
...) – исполнение системы S. Если Е конечно, его
последняя конфигурация является терминальной, и т.к. term Þ Р всегда
истина в системе S, то Р выполняется в этой конфигурации.
Если Е бесконечно, пусть E’ будет самым длинным
префиксом Е, который не содержит конфигураций, в которых Р истина, и пусть s будет последовательностью (f(g0 ), f(g1), ...) для всех конфигураций gi,
которые появляются в Е’. В зависимости от выбора Е’ и свойства f, s может
быть убывающей последовательностью, и отсюда, по обоснованности W, s конечна. Это подразумевает
также, что Е’ – конечный префикс (g0, g1,
..., gk ) исполнения Е. В
зависимости от выбора Е’, Р(gk+1) выполняется.
Если приняты
свойства справедливости, то можно заключить из более слабых посылок (чем в
теореме 2.17), что Р в конце концов станет истиной. Значение нормирующей
функции не должно уменьшаться при каждом переходе. Предположение
справедливости может быть использовано, чтобы показать, что бесконечные
исполнения содержат переходы определенного типа бесконечно часто. Затем будет
достаточно показать, что f никогда не увеличивается, а
уменьшается с каждым переходом этого типа.
В некоторых
случаях мы будем использовать следующий результат, который есть специальный
случай теоремы 2.17
Теорема 2.18
Если S завершается правильно и есть число К
такое, что каждое исполнение содержит по крайней мере К переходов, то Р истина
в некоторой конфигурации каждого исполнения.
Рис. 2.1 Пример пространственно-временной диаграммы
2.3 Каузальный порядок событий и логические часы
Взгляд на
исполнения как последовательности переходов естественным образом порождает
понятие времени в исполнениях. Говорят, что переход а появляется раньше
перехода b, если a встречается
в последовательности перед b. Для исполнения Е = (g0, g1,
...) определим ассоциированную последовательность событий Е’=(е0,
е1, ...), где еi – это событие, при котором конфигурация
изменяется из gi в gi+1. Заметьте, что каждое
исполнение определяет уникальную последовательность событий этим путем.
Исполнение может быть визуализировано в пространственно-временной
диаграмме, рисунок 2.1, которой, представляет пример. В такой диаграмме,
горизонтальная линия нарисована для каждого процесса, и каждое событие нарисовано
точкой на линии процесса, где оно имеет место. Если сообщение m послано при
событии s и получено при событии r, стрелка рисуется от
s к r. Говорят, что события s и r соответственные в этом случае.
Как мы увидим в
подразделе 2.3.1, события распределенного исполнения могут иногда быть взаимно
обменены без воздействия на последующие конфигурации исполнения. Поэтому
понятие времени как абсолютного порядка на событиях исполнения не приемлемо для
распределенных исполнений, и вместо этого представляется понятие каузальной
зависимости. Эквивалентность исполнений при переупорядочивании событий
изучается в подразделе 2.3.2. Мы обсуждаем в подразделе 2.3.3 как могут быть
определены часы для измерения каузальной зависимости (а не времени), и
представляем логические часы Лампорта, важный пример таких часов.
2.3.1 Независимость и зависимость событий
Уже было
замечено, что переходы распределенной системы влияют, и подвержены влиянию,
только на часть конфигураций. Это ведет к тому наблюдению, что два
последовательных события, влияя на разделенные части конфигурации, независимы и
могут также появляться в обратном порядке. Для систем с асинхронной передачей
сообщений, это выражается в следующей теореме.
Теорема 2.19
Пусть g будет
конфигурацией распределенной системы (с асинхронной передачей сообщений) и
пусть ер и еq будут событиями различных процессов р и q, применимых в g.
Тогда ер применимо в еq(g), еq применимо в ер(g), и ер(еq(g)) = еq(ер(g)).
Доказательство.
Чтобы избежать анализа случаев, которые есть посылка, получение, или внутренние
события, мы представим каждое событие однородной нотацией (с, х, у, d). Здесь с и d обозначают состояние процесса до и после
события, х – набор сообщений, полученных во время события, и у – набор сообщений,
посланных во течение события. Таким образом, внутренне событие (с, d)
обозначается как (c,Æ,Æ,d), событие отправки (с, m, d)
обозначается как (с, Æ, {m}, d), и событие приема (с, m, d) – (c, {m}, Æ, d). В этой
нотации, событие е = (с, x, y, d) процесса p применимо
в конфигурации g = (Сp1, ..., Cp, ..., СрN, M), если ср = с и x Í M. В этом
случае
е(g) = (Сp1, ..., d, ..., (M \ x) È у).
Теперь
предположим ер = (bp, xр, ур, dp)
и еq = (bq, xq, уq, dq)
применимы в
g
= (..., ср, ..., сq, ..., M),
то есть ср = bp, cq = bq, xp
Í M, и xq Í M. Важное наблюдение состоит в том,
что хр и xq разделены, сообщение в xp (если
есть такое) имеет назначением р, в то время как сообщение в хq (если
есть такое) имеет назначением q.
Запишем gр = ер(g), и запомним что
gр = (..., dp,
..., cq, ..., (M \ xp ) È ур ).
Так как xq
Í M и xq Ç хр = Æ, следует, что хq Í (M \ xp È ур ), и отсюда еq
применимо в gр. Запишем gpq = eq(gр), и
запомним, что
gрq
= (..., dp, ..., dq, ..., ((M \ xp
È ур ) \ xq ) È
уq ).
С помощью
симметричного аргумента может быть показано, что ер применимо в gq = eq(g). Запишем gqp
= ep(gq), и запомним, что
gqp =
(..., dp, ..., dq, ..., ((M \ xq
È уq ) \ xp ) È
уp ).
Так как M – мультимножество сообщений, xp
Í M, и xq Í M,
((M \ xp È
ур ) \ хq È
уq ) = ((M \ xq È уq ) \ xp
È ур ),
и отсюда gpq = gqp .
Пусть ер
и еq будут двумя событиями, которые появляются последовательно в
исполнении, т.е. исполнение содержит подпоследовательность
...,
g, ер(g), еq(ер(g)), ...
для некоторых g. Посылка теоремы 2.19
применима к этим событиям за исключением следующих двух случаев.
(1) p = q; или
(2) ер
– событие отправки, и еq - соответствующее событие получения.
В самом деле,
теорема явно утверждает, что p и q должны
быть различными, и если еq получает сообщение, посланное в ер,
событие отправки не применимо в начальной конфигурации события ep, как требуется. Таким образом, если одно из
этих двух утверждений истина, события не могут появляться в обратном порядке,
иначе они могут встречаться в обратном порядке и кроме того иметь результат в
одной конфигурации. Запомните, что с глобальной точки зрения переходы не могут
быть обменены, потому что (в нотации теоремы 2.19) переход из gр в gpq отличается от перехода из g в gq.
Однако, с точки зрения процесса эти события неразличимы.
Тот факт, что
конкретная пара событий не может быть обменена, выражается тем, что существует каузальное
отношение между этими двумя событиями. Это отношение может быть расширено
до частичного порядка на множестве событий в исполнении, называемого каузальный
порядок исполнения.
Определение
2.20 Пусть Е – исполнение. Отношение í, называемое каузальным порядком, на событиях исполнения
есть самое малое отношение, которое удовлетворяет
(1) Если
е и f – различные события одного процесса и е
появляется перед f, то е í f.
(2) Если
s – событие отправки и r
– соответствующее событие получения, то s í r.
(3) Отношение
í транзитивно.
Мы пишем а í= b, чтобы
обозначить (а í b Ú а = b). Так как í=
есть частичный порядок, могут существовать события а и b,
для которых ни а í= b ни b í=
а не выполняется. Говорят такие события конкурирующие, в нотации а || b. На рисунке 2.1, b || f, d || i, и
т.д.
Каузальный
порядок был впервые определен Лампортом [Lam78] и
играет важную роль в рассуждениях, относящихся к распределенным алгоритмам. Определение
í подразумевает существование каузальной
цепочки между каузально связанными событиями. Этим мы подразумеваем, что а í b включает
существование последовательности а = е0 , е1 , ..., ек
= b такой, что каждая пара последовательных событий в
цепочке удовлетворяет либо (1), либо (2) в определении 2.20. Каузальная цепочка
может быть даже выбрана так, что каждая пара, удовлетворяющая (1), есть
последовательная пара событий в процессе, где они встречаются, т.е., нет
событий между ними. На рисунке 2.1 каузальная цепочка между событием а и
событием l есть последовательность а, f,
g, h, j, k, l.
2.3.2 Эквивалентность исполнений:
вычисления
В этом
подразделе показывается, что события исполнения могут быть переупорядочены в
любом порядке, согласующимся с каузальным порядком, без воздействия на
результат исполнения. Это переупорядочивание событий вызывает другую
последовательность конфигураций, но это исполнение будет рассматриваться как
эквивалент исходного исполнения.
Пусть f = (f0 , f1 , f2 ,...) будет
последовательностью событий. Эта последовательность - последовательность
событий относящихся к исполнению F = (d0,
d1, d2, ...), если для каждого i, fi
применимо в di и fi (di)
= di+1. В этом случае F называется включенным исполнением последовательности
f. Мы хотели бы, чтобы F уникально
определялась последовательностью f, но это не всегда
так. Если для некоторого процесса p нет события в p, включенного в f, то состояние
процесса p может быть произвольным начальным
состоянием. Однако, если f содержит по крайней мере
одно событие из р, то первое событие в р, скажем (с, х, у, d),
определяет, что начальное состояние процесса р будет с. Поэтому, если f содержит по крайней мере одно событие в каждом процессе, d0 уникально определено, и это
определяет целое исполнение уникально.
Теперь пусть Е
= (g0, g1, g2,
... ) будет исполнением с ассоциированной последовательностью событий Е’ = (е0 , е1 , е2 , ...) и
положим, что f –перестановка из Е’.
Это означает, что существует перестановка s
натуральных чисел (или множества {0, ..., k-1}, если Е – конечное исполнение с
k событиями) таких, что fi = еs(i).
Перестановка (f0 , f1 , f2 ,
...) событий из Е согласующаяся с каузальным порядком, если fi í=
fj подразумевает i £ j,
т.е., если нет события, которому предшествует в последовательности событие,
которому оно само каузально предшествует.
Теорема 2.21
Пусть f = (f0 , f1 , f2
, ...) – перестановка событий из Е, которая согласуется с каузальным
порядком исполнения Е. Тогда f определяет уникальное исполнение F, начинающееся в начальной конфигурации из Е. F имеет столько же событий сколько и Е, и если Е конечно, то
последняя конфигурация из F такая же как и
последняя конфигурация из Е.
Доказательство.
Конфигурации из F строятся одна за другой, и чтобы построить
di+1 достаточно показать,
что fi применимо в di.
Возьмем d0 = g0.
Предположим,
что для всех j < i, fj применимо
в конфигурации dj и dj+1 = fj (dj ).
Пусть di = (cp1 , ..., cpN , M) и пусть fi =(c, x, y, d) будет событие в процессе р, тогда
событие fi применимо в di, если сp
= c и х Í
М.
Чтобы показать,
что сp = c нужно различать два случая. В обоих случаях мы должны
помнить, что каузальный порядок исполнения Е абсолютно упорядочивает
события в процессе р. Это подразумевает, что события в процессе р появляются в
точно таком же порядке и в f и в Е’.
Случай 1:
fi - первое событие в р из f, тогда ср – это начальное состояние р. Но тогда fi – также первое событие в р из Е’, что подразумевает, что с – это начальное состояние р.
Следовательно, с = ср.
Случай 2:
fi – не первое событие в р из f. Пусть последнее событие в р из f перед
fi будет fi' = (c’, x’, y’, d’),
тогда ср = d’. Но тогда fi' также последнее событие в р
перед fi из Е’, что подразумевает, что с = d’.
Следовательно, с = ср.
Чтобы показать,
что х Í М мы должны помнить, что
соответствующие события приема и посылки встречаются в одном порядке и в f и в Е’. Если fi не
событие посылки, то х = Æ и х Í М выполняется тривиально. Если fi – это событие посылки, пусть fi
будет соответствующим событием посылки. Так как fj
í fi
, j < i выполняется, т.е., событие посылки предваряет fi в f, следовательно, х Í М.
Мы сейчас
показали, что для каждого i, fi применимо в di, и di+1 может быть взято как fi(di). Мы должны, наконец, показать, что последние конфигурации
из F и Е совпадают, если Е конечно. Пусть gk будет последней конфигурацией
из Е. Если Е’ не содержит события в р, то состояние р
в gk равно его начальному
состоянию. Так как f также не содержит события в р, то
состояние р в dk также равно
начальному состоянию, отсюда состояние р в dk
равняется его состоянию в gk.
Иначе, состояние р в gk есть
состояние после последнего события в р из Е’. Это также
последнее событие в р из f, так что это также состояние
р в dk.
Сообщения в
процессе передачи в gk есть
такие сообщения, для которых событию посылки нет соответствующего события
получения в Е’. Но так как Е’ и f содержат один и тот же набор событий, те же сообщения в
процессе передачи в последней конфигурации из F.
Рис. 2.2 Пространственно-временная диаграмма эквивалентная рис. 2.1
Исполнения F и Е имеют один набор событий, и каузальный порядок этих
событий – один и тот же для Е и F. Поэтому, также, в
этом случае Е – это перестановка событий из F, которая
согласуется с каузальным порядком исполнения F. Если
применить условие теоремы 2.21, мы можем сказать, что Е и F
– эквивалентные исполнения, что обозначается как E ~ F.
Рис. 2.2
показывает временную диаграмму исполнения, эквивалентного исполнению,
изображенному на рис. 2.1. Эквивалентные временные диаграммы могут быть
получены с помощью «трансформаций резиновой ленты» [Mat89c].
Полагая, что временная ось процесса может быть сжата и растянута пока стрелки
сообщений продолжают указывать направо, рис. 2.1 может быть деформирован до
рис. 2.2.
Хотя
изображенные исполнения эквивалентны и содержат одинаковый набор событий, они
не могут содержать одинаковый набор конфигураций. Рис. 2.1 содержит