Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 3
Текст из файла (страница 3)
Упражнения к главе 1 0 ..................................................................................................372Глава11.1.11.Восприятие направления и ориентацияВведение и о п р ед ел ен и я ..............................................................................................11.1.1. Определения и характеристические свойства восприятия направления ...................................................................................................................................11.1.2. Применение восприятия направления.........................................................11.1.3.
Широковещательная рассылка сообщений при наличии восприятиянаправления.................................................................................................................374375375379380Оглавление911.2. Выборы на кольцах и хордовых кольцах..................................................................11.2.1. Алгоритм Ф р ан к л и н а.......................................................................................11.2.2. Усовершенствование Аттьи..............................................................................11.2.3.
Минимизация числа хо р д .................................................................................11.2.4. Однохордовый линейный алгоритм...............................................................38338338438638911.3. Вычисления в г и п ер к у б а х ............................................................................................11.3.1. Базис: отсутствие осведомленности о топологии с е т и ........................11.3.2.
Алгоритм посредничества.................................................................................11.3.3. Алгоритм потока по многим путям...............................................................11.3.4. Эффективные алгоритмы для гиперкубов на основе трафаретов. . .11.3.5. Выборы в неразмеченных гиперкубах.........................................................39339439439740140411.4. Сложностные аспекты......................................................................................................11.4.1. Ориентация клики или произвольного г р а ф а ..........................................11.4.2.
Битовая сложность и алгоритм потока по многим п у т я м ..................11.4.3. Алгоритм случайного блуждания В ер вей дж а..........................................40540540740911.5. Заключение и открытые вопросы.................................................................................11.5.1. Использование восприятия направления...................................................11.5.2. Понижение сложности.......................................................................................11.5.3. Современные и ссл едован ия...........................................................................41141141241311.6. Упражнения к главе 1 1 ...................................................................................................413Глава12.Синхронизация в сетях41512.1.
Начальные сведения........................................................................................................12.1.1. Синхронные с е т и ................................................................................................12.1.2. Повышение эффективности за счет синхронизации..............................12.1.3. Асинхронные сети с ограниченной за д е р ж к о й .......................................41641641841912.2. Выборы в синхронных сетях..........................................................................................12.2.1.
Размер сети и з в е с т е н .......................................................................................12.2.2. Размер сети неизвестен....................................................................................12.2.3. Дополнительные результаты...........................................................................42342442542612.3. Алгоритмы-синхронизаторы..........................................................................................12.3.1. Простой синхронизатор....................................................................................12.3.2.
а, р, и у-синхронизаторы.................................................................................42742843012.4. Приложения: поиск в ширину.......................................................................................12.4.1. Синхронный B F S -ал гор итм ...........................................................................12.4.2. Соединение с синхронизатором.....................................................................12.4.3.
Асинхронные B F S -алгоритмы........................................................................43343443543512.5. Допущение А р х и м ед а ......................................................................................................43912.6. Упражнения к главе 1 2 ...................................................................................................441Глава13.О тказоустойчивость в распределенны х систем ах44413.1. Зачем нужны отказоустойчивые алгоритмы............................................................44413.2.
Робастные алгоритмы.....................................................................................................13.2.1. Модели неисправностей....................................................................................13.2.2. Проблемы принятия реш ения........................................................................13.2.3. Краткое содержание глав 14—1 6 ..................................................................13.2.4.
Темы, которые не были включены в эту к н и г у .......................................44644644845045213.3. Стабилизирующиеся алгоритм ы .................................................................................45310ОглавлениеГлава14.О тказоустойчивость в асинхронны х систем ах45514.1. Невозможность к о н сен су са ..........................................................................................14.1.1.
Обозначения, определения и простейшие результаты...........................14.1.2. Доказательство невозможности построения робастных асинхронныхси ст ем .............................................................................................................................14.1.3. О б с у ж д е н и е ........................................................................................................45545545846014.2. Изначально бездействующие процессы.....................................................................46114.3. На что способны детерминированные систем ы ?...................................................14.3.1. Разрешимая задача: переименование.........................................................14.3.2.
Более общие результаты о невозможности построения алгоритмов46446546914.4. Вероятностные алгоритмы к о н сен су са ..................................................................... 47114.4.1. Протоколы консенсуса, робастные относительно выхода процессовиз ст р о я .......................................................................................................................... 47214.4.2.
Робастные в византийской модели неисправностей протоколы консенсуса .......................................................................................................................... 47714.5. Слабая заверш аем ость...................................................................................................48314.6. Упражнения к главе 1 4 ...................................................................................................487Глава15.О тказоустойчивость в синхронны х систем ах49015.1. Синхронные протоколы принятия р еш ен и я ............................................................15.1.1.
Границы устойчивости......................................................................................15.1.2. Алгоритм широковещательного распространения информации приналичии неисправностей византийского т и п а ...................................................15.1.3. Алгоритм широковещательного распространения информации, имеющий полиномиальную сложность........................................................................49149215.2. Протоколы с аутентификацией....................................................................................15.2.1. Протоколы, обладающие высокой устойчивостью.................................15.2.2.
Как устроены схемы цифровой п о д п и с и ...................................................15.2.3. Схема цифровой подписи Э л ь-Г ам ал я......................................................15.2.4. Схема цифровой подписи R S A .....................................................................15.2.5. Схема цифровой подписи Фиата— Ш ам ира.............................................15.2.6. Подведение и т о го в ............................................................................................50450450850951151251415.3.
Синхронизация ч а с о в .....................................................................................................15.3.1. Как снимать показания с удаленных ч а с о в .............................................15.3.2. Синхронизация часов в распределенной системе....................................15.3.3. Реализация раундовой модели........................................................................51751852152615.4. Упражнения к главе 1 5 ..................................................................................................527Глава16.О бнаруж ение неисправностей16.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
