Распределенные алгоритмы
| Сдавался/использовался | 2000г. |
| Загрузить архив: | |
| Файл: ref-2049.zip (938kb [zip], Скачиваний: 31) скачать |
TOC t "chap_number;1;chap_name;1;sc;2;ssc;3" Пролог PAGEREF _Toc423280427 h 6
1 Введение: распределенные системы PAGEREF _Toc423280428 h 7
1.1 Что такое распределенная система? PAGEREF _Toc423280429 h 7
1.1.1 Мотивация PAGEREF _Toc423280430 h 8
1.1.2 Компьютерные сети PAGEREF _Toc423280431 h 10
1.1.3 Глобальные сети PAGEREF _Toc423280432 h 11
1.1.4 Локальные сети PAGEREF _Toc423280433 h 13
1.1.5 Многопроцессорные компьютеры PAGEREF _Toc423280434 h 16
1.1.6 Взаимодействующие процессы PAGEREF _Toc423280435 h 19
1.2 Архитектура и Языки PAGEREF _Toc423280436 h 22
1.2.1 Архитектура PAGEREF _Toc423280437 h 22
1.2.2 Ссылочная МодельOSI PAGEREF _Toc423280438 h 24
1.2.3 OSI Модель влокальных сетях: IEEE Стандарты PAGEREF _Toc423280439 h 26
1.2.4 Поддержка Языка PAGEREF _Toc423280440 h 27
1.3 Распределенные Алгоритмы PAGEREF _Toc423280441 h 29
1.3.1 Распределенный против Централизованных Алгоритмов PAGEREF _Toc423280442 h 30
1.3.2 Пример: Связь содиночным сообщением PAGEREF _Toc423280443 h 32
1.3.3 Область исследования PAGEREF _Toc423280444 h 37
1.3.4 Иерархическая структура книги PAGEREF _Toc423280445 h 37
2 Модель PAGEREF _Toc423280446 h 40
2.1 Системы перехода и алгоритмы PAGEREF _Toc423280447 h 41
2.1.1 Системы переходов PAGEREF _Toc423280448 h 42
2.1.2 Системы с асинхронной передачей сообщений PAGEREF _Toc423280449 h 43
2.1.3 Системы с синхронной передачей сообщений PAGEREF _Toc423280450 h 45
2.1.4 Справедливость PAGEREF _Toc423280451 h 47
2.2 Доказательство свойств систем перехода PAGEREF _Toc423280452 h 47
2.2.1 Свойства безопасности PAGEREF _Toc423280453 h 48
2.2.2 Свойства живости PAGEREF _Toc423280454 h 50
2.3 Каузальный порядок событий и логические часы PAGEREF _Toc423280455 h 51
2.3.1 Независимость и зависимость событий PAGEREF _Toc423280456 h 52
2.3.2 Эквивалентность исполнений: вычисления PAGEREF _Toc423280457 h 54
2.3.3 Логические часы PAGEREF _Toc423280458 h 57
2.4 Дополнительные допущения, сложность PAGEREF _Toc423280459 h 60
2.4.2 Свойства каналов PAGEREF _Toc423280460 h 62
2.4.3 Допущения реального времени PAGEREF _Toc423280461 h 64
2.4.4 Знания процессов PAGEREF _Toc423280462 h 64
2.4.5 Сложность распределенных алгоритмов PAGEREF _Toc423280463 h 66
3 Протоколы Связи PAGEREF _Toc423280464 h 66
3.1 Сбалансированный протокол скользящего окна PAGEREF _Toc423280465 h 68
3.1.1 Представление протокола PAGEREF _Toc423280466 h 68
3.1.2 Доказательство правильности протокола PAGEREF _Toc423280467 h 71
3.1.3 Обсуждение протокола PAGEREF _Toc423280468 h 73
3.2 Протокол, основанный на таймере PAGEREF _Toc423280469 h 75
3.2.1 Представление Протокола PAGEREF _Toc423280470 h 78
3.2.2 Доказательство корректности протокола PAGEREF _Toc423280471 h 81
3.2.3 Обсуждение протокола PAGEREF _Toc423280472 h 85
Упражнения к главе 3 PAGEREF _Toc423280473 h 88
Раздел 3.1 PAGEREF _Toc423280474 h 88
Раздел 3.2 PAGEREF _Toc423280475 h 89
4 Алгоритмы маршрутизации PAGEREF _Toc423280476 h 89
4.1 Адресат-основанная маршрутизация PAGEREF _Toc423280477 h 91
4.2 Проблема кротчайших путей всех пар PAGEREF _Toc423280478 h 95
4.2.1 Алгоритм Флойда-Уошала PAGEREF _Toc423280479 h 95
4.2.2 Алгоритм кротчайшего пути.(Toueg) PAGEREF _Toc423280480 h 98
4.2.3 Обсуждение и Дополнительные Алгоритмы PAGEREF _Toc423280481 h 102
4.3 Алгоритм Netchange PAGEREF _Toc423280482 h 106
4.3.1 Описание алгоритма PAGEREF _Toc423280483 h 107
4.3.2 Корректность алгоритма Netchange PAGEREF _Toc423280484 h 112
4.3.3 Обсуждение алгоритма PAGEREF _Toc423280485 h 113
4.4 Маршрутизация с Компактными Таблицами маршрутизации PAGEREF _Toc423280486 h 114
4.4.1 Схема разметки деревьев PAGEREF _Toc423280487 h 115
4.4.2 Интервальная маршрутизация PAGEREF _Toc423280488 h 118
4.4.3 Префиксная маршрутизация PAGEREF _Toc423280489 h 125
4.5 Иерархическая маршрутизация PAGEREF _Toc423280490 h 127
4.5.1 Уменьшение количества решений маршрутизации PAGEREF _Toc423280491 h 128
Упражнения к Части 4 PAGEREF _Toc423280492 h 130
Раздел 4.1 PAGEREF _Toc423280493 h 130
Раздел 4.2 PAGEREF _Toc423280494 h 131
Раздел 4.3 PAGEREF _Toc423280495 h 131
Раздел 4.4 PAGEREF _Toc423280496 h 131
Раздел 4.5 PAGEREF _Toc423280497 h 132
5 Беступиковая коммутация пакетов PAGEREF _Toc423280498 h 132
5.1 Введение PAGEREF _Toc423280499 h 133
5.2 Структурированные решения PAGEREF _Toc423280500 h 134
5.2.1 Буферные Графы PAGEREF _Toc423280501 h 135
5.2.2 Ориентации G PAGEREF _Toc423280502 h 138
5.3 Неструктурированные решения PAGEREF _Toc423280503 h 141
5.3.1 Контроллеры с прямым и обратным счетом PAGEREF _Toc423280504 h 141
5.3.2 Контроллеры с опережающим и отстающим состоянием PAGEREF _Toc423280505 h 142
5.4 Дальнейшие проблемы PAGEREF _Toc423280506 h 144
5.4.1 Топологические изменения PAGEREF _Toc423280507 h 145
5.4.2 Другие виды тупиков PAGEREF _Toc423280508 h 146
5.4.3 Лайфлок (livelock) PAGEREF _Toc423280509 h 147
Упражнения к Главе 5 PAGEREF _Toc423280510 h 149
Раздел 5.1 PAGEREF _Toc423280511 h 149
Раздел 5.2 PAGEREF _Toc423280512 h 149
Раздел 5.3 PAGEREF _Toc423280513 h 149
6 Волновые алгоритмы и алгоритмы обхода PAGEREF _Toc423280514 h 149
6.1Определение и использование волновых алгоритмов PAGEREF _Toc423280515 h 150
6.1.1Определение волновых алгоритмов PAGEREF _Toc423280516 h 151
6.1.2Элементарные результаты о волновых алгоритмах PAGEREF _Toc423280517 h 153
6.1.3Распространение информации с обратной связью PAGEREF _Toc423280518 h 155
6.1.4Синхронизация PAGEREF _Toc423280519 h 156
6.1.5Вычисление функций инфимума PAGEREF _Toc423280520 h 156
6.2Волновые алгоритмы PAGEREF _Toc423280521 h 158
6.2.1Кольцевой алгоритм PAGEREF _Toc423280522 h 158
6.2.2Древовидный алгоритм PAGEREF _Toc423280523 h 159
6.2.3Эхо-алгоритм PAGEREF _Toc423280524 h 161
6.2.4Алгоритм опроса PAGEREF _Toc423280525 h 163
6.2.5Фазовый алгоритм PAGEREF _Toc423280526 h 164
6.2.6Алгоритм Финна PAGEREF _Toc423280527 h 167
6.3Алгоритмы обхода PAGEREF _Toc423280528 h 169
6.3.1Обход клик PAGEREF _Toc423280529 h 170
6.3.2Обход торов PAGEREF _Toc423280530 h 171
6.3.3Обход гиперкубов PAGEREF _Toc423280531 h 172
6.3.4Обход связных сетей PAGEREF _Toc423280532 h 173
6.4Временная сложность: поиск в глубину PAGEREF _Toc423280533 h 175
6.4.1Распределенный поиск в глубину PAGEREF _Toc423280534 h 176
6.4.2 Алгоритмы поиска в глубину за линейное время PAGEREF _Toc423280535 h 177
6.4.3Поиск в глубину со знанием соседей PAGEREF _Toc423280536 h 182
6.5Остальные вопросы PAGEREF _Toc423280537 h 182
6.5.1Обзор волновых алгоритмов PAGEREF _Toc423280538 h 182
6.5.2Вычисление сумм PAGEREF _Toc423280539 h 184
6.5.3Альтернативные определения временной сложности PAGEREF _Toc423280540 h 186
Упражнения кГлаве 6 PAGEREF _Toc423280541 h 188
Раздел 6.1 PAGEREF _Toc423280542 h 188
Раздел 6.2 PAGEREF _Toc423280543 h 189
Раздел 6.3 PAGEREF _Toc423280544 h 190
Раздел 6.4 PAGEREF _Toc423280545 h 190
Раздел 6.5 PAGEREF _Toc423280546 h 190
7Алгоритмы выбора PAGEREF _Toc423280547 h 190
7.1Введение PAGEREF _Toc423280548 h 191
7.1.1Предположения, используемые в этой главе PAGEREF _Toc423280549 h 192
7.1.2Выбор и волны PAGEREF _Toc423280550 h 193
7.2Кольцевые сети PAGEREF _Toc423280551 h 196
7.2.1Алгоритмы ЛеЛанна и Чанга-Робертса PAGEREF _Toc423280552 h 196
7.2.2Алгоритм Petersen / Dolev-Klawe-Rodeh PAGEREF _Toc423280553 h 200
7.2.3Вывод нижней границы PAGEREF _Toc423280554 h 203
7.3 Произвольные Сети PAGEREF _Toc423280555 h 207
7.3.1 Вырождение и Быстрый Алгоритм PAGEREF _Toc423280556 h 208
7.3.2 Алгоритм Gallager-Humblet-Spira PAGEREF _Toc423280557 h 210
7.3.3 Глобальное Описание GHS Алгоритма. PAGEREF _Toc423280558 h 212
7.3.4 Детальное описания GHS алгоритма PAGEREF _Toc423280559 h 215
7.3.5 Обсуждения и Варианты GHS Алгоритма PAGEREF _Toc423280560 h 219
7.4 Алгоритм Korach-Kutten-Moran PAGEREF _Toc423280561 h 220
7.4.1 Модульное Строительство PAGEREF _Toc423280562 h 221
7.4.2 Применения Алгоритма KKM PAGEREF _Toc423280563 h 225
Упражнения кГлаве 7 PAGEREF _Toc423280564 h 225
Раздел 7.1 PAGEREF _Toc423280565 h 225
Раздел 7.2 PAGEREF _Toc423280566 h 226
Раздел 7.3 PAGEREF _Toc423280567 h 226
Раздел 7.4 PAGEREF _Toc423280568 h 226
8 Обнаружение завершения PAGEREF _Toc423280569 h 227
8.1 Предварительные замечания PAGEREF _Toc423280570 h 228
8.1.1 Определения PAGEREF _Toc423280571 h 228
8.1.2 Две нижних границы PAGEREF _Toc423280572 h 231
8.1.3 Завершение Процессов PAGEREF _Toc423280573 h 233
8.2.2 Алгоритм Shavit-Francez PAGEREF _Toc423280574 h 237
8.3 Решения, основанные на волнах PAGEREF _Toc423280575 h 241
8.3.1 Алгоритм Dijkstra-Feijen-Van Gasteren PAGEREF _Toc423280576 h 242
8.3.2 Подсчет Основных Сообщений: Алгоритм Сафра PAGEREF _Toc423280577 h 245
8.3.3 Использование Подтверждений PAGEREF _Toc423280578 h 249
8.3.4 Обнаружение завершения с помощью волн PAGEREF _Toc423280579 h 252
8.4 Другие Решения PAGEREF _Toc423280580 h 254
8.4.1 Алгоритм восстановления кредита PAGEREF _Toc423280581 h 254
8.4.2 Решения, использующие временные пометки PAGEREF _Toc423280582 h 256
Упражнения кГлаве 8 PAGEREF _Toc423280583 h 259
Раздел 8.1 PAGEREF _Toc423280584 h 259
Раздел 8.2 PAGEREF _Toc423280585 h 259
Раздел 8.3 PAGEREF _Toc423280586 h 259
Раздел 8.4 PAGEREF _Toc423280587 h 260
13 Отказоустойчивость в Асинхронных Системах PAGEREF _Toc423280588 h 260
13.1 Невозможность согласия PAGEREF _Toc423280589 h 260
13.1.1 Обозначения, Определения, Элементарные Результаты PAGEREF _Toc423280590 h 260
13.1.2 Доказательство невозможности PAGEREF _Toc423280591 h 262
13.1.3 Обсуждение PAGEREF _Toc423280592 h 264
13.2 Изначально-мертвые Процессы PAGEREF _Toc423280593 h 265
13.3 Детерминированно Достижимые Случаи PAGEREF _Toc423280594 h 268
13.3.1 Разрешимая Проблема: Переименование PAGEREF _Toc423280595 h 269
13.3.2 Расширение Результатов Невозможности PAGEREF _Toc423280596 h 273
13.4 Вероятностные Алгоритмы Согласия PAGEREF _Toc423280597 h 275
13.4.1 Аварийно-устойчивые Протоколы Согласия PAGEREF _Toc423280598 h 276
13.4.2 Византийско-устойчивые Протоколы Согласия PAGEREF _Toc423280599 h 280
13.5 Слабое Завершение PAGEREF _Toc423280600 h 285
Упражнения к Главе 13 PAGEREF _Toc423280601 h 289
Раздел 13.1 PAGEREF _Toc423280602 h 289
Раздел 13.2 PAGEREF _Toc423280603 h 289
Раздел 13.3 PAGEREF _Toc423280604 h 289
Раздел 13.4 PAGEREF _Toc423280605 h 290
Раздел 13.5 PAGEREF _Toc423280606 h 291
14 Отказоустойчивость в Синхронных Системах PAGEREF _Toc423280607 h 291
14.1 Синхронные Протоколы Решения PAGEREF _Toc423280608 h 292
14.1.1 Граница Способности восстановления PAGEREF _Toc423280609 h 293
14.1.2 Алгоритм Византийского вещания PAGEREF _Toc423280610 h 295
14.1.3 Полиномиальный Алгоритм Вещания PAGEREF _Toc423280611 h 298
14.2 Протоколы с Установлением Подлинности PAGEREF _Toc423280612 h 303
14.2.1 Протокол Высокой Степени Восстановления PAGEREF _Toc423280613 h 304
14.2.2 Реализация Цифровых Подписей PAGEREF _Toc423280614 h 307
14.2.3 Схема Подписи ЭльГамаля PAGEREF _Toc423280615 h 308
14.2.4 Схема Подписи RSA PAGEREF _Toc423280616 h 310
14.2.5 Схема Подписи Фиата-Шамира PAGEREF _Toc423280617 h 310
14.2.6 Резюме и Обсуждение PAGEREF _Toc423280618 h 313
14.3 Синхронизация Часов PAGEREF _Toc423280619 h 315
14.3.1 Чтение Удаленных Часов PAGEREF _Toc423280620 h 316
14.3.2 Распределенная Синхронизация Часов PAGEREF _Toc423280621 h 318
INCLUDETEXT "E:\DISTR\(1-2)Bykov.doc" [AK1] Многие приложения используют одновременное или последовательное распространение нескольких волн; в этом случае в сообщение должна быть включена информация о волне, которой оно принадлежит. Кроме того, процесс может хранить дополнительные переменные для управления волной, или волнами, в которых он в настоящее время активен.
Важный подкласс волновых алгоритмов составляют централизованные волновые алгоритмы, обладающие двумя дополнительными качествами: инициатор является единственным процессом, который принимает решение; и все события совершенно упорядочены каузальными отношениями. Такие волновые алгоритмы называются алгоритмами обхода и рассматриваются в Разделе 6.3.
[1] для данного сообщения одинаково вероятным результатом процедуры подписывания. Таким образом, один и тот же документ, подписанный дважды, почти обязательно произведет две различных действительных подписи. Рандомизация необходима в процедуре подписывания; если p подписывает два сообщения, пользуясь одним и тем же значением a, из подписей можно вычислить секретный ключ p; см. Упражнение 14.6.
[1] - функция Эйлера “фи”; - размер
[AK1]