Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата

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

Рекомендуем скачать другие рефераты по теме: педагогические рефераты, реферат машини.





Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата