Распределенные алгоритмы — страница 3

  • Просмотров 19596
  • Скачиваний 574
  • Размер файла 960
    Кб

Алгоритмы поиска в глубину за линейное время 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 Расширение