Пролог 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