ПРОЛОГ 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 Пролог
    Распределенные системы и обработка распределенной информации получили значительное внимание в последние несколько лет, и почти каждый университет предлагает, по крайней мере, один курс по разработке распределенных алгоритмов. ............