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

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

Пролог                                                                                                                             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) оканчивается списком упражнений и маленьких проектов. Проекты обычно требуют, чтобы читатель разработал маленькое, но нетривиальное расширение или практическое решение по материалу главы, и в большинстве случаев у автора нет решения. Если читатель добьется успеха в разработке этих маленьких проектов, то мне бы хотелось иметь копию результата.

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42