Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 2
Текст из файла (страница 2)
Определение волновых алгоритм ов............................................................6.1.2. Основные свойства волновых алгоритмов................................................6.1.3. Распространение информации с обратной связью ...................................193194194196198Оглавление6.1.4.6.1.5.6.2.С инхронизация..................................................................................................Вычисление функций точной нижней гр а н и .............................................Семейство волновых алгоритмов................................................................................6.2.1.
Кольцевой алгоритм .........................................................................................6.2.2. Древесный алгоритм.........................................................................................6.2.3. Алгоритм э х а ........................................................................................................6.2.4. Алгоритм о п р о с а ...............................................................................................6.2.5. Фазовый ал гори тм ............................................................................................6.2.6.
Алгоритм Ф и н н а ...............................................................................................71992002022022032062082092126.3.Алгоритмы о б х о д а ...........................................................................................................6.3.1. О бход клик...........................................................................................................6.3.2. О бход т о р о в ........................................................................................................6.3.3. О бход гиперкубов...............................................................................................6.3.4. О бход связных сетей.........................................................................................2142162162172186.4.Сложность по времени: поиск в глубину..................................................................6.4.1.
Распределенный поиск в глубину..................................................................6.4.2. Алгоритмы поиска в глубину, требующие линейного времени . . . .6.4.3. Поиск в глубину с учетом сведений о с о с е д я х .......................................2206.5.Прочие вопросы.................................................................................................................6.5.1. Обзор волновых алгоритмов..........................................................................6.5.2.
Вычисление су м м ...............................................................................................6.5.3. Альтернативные определения сложности по времени...........................2292292302336.6.Упражнения к главе 6 .....................................................................................................236Глава7.
Алгоритмы избрания лидера2222232282397.1.В в е д е н и е .............................................................................................................................7.1.1. Допущения, которых придерживаются в этой главе..............................7.1.2. Выборы и в о л н ы ...............................................................................................2392402417.2.Кольцевые с е т и .................................................................................................................7.2.1.
Алгоритмы Ле-Ланна и Ченя— Р о б е р т с а ................................................7.2.2. Алгоритм Петерсона/Долева— Клейва— Р о д е .......................................7.2.3. Результат о нижних оценках..........................................................................2442452492537.3.Произвольные сети...........................................................................................................7.3.1.
Эффект угасания и быстрый алгоритм ......................................................7.3.2. Алгоритм Галладжера— Хамблета— С п и р ы .............................................7.3.3. Глобальное описание алгоритма G H S .........................................................7.3.4. Подробное описание алгоритма G H S ........................................................7.3.5. Обсуждение G H S -алгоритма и его модификаций.................................2582592612632652717.4.Алгоритм Корача— Каттена— М о р а н а ....................................................................7.4.1. Модульная конструкция...................................................................................7.4.2. Приложения алгоритма Корача— Каттена— М о р а н а ...........................2722732787.5.Упражнения к главе 7 .....................................................................................................279Глава8.О бнаруж ение заверш ения2818.1.Основные понятия...........................................................................................................8.1.1.
О пределения........................................................................................................8.1.2. Две нижние оценки............................................................................................8.1.3. Как остановить процессы................................................................................2822822862888.2.Деревья и леса вычислений.........................................................................................289Оглавление8.2.1.8.2.2.Алгоритм Дейкстры— Ш олтена.....................................................................Алгоритм Шави— Ф р ан чеза...........................................................................2892948.3.Решения на основе волновых алгоритмов...............................................................8.3.1.
Алгоритм Дейкстры— Фейджена— ван Г а стер ен а.................................8.3.2. Подсчет базовых сообщений: алгоритм Сафры.......................................8.3.3. Использование подтверждений.....................................................................8.3.4. Обнаружение завершения вычислений при помощи в о л н ..................2993003043093128.4.Прочие р е ш е н и я ..............................................................................................................8.4.1. Алгоритм возвращения кредита.....................................................................8.4.2. Решения, использующие штемпель времени.............................................3143143178.5.Упражнения к главе 8 .....................................................................................................320Глава9.
Анонимные сети3229.1.Основные понятия...........................................................................................................9.1.1. О пределения........................................................................................................9.1.2. Классификация вероятностных алгоритмов.............................................9.1.3. Задачи, рассматриваемые в этой г л а в е......................................................9.1.4. Синхронный и асинхронный обмен сообщениями...................................3233243273293319.2.Детерминированные алгоритмы...................................................................................9.2.1.
Детерминированные выборы: отрицательныерезультаты ....................9.2.2. Вычисление функций на кольце.....................................................................3313323339.3.Вероятностный алгоритм избрания л и д е р а ............................................................3389.4.Вычисление размера сети...............................................................................................9.4.1. Отрицательные результаты..............................................................................9.4.2. Алгоритм вычисления размера к о л ь ц а ......................................................3423423459.5.Упражнения к главе 9 .....................................................................................................348Глава10.М оментальные состояния системы35110.1.
Начальные сведения........................................................................................................35210.2. Два алгоритма построения моментального с о с т о я н и я .......................................10.2.1. Алгоритм Ченди— Л эмпорта...........................................................................10.2.2. Алгоритм Лая— Я н г а .......................................................................................35735735910.3. Применение алгоритмов построения моментальных состояний........................10.3.1.
Вычисление состояния канала........................................................................10.3.2. Своевременность моментальных состояний си стем ы ...........................10.3.3. Обнаружение устойчивых свой ств...............................................................36136136236310.4. Приложения: обнаружение тупиков...........................................................................10.4.1. Модель базового вычисления и постановка за д а ч и ..............................10.4.2. Алгоритм глобальной разметки.....................................................................10.4.3. Обнаружение тупиков в ограниченных м о д е л я х ....................................36636636837110.5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
