Реферат: Распределенные алгоритмы
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<sp