Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно).pdf), страница 2
Описание файла
PDF-файл из архива "Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно).pdf", который расположен в категории "". Всё это находится в предмете "распределенные алгоритмы" из 10 семестр (2 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 2 страницы из PDF
. . . . . . . . .5.2.1. Буферные графы . . . . . . . . . . . . . . . . . . . . . . . . . . .5.2.2. Ориентации сети G . . . . . . . . . . . . . . . . . . . . . . . . . .Неструктурированные решения . . . . . . . . . . . . . . . . . . . . . .5.3.1. Контроллеры с прямым и обратным отсчетом . . . . . . . .5.3.2. Контроллеры с состояниями прямого и обратного отсчетаПрочие вопросы. .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5.4.1. Изменения топологии . . . . . . . . . . . . . . . . . . . . . . . .5.4.2. Другие типы блокировок . . . . . . . . . . . . . . . . . . . . . .5.4.3. Активный тупик . . . . . . . . . . . . . . . . . . . . . . . . . . . .Упражнения к главе 5 . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .Г л а в а 6.8889929498100105111114116Г л а в а 5. Неблокируемая коммутация пакетов5.1.5.2.7Оглавление7.3.7.4.7.5.239Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7.1.1. Допущения, которых придерживаются в этой главе .7.1.2. Выборы и волны . . . . . . . . . . . . . . . . . . .
. . . .Кольцевые сети . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7.2.1. Алгоритмы Ле-Ланна и Ченя—Робертса . . . . . . .7.2.2. Алгоритм Петерсона/Долева—Клейва—Роде . . . .7.2.3. Результат о нижних оценках . . . . . . . . . . . . . . . .Произвольные сети. . . .
. . . . . . . . . . . . . . . . . . . . . . .7.3.1. Эффект угасания и быстрый алгоритм . . . . . . . . .7.3.2. Алгоритм Галладжера—Хамблета—Спиры . . . . . .7.3.3. Глобальное описание алгоритма GHS. . . . . . . . . .7.3.4. Подробное описание алгоритма GHS . . . . . . . . . .7.3.5. Обсуждение GHS-алгоритма и его модификаций . .Алгоритм Корача—Каттена—Морана . . . . . . .
. . . . . . .7.4.1. Модульная конструкция. . . . . . . . . . . . . . . . . . .7.4.2. Приложения алгоритма Корача—Каттена—МоранаУпражнения к главе 7 . . . . . . . . . . . . . . . . . . . . . . . . ...........................................................................................................................................................................Г л а в а 8. Обнаружение завершения1938.1.1941941961988.2.Основные понятия . . .
. . . . . . .8.1.1. Определения . . . . . . . . .8.1.2. Две нижние оценки . . . . .8.1.3. Как остановить процессы.Деревья и леса вычислений . . . .199200202202203206208209212214216216217218220222223228229229230233236239240241244245249253258259261263265271272273278279281.......................................................................................................................................2822822862882898Оглавление8.5..............................................................................Г л а в а 9.
Анонимные сети9.1.9.2.9.3.9.4.9.5.322Основные понятия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9.1.1. Определения . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9.1.2. Классификация вероятностных алгоритмов . . . . . . . . .9.1.3. Задачи, рассматриваемые в этой главе . . . . . . . . . . . .9.1.4. Синхронный и асинхронный обмен сообщениями. . . . .
.Детерминированные алгоритмы . . . . . . . . . . . . . . . . . . . . . .9.2.1. Детерминированные выборы: отрицательные результаты9.2.2. Вычисление функций на кольце. . . . . . . . . . . . . . . . .Вероятностный алгоритм избрания лидера . . . . . . . .
. . . . . .Вычисление размера сети. . . . . . . . . . . . . . . . . . . . . . . . . .9.4.1. Отрицательные результаты . . . . . . . . . . . . . . . . . . . .9.4.2. Алгоритм вычисления размера кольца . . . . . . . . . . . .Упражнения к главе 9 . . .
. . . . . . . . . . . . . . . . . . . . . . . . ............................................................................................Г л а в а 10. Моментальные состояния системы10.1. Начальные сведения . . . . . . . . . . . . . . . . . . . . . . . . . . . .10.2. Два алгоритма построения моментального состояния . . . . .
.10.2.1. Алгоритм Ченди—Лэмпорта . . . . . . . . . . . . . . . . . .10.2.2. Алгоритм Лая—Янга . . . . . . . . . . . . . . . . . . . . . .10.3. Применение алгоритмов построения моментальных состояний.10.3.1. Вычисление состояния канала. . . . . . . . . . . . . . . . .10.3.2. Своевременность моментальных состояний системы . .10.3.3.
Обнаружение устойчивых свойств . . . . . . . . . . . . . .10.4. Приложения: обнаружение тупиков . . . . . . . . . . . . . . . . . .10.4.1. Модель базового вычисления и постановка задачи . . .10.4.2. Алгоритм глобальной разметки . . . . . . . . . . . . . . . .10.4.3. Обнаружение тупиков в ограниченных моделях .
. . . .10.5. Упражнения к главе 10 . . . . . . . . . . . . . . . . . . . . . . . . . .289294299300304309312314314317320323324327329331331332333338342342345348351............................................................................................ 352. 357. 357. 359. 361. 361. 362. 363. 366.
366. 368. 371. 372Г л а в а 11. Восприятие направления и ориентация11.1. Введение и определения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11.1.1. Определения и характеристические свойства восприятия направления . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11.1.2. Применение восприятия направления . . . . . . . . . . . . . . . . . . . .11.1.3. Широковещательная рассылка сообщений при наличии восприятиянаправления . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .37437537537938011.2. Выборы на кольцах и хордовых кольцах . . . . . . . . . . . . . . . . . . . . .11.2.1. Алгоритм Франклина . . . . . . . . . . . . . . . . . . . . . . . . . . . .11.2.2. Усовершенствование Аттьи. . . . . . . . . . . . . .
. . . . . . . . . . .11.2.3. Минимизация числа хорд . . . . . . . . . . . . . . . . . . . . . . . . . .11.2.4. Однохордовый линейный алгоритм. . . . . . . . . . . . . . . . . . . .11.3. Вычисления в гиперкубах . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . .11.3.1. Базис: отсутствие осведомленности о топологии сети . . . . . . .11.3.2. Алгоритм посредничества. . . . . . . . . . . . . . . . . . . . . . . . . .11.3.3. Алгоритм потока по многим путям . . . . . . . . . . . . . . . . . . . .11.3.4. Эффективные алгоритмы для гиперкубов на основе трафаретов.11.3.5. Выборы в неразмеченных гиперкубах . . . .
. . . . . . . . . . . . . .11.4. Сложностные аспекты. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11.4.1. Ориентация клики или произвольного графа . . . . . . . . . . . . .11.4.2. Битовая сложность и алгоритм потока по многим путям . . . . .11.4.3. Алгоритм случайного блуждания Вервейджа . . . . . .
. . . . . . .11.5. Заключение и открытые вопросы. . . . . . . . . . . . . . . . . . . . . . . . . .11.5.1. Использование восприятия направления . . . . . . . . . . . . . . . .11.5.2. Понижение сложности. . . . . . . . . . . . . . . . . . . . . . . . . . . .11.5.3. Современные исследования . .
. . . . . . . . . . . . . . . . . . . . . .11.6. Упражнения к главе 11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .........................................Г л а в а 12. Синхронизация в сетях12.1. Начальные сведения . . . .
. . . . . . . . . . . . . . . . . . . . . .12.1.1. Синхронные сети . . . . . . . . . . . . . . . . . . . . . . .12.1.2. Повышение эффективности за счет синхронизации .12.1.3. Асинхронные сети с ограниченной задержкой . . . .12.2. Выборы в синхронных сетях. . . . . . . . . . . . . . . . . . . .
.12.2.1. Размер сети известен . . . . . . . . . . . . . . . . . . . .12.2.2. Размер сети неизвестен . . . . . . . . . . . . . . . . . . .12.2.3. Дополнительные результаты . . . . . . . . . . . . . . . .12.3. Алгоритмы-синхронизаторы . . . . . . . . . . . . . . . . . . . . .12.3.1. Простой синхронизатор . . . . . . . .
. . . . . . . . . . .12.3.2. , , и -синхронизаторы . . . . . . . . . . . . . . . . . .12.4. Приложения: поиск в ширину . . . . . . . . . . . . . . . . . . . .12.4.1. Синхронный BFS-алгоритм . . . . . . . . . . . . . . . .12.4.2. Соединение с синхронизатором . . . . . . . . . . . . . .12.4.3. Асинхронные BFS-алгоритмы.
. . . . . . . . . . . . . .12.5. Допущение Архимеда . . . . . . . . . . . . . . . . . . . . . . . . .12.6. Упражнения к главе 12 . . . . . . . . . . . . . . . . . . . . . . . ..........................................................................................................................................................Г л а в а 13. Отказоустойчивость в распределенных системах13.1.
Зачем нужны отказоустойчивые алгоритмы . . . . . . .13.2. Робастные алгоритмы . . . . . . . . . . . . . . . . . . . . .13.2.1. Модели неисправностей . . . . . . . . . . . . . . .13.2.2. Проблемы принятия решения . . . . . . . . . . .13.2.3. Краткое содержание глав 14–16 . . .
. . . . . .13.2.4. Темы, которые не были включены в эту книгу13.3. Стабилизирующиеся алгоритмы . . . . . . . . . . . . . .3833833843863893933943943974014044054054074094114114124134134158.4.8.2.1. Алгоритм Дейкстры—Шолтена . . . . . . . . . . . . . . . . .8.2.2. Алгоритм Шави—Франчеза . . . . . . . . . . . . . . .
. . . .Решения на основе волновых алгоритмов . . . . . . . . . . . . . . .8.3.1. Алгоритм Дейкстры—Фейджена—ван Гастерена . . . . .8.3.2. Подсчет базовых сообщений: алгоритм Сафры. . . . . . .8.3.3. Использование подтверждений . . . . . . . . . . . . . . . . .8.3.4. Обнаружение завершения вычислений при помощи волнПрочие решения . .
