Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно).pdf)
Описание файла
PDF-файл из архива "Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно).pdf", который расположен в категории "". Всё это находится в предмете "распределенные алгоритмы" из 10 семестр (2 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст из PDF
4УДК ????ББК ????Т??ОГЛАВЛЕНИЕT?? Тель Ж.Введение в распределенные алгоритмы. Пер. с англ. / Под ред. Р. Подловченко. — М.: МЦНМО. 2007. — ??? с.: ил.ББК ????Во всемирно известной монографии голландского математика Ж. Теля рассказывается об устройстве и принципах работы распределенных вычислительныхсистем, об алгоритмах решения наиболее важных задач, возникающих при проектировании программного обеспечения распределенных систем.
Большое внимание уделяется методам повышения надежности распределенных систем.Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .12Г л а в а 1. Введение: распределенные системы141.1.1.2.1.3.Издание осуществлено при финансовой поддержкеРоссийского фонда фундаментальных исследований (РФФИ)грант №06-01-141071.4.Что такое распределенная система? . . . .
. . . . . . . . . . . . . . . . . .1.1.1. Мотивировка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.1.2. Вычислительные сети . . . . . . . . . . . . . . . . . . . . . . . . . .1.1.3. Глобальные сети. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .1.1.4. Локальные сети . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.1.5. Многопроцессорные компьютеры . . . . . . . . . . . . . . . . . .1.1.6. Взаимодействующие процессы . . . . . . . . . . . . . . . . . . . .Архитектура и языки. . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .1.2.1. Архитектура . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.2.2. Эталонная модель OSI . . . . . . . . . . . . . . . . . . . . . . . . .1.2.3. Модель OSI для локальных сетей: стандарт IEEE . . . . . . .1.2.4. Языковая поддержка. . . . . . . . . . . . . . . . . . . . . . . . .
. .Распределенные алгоритмы . . . . . . . . . . . . . . . . . . . . . . . . . . .1.3.1. Сравнение распределенных и централизованных алгоритмов .1.3.2. Пример связи с передачей одного сообщения. . . . . . . . . . .1.3.3. Область исследований. . . . . . . . . . . .
. . . . . . . . . . . . . .Обзор содержания книги . . . . . . . . . . . . . . . . . . . . . . . . . . . . .....................................................................Г л а в а 2. МодельISBN 0-521-79483-8 (англ.)ISBN ?-???-?????-? (русск.)1994 Gerard Tel2000 Cambridge University Press, 2nd edition2007 МЦНМО, перевод с англ.Жирар Тель2.1.2.2.Введение в распределенные алгоритмы2.3.Лицензия ИД №????? от ?????Подписано к печати ???????Формат 60×90/16. Бумага офсетная. Печать офсетная.Объем ?? печ. л.
Тираж ???? экз. Заказ.2.4.Издательство Московского центра непрерывного математического образования.121002, Москва, Г-2, Бол. Власьевский пер., 11.Отпечатано с готовых диапозитивов в ?????2.5.Системы переходов и алгоритмы . . . . . . . . . . . . . . . . . . . .2.1.1. Системы переходов . . . . . . . .
. . . . . . . . . . . . . . . .2.1.2. Системы с асинхронным обменом сообщениями . . . . .2.1.3. Системы с синхронным обменом сообщениями. . . . . .2.1.4. Справедливость . . . . . . . . . . . . . . . . . . . . . . . . . .Как обосновывать свойства систем переходов . . . . . . . . . . .2.2.1. Свойства безопасности . . . . . .
. . . . . . . . . . . . . . .2.2.2. Свойства живости . . . . . . . . . . . . . . . . . . . . . . . .Причинно-следственный порядок событий и логические часы .2.3.1. Зависимые и независимые события . . . . . . . . . . . . .2.3.2. Эквивалентность выполнений: вычисления . . . . . . . .2.3.3.
Логические часы . . . . . . . . . . . . . . . . . . . . . . . . .Дополнительные допущения. Сложность. . . . . . . . . . . . . . .2.4.1. Топология сети. . . . . . . . . . . . . . . . . . . . . . . . . . .2.4.2. Свойства каналов . . . . . . . .
. . . . . . . . . . . . . . . . .2.4.3. Допущения реального времени . . . . . . . . . . . . . . . .2.4.4. Осведомленность процессов . . . . . . . . . . . . . . . . . .2.4.5. Сложность распределенных алгоритмов . . . . . . . . . .Упражнения к главе 2 . . . . . . . . . . . . . . .
. . . . . . . . . . . .151517192124273131333637404042484954........................................................................................................................................................555656586061626466676974767779818182846ОглавлениеГ л а в а 3. Коммуникационные протоколы3.1.3.2.3.3.Симметричный протокол раздвижного окна .
. . .3.1.1. Описание протокола . . . . . . . . . . . . . .3.1.2. Доказательство корректности протокола .3.1.3. Обсуждение протокола . . . . . . . . . . . .Протокол с таймерами . . . . . . . . . . . . . . . . .3.2.1. Описание протокола . . . . . . . . . . . . . .3.2.2. Доказательство корректности протокола .3.2.3. Обсуждение протокола . .
. . . . . . . . . .Упражнения к главе 3 . . . . . . . . . . . . . . . . . .86.........................................................................................................................................................Г л а в а 4. Алгоритмы маршрутизации4.1.4.2.4.3.4.4.4.5.4.6.5.3.5.4.5.5.Маршрутизация на основе узлов-адресатов. . . . . . . . . .
. . . . .Задача построения кратчайших путей для всех пар вершин . . . .4.2.1. Алгоритм Флойда—Уоршалла. . . . . . . . . . . . . . . . . . .4.2.2. Алгоритм Туэга построения кратчайших путей . . . . . . . .4.2.3. Другие алгоритмы. . . . . . . . . . . . . . . . . . . . . . . . . . .Алгоритм Netchange . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .4.3.1. Описание алгоритма . . . . . . . . . . . . . . . . . . . . . . . . .4.3.2. Корректность алгоритма Netchange . . . . . . . . . . . . . . .4.3.3. Обсуждение алгоритма . . . . . . . . . . . . . . . . . . . . . . .Маршрутизация с использованием компактных таблиц . . . . . .
.4.4.1. Схема древесной разметки . . . . . . . . . . . . . . . . . . . . .4.4.2. Интервальная маршрутизация. . . . . . . . . . . . . . . . . . .4.4.3. Префиксная маршрутизация . . . . . . . . . . . . . . . . . . . .Иерархическая маршрутизация . . . . . . . . . . . . . . . . .
. . . . . .4.5.1. Сокращение числа узлов, в которых выбирается маршрутУпражнения к главе 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6.1.................................................................................................118123123126132137137143145147148151160164165167........................................................................171173173178182182183186187188189192Волновые алгоритмы и алгоритмы обходаОпределение и применение волновых алгоритмов . . . . .
.6.1.1. Определение волновых алгоритмов . . . . . . . . . .6.1.2. Основные свойства волновых алгоритмов . . . . . .6.1.3. Распространение информации с обратной связью .6.2.6.3.6.4.6.5.6.6.............................................6.1.4. Синхронизация . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .6.1.5. Вычисление функций точной нижней грани . . . . . . . . . . . .Семейство волновых алгоритмов . . . . . . . . . . . . . . . . . . . . . . . .6.2.1. Кольцевой алгоритм . . . . . . . . . . . . . . . . . . . . . . . . .
. .6.2.2. Древесный алгоритм . . . . . . . . . . . . . . . . . . . . . . . . . . .6.2.3. Алгоритм эха. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6.2.4. Алгоритм опроса . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6.2.5. Фазовый алгоритм . . . . . .
. . . . . . . . . . . . . . . . . . . . . .6.2.6. Алгоритм Финна . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Алгоритмы обхода . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6.3.1. Обход клик . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . .6.3.2. Обход торов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6.3.3. Обход гиперкубов. . . . . . . . . . . . . . . . . . . . . . . . . . . . .6.3.4. Обход связных сетей. . . . . . . . . . .
. . . . . . . . . . . . . . . .Сложность по времени: поиск в глубину . . . . . . . . . . . . . . . . . . .6.4.1. Распределенный поиск в глубину. . . . . . . . . . . . . . . . . . .6.4.2. Алгоритмы поиска в глубину, требующие линейного времени6.4.3. Поиск в глубину с учетом сведений о соседях .
. . . . . . . . .Прочие вопросы. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6.5.1. Обзор волновых алгоритмов . . . . . . . . . . . . . . . . . . . . . .6.5.2. Вычисление сумм . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6.5.3. Альтернативные определения сложности по времени . . . . . .Упражнения к главе 6 . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . .............................................................................................Г л а в а 7. Алгоритмы избрания лидера7.1.7.2.170Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Структурированные решения . . . . . . . . . . . . . . .
