Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно).pdf), страница 3

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .8.4.1. Алгоритм возвращения кредита . . . . . . . . . . . . . . . . .8.4.2. Решения, использующие штемпель времени. . . . . . . . .Упражнения к главе 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . .8.3.9Оглавление.............................................416416418419423424425426427428430433434435435439441444................................................................ 444.

446. 446. 448. 450. 452. 45310ОглавлениеГ л а в а 14. Отказоустойчивость в асинхронных системах45514.1. Невозможность консенсуса . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .14.1.1. Обозначения, определения и простейшие результаты . . . . . .

. . . .14.1.2. Доказательство невозможности построения робастных асинхронныхсистем . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .14.1.3. Обсуждение . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . .14.2. Изначально бездействующие процессы. . . . . . . . . . . . . . . . . . . . . . . .14.3. На что способны детерминированные системы? . . . . . . . . . . . . . . . . . .14.3.1. Разрешимая задача: переименование . . . . . . . . . . . . . . . . . . . .14.3.2. Более общие результаты о невозможности построения алгоритмов14.4. Вероятностные алгоритмы консенсуса . . . . . . . . . .

. . . . . . . . . . . . . .14.4.1. Протоколы консенсуса, робастные относительно выхода процессовиз строя . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .14.4.2. Робастные в византийской модели неисправностей протоколы консенсуса . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .14.5. Слабая завершаемость . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .14.6. Упражнения к главе 14 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Г л а в а 15. Отказоустойчивость в синхронных системах45545545846046146446546947147247748348749015.1. Синхронные протоколы принятия решения . . .

. . . . . . . . . . . . . . . . . .15.1.1. Границы устойчивости . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .15.1.2. Алгоритм широковещательного распространения информации приналичии неисправностей византийского типа . . . . . . . . . . . . . . . . . .15.1.3. Алгоритм широковещательного распространения информации, имеющий полиномиальную сложность. .

. . . . . . . . . . . . . . . . . . . . . . .15.2. Протоколы с аутентификацией . . . . . . . . . . . . . . . . . . . . . . . . . . . . .15.2.1. Протоколы, обладающие высокой устойчивостью . . . . . . . . . . . .15.2.2. Как устроены схемы цифровой подписи . . . . . . . . . . . . . . . . . .15.2.3. Схема цифровой подписи Эль-Гамаля . . . . . . . .

. . . . . . . . . . .15.2.4. Схема цифровой подписи RSA . . . . . . . . . . . . . . . . . . . . . . . .15.2.5. Схема цифровой подписи Фиата—Шамира . . . . . . . . . . . . . . . .15.2.6. Подведение итогов . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . .15.3. Синхронизация часов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .15.3.1. Как снимать показания с удаленных часов . . . . . . . . . . . . . . . .15.3.2. Синхронизация часов в распределенной системе. . . . . . . . . . . . .15.3.3. Реализация раундовой модели. . . . . . . . . . . . . . . . . . . . . . . . .15.4. Упражнения к главе 15 . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . .Г л а в а 16. Обнаружение неисправностей16.1. Модель и определения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .16.1.1. Четыре основных класса детекторов . . . . . . . . . . . . .

. . . .16.1.2. О том, как использовать детекторы неисправностей и подвохи16.2. Решение задачи консенсуса при помощи слабо точных детекторов. . .16.3. Слабо точные в конечном итоге детекторы . . . . . . . . . . . . . . . . . .16.3.1. Верхняя оценка устойчивости . . . . .

. . . . . . . . . . . . . . . . .16.3.2. Алгоритм консенсуса. . . . . . . . . . . . . . . . . . . . . . . . . . . .16.4. Реализация детекторов неисправности . . . . . . . . . . . . . . . . . . . . .16.4.1. Синхронные системы: совершенное обнаружение . . . . . . . . .11Оглавление491492494497504504508509511512514517518521526527530................... 531. 531. 534. 535. 537. 537. 539.

541. 54216.4.2. Частично синхронные системы: в конечном итоге совершенное обнаружение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54216.4.3. Заключительные замечания . . . . . . . . . . . . . . . . . . . . . . . . . . 54316.5. Упражнения к главе 16 . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . 544Г л а в а 17. Стабилизация54617.1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17.1.1. Определения . . . . . . . . . . . . . . . . . . . . . . . .17.1.2. Коммуникация в стабилизирующихся системах .17.1.3. Пример Дейкстры: кольцо с маркерами . . . . .

.17.2. Графовые алгоритмы . . . . . . . . . . . . . . . . . . . . . . . .17.2.1. Ориентация колец . . . . . . . . . . . . . . . . . . . .17.2.2. Максимальное покрытие . . . . . . . . . . . . . . . .17.2.3. Выборы лидера и построение остовных деревьев17.3. Общие методы стабилизации . . . . . . . . . . . . .

. . . . .17.3.1. Композиция протоколов. . . . . . . . . . . . . . . . .17.3.2. Вычисление минимальных путей . . . . . . . . . . .17.3.3. Заключительные выводы и обсуждение. . . . . . .17.4. Упражнения к главе 17 . . . . . . . . . . .

. . . . . . . . . . .............................................................................................................................................................547547549550553553557560563563570577577П р и л о ж е н и е A. Соглашения об использовании псевдокода579П р и л о ж е н и е Б. Графы и сети584Б.1. Определения и термины. . . . .

. . . . . . . .Б.1.1. Неориентированные графы . . . . . .Б.1.2. Ориентированные графы . . . . . . .Б.1.3. Взвешенные графы . . . . . . . . . . .Б.2. Наиболее распространенные виды графов .Б.2.1. Кольца . . . . . . . . . . . . . . . . . . .Б.2.2. Деревья, леса и звезды . . . . . . . .Б.2.3.

Клики . . . . . . . . . . . . . . . . . . .Б.2.4. Решетки и торы . . . . . . . . . . . . .Б.2.5. Гиперкубы . . . . . . . . . . . . . . . . .Б.3. Восприятие направления . . . . . . . . . . . .Б.4. Упражнения к главе Б . . . .

. . . . . . . . .............................................................................................................................................................................................................................................................584584586586587587588590591592593597Литература .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .600Предметный указатель . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .615ПредисловиеПРЕДИСЛОВИЕВ последние годы все большее внимание уделяется распределенным системам и распределенной обработке информации, и почти в каждом университетеесть хотя бы один курс лекций по разработке распределенных алгоритмов. Имеется немало книг, посвященных принципам устройства распределенных систем;к их числу относятся, например монографии Таненбаума [182] , а также Сломана и Крамера [176] . Однако в этих книгах рассматриваются преимущественновопросы архитектуры распределенных систем, а не распределенные алгоритмы.После публикации первого издания настоящей книги вышли в свет монографииБарбосы [24] , Линч [136] , Аттьи и Велча [12] .Как было верно замечено, алгоритмы образуют становой хребет каждого компьютерного приложения, и поэтому появление книг, посвященных исключительнораспределенным алгоритмам, вполне оправдано.

Цель настоящей книги — ознакомить читателей с наиболее значительными достижениями теории распределенных алгоритмов, которые были получены за последние двадцать лет. Эту книгу можно использовать в качестве учебного пособия по курсу распределенныхалгоритмов, который может охватывать один или два семестра; преподаватель,задумавший прочитать односеместровый курс, может выбирать темы из этой книги по своему желанию.

Профессиональные программисты и научные работники,имеющие дело с распределенными системами, могут найти в этой книге полезныйсправочный и библиографический материал.Упражнения. Каждая глава книги (за исключением глав 1 и 13) оканчивается списком упражнений и тем для небольших самостоятельных работ. В этихработах от читателя обычно требуется разработать небольшое, но, тем не менее,нетривиальное развитие или приложение того материала, который был представлен в той или иной главе книги. В большинстве случаев я не могу предложить«готового» решения этих задач, и если читателю удастся завершить один из таких мини-проектов, то автор книги будет рад ознакомиться с полученными результатами.

Преподаватели могут получить список ответов (иногда всего лишьчастичных) к большинству упражнений, обратившись к автору этой книги иливоспользовавшись анонимным ftp.Исправления и замечания. К тем читателям, которые обнаружат в этой книге ошибки или упущения, автор обращается с просьбой сообщить ему об этом(лучше всего это сделать, воспользовавшись электронной почтой). Все конструктивные замечания, включая предложения новых упражнений, тепло приветствуются.13Признательность. Предварительный вариант этой книги внимательно прочитали мои коллеги: Эрвин Беккер, Ганс Бодлаэндер, Стефан Добрев, Петра ванХаафтен, Тед Херман, Ян ван Льювен, Патрик Лентферт, Фридеманн Маттерн,Паскаль ван дер Пут, Питер Ружичка, Мартин Рудаликс, Анник Шун и КасаСере.