# Реферат: Распределенные алгоритмы

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

Еще работы по компьютерам и переферийным устройствам