Реферат: Распределенные алгоритмы

Раздел 7.4                                                                                                                      226

8 Обнаружение завершения                                                                        227

8.1 Предварительные замечания                                                                               228

8.1.1 Определения                                                                                                       228

8.1.2 Две нижних границы                                                                                         231

8.1.3 Завершение Процессов                                                                                      233

8.2.2 Алгоритм Shavit-Francez                                                                                    237

8.3 Решения, основанные на волнах                                                                         241

8.3.1 Алгоритм Dijkstra-Feijen-Van Gasteren                                                             242

8.3.2 Подсчет Основных Сообщений: Алгоритм Сафра                                        245

8.3.3 Использование Подтверждений                                                                       249

8.3.4 Обнаружение завершения с помощью волн                                                    252

8.4 Другие Решения                                                                                                      254

8.4.1 Алгоритм восстановления кредита                                                                  254

8.4.2 Решения, использующие временные пометки                                                256

Упражнения к  Главе 8                                                                                                259

Раздел 8.1                                                                                                                      259

Раздел 8.2                                                                                                                      259

Раздел 8.3                                                                                                                      259

Раздел 8.4                                                                                                                      260

13 Отказоустойчивость в Асинхронных Системах                  260

13.1 Невозможность согласия                                                                                     260

13.1.1 Обозначения, Определения, Элементарные Результаты                             260

13.1.2 Доказательство невозможности                                                                      262

13.1.3 Обсуждение                                                                                                      264

13.2 Изначально-мертвые Процессы                                                                        265

13.3 Детерминированно Достижимые Случаи                                                        268

13.3.1 Разрешимая Проблема: Переименование                                                      269

13.3.2 Расширение Результатов Невозможности                                                     273

13.4 Вероятностные Алгоритмы Согласия                                                             275

13.4.1 Аварийно-устойчивые Протоколы Согласия                                               276

13.4.2 Византийско-устойчивые Протоколы Согласия                                          280

13.5 Слабое Завершение                                                                                              285

Упражнения к Главе 13                                                                                               289

Раздел 13.1                                                                                                                    289

Раздел 13.2                                                                                                                    289

Раздел 13.3                                                                                                                    289

Раздел 13.4                                                                                                                    290

Раздел 13.5                                                                                                                    291

14 Отказоустойчивость в Синхронных Системах                     291

14.1 Синхронные Протоколы Решения                                                                    292

14.1.1 Граница Способности восстановления                                                         293

14.1.2 Алгоритм Византийского вещания                                                                295

14.1.3 Полиномиальный Алгоритм Вещания                                                          298

14.2 Протоколы с Установлением Подлинности                                                    303

14.2.1 Протокол Высокой Степени Восстановления                                              304

14.2.2 Реализация Цифровых Подписей                                                                   307

14.2.3 Схема Подписи ЭльГамаля                                                                             308

14.2.4 Схема Подписи RSA                                                                                        310

14.2.5 Схема Подписи Фиата-Шамира                                                                     310

14.2.6 Резюме и Обсуждение                                                                                     313

14.3 Синхронизация Часов                                                                                          315

14.3.1 Чтение Удаленных Часов                                                                                316

14.3.2 Распределенная Синхронизация Часов                                                         318

Пролог

Распределенные системы и обработка распределенной информации получили значительное внимание в последние несколько лет, и почти каждый университет предлагает, по крайней мере, один курс по разработке распределенных алгоритмов. Существует большое число книг о принципах распределенных систем; см. например Tanenbaum [Tan88] или Sloman and Kramer [SK87], хотя они концентрируются в основном на архитектурных аспектах, а не на алгоритмах.

Было замечено, что алгоритмы – это основа любого применения компьютеров. Поэтому кажется оправданным посвятить эту книгу полностью распределенным алгоритмам. Эта книга направлена на то, чтобы представить большую часть теории распределенных алгоритмов, которые развивались в течение последних 15 лет.  Эта книга может быть использована как учебник для одно- или двух-семестрового курса по распределенным алгоритмам. Преподаватель одно-семестрового курса может выбирать темы по своему усмотрению.

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

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

Список ответов (иногда частичных) у большинству упражнений доступен для преподавателей. Он может быть получен у автора или по анонимному ftp.

Исправления и предложения. Если читатель найдет ошибки и пропуски в этой книге, то пусть информирует автора (предпочтительно по электронной почте). Вся конструктивная критика, включая предложения по упражнения, очень приветствуется.

1 Введение: распределенные системы

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

Различные типы распределенных систем и причины использования распределенных систем обсуждаются в разделе 1.1. Приводятся некоторые примеры существующих систем. Главная тема этой книги, однако, не то, как эти системы выглядят, или как они используются, но как заставить их работать. Более того, как заставить работать распределенные алгоритмы в этих системах.

Конечно, целиком структуру и функционирование распределенной системы нельзя полностью понять изучением только алгоритмов самих по себе. Чтобы понять такую систему полностью нужно также изучить ее архитектуру и программное обеспечение, то есть, разбиение цельной функциональности по модулям. Также, есть много важных вопросов, относящихся к свойствам языков программирования, используемых для разработки программного обеспечения распределенных систем. Эти вопросы будут обсуждаться в разделе 1.2.

Однако сейчас существует много превосходных книг по распределенным системам, касающихся архитектурных и языковых аспектов. Смотрите Tanenbaum [Tan88], Sloman and Kramer [SK87], Bal [Bal90], Coulouris [CD88], Goscinski [Gos91]. Как уже говорилось, настоящий труд делает упор на алгоритмы распределенных систем. Раздел 1.3 объясняет, почему разработка распределенных алгоритмов отличается от разработки централизованных алгоритмов, там также делается краткий обзор текущего состояния дел в исследованиях и дается описание остальной части книги.

1.1 Что такое распределенная система?

В этой главе мы будем использовать термин «распределенная система», подразумевая взаимосвязанный набор автономных компьютеров, процессов или процессоров. Компьютеры, процессы или процессоры упоминаются как узлы распределенной системы. (В последующих главах мы будем использовать более техническое понятие, см. определение 2.6.) Будучи определенными как «автономные», узлы должны быть, по крайней мере, оборудованы своим собственным блоком управления. Таким образом, параллельный компьютер с одним потоком управления и несколькими потоками данных (SIMD) не подпадает под определение распределенной системы. Чтобы быть определенными как «взаимосвязанными», узлы должны иметь возможность обмениваться информацией.

Так как процессы могут играть роль узлов системы, определение включает программные системы, построенные как набор взаимодействующих процессов, даже если они выполняются на одной аппаратной платформе. В большинстве случаев, однако, распределенная система будет, по крайней мере, содержать несколько процессоров, соединенный коммутирующей аппаратурой.

Более ограничивающие определения распределенных систем могут быть также найдены в литературе. Tanenbaum [Tan88], например, называет систему распределенной, только если существуют автономные узлы прозрачные для пользователей системы. Система распределенная в этом смысле ведет себя как виртуальная самостоятельная компьютерная система, но реализация этой прозрачности требует разработки замысловатых алгоритмов распределенного управления.

1.1.1 Мотивация

Распределенные компьютерные системы могут получить предпочтение среди ряда систем или их использования бывает просто не избежать, в силу многих причин, некоторые из которых обсуждаются ниже. Этот список не исчерпывающий. Выбор распределенной системы может быть мотивирован более чем одним аргументов приведенным ниже. И некоторые из преимуществ могут быть получены как полезный побочный эффект при выборе других причин. Характеристики распределенных систем могут также варьироваться, в зависимости от причины их существования, но об этом мы поговорим более детально в разделах с 1.1.2 по 1.1.6.

(1)  Обмен информацией. Необходимость обмена данными между различными компьютерами возросла в шестидесятых, когда большинство основных университетов и компаний начали пользоваться своими собственными майнфреймами. Взаимодействие между людьми из различных организаций облегчилось благодаря обмену данными между компьютерами этих организаций, и это дало рост развитию так называемых глобальных сетей (WAN). Компьютерная система соединенная в глобальную сеть обычно снабжалась всем что необходимо пользователю: резервными хранилищами данных, дисками, многими прикладными программами и принтерами.
            Позже компьютеры стали меньше и дешевле, и сегодня одна организация может иметь множество компьютеров, иногда даже один компьютер на одного работника (рабочую станцию). В этом случае также требуется чтобы эти компьютеры были соединены для электронного обмена информацией между персоналом компании.

(2)  Разделение ресурсов. Хотя с приходом более дешевых компьютеров стало возможно снабжать каждого сотрудника организации личным компьютером, это же нельзя сделать для периферии (принтеры, резервные хранилища, блоки дисков). В этом меньшем масштабе каждый компьютер может положиться на специальные серверы, которые снабжают его компиляторами и другими прикладными программами. Также, памяти любого компьютера обычно недостаточно, чтобы хранить большой набор прикладных программ, требуемых для каждого пользователя. Кроме того, компьютеры могут использовать специальные узлы для служб печати и хранения данных. Сеть, соединяющая компьютеры в масштабе предприятия называется локальной вычислительной сетью(LAN).
      Причины, по которым организация устанавливает сеть небольших компьютеров, а не майнфреймы – снижение стоимости и расширяемость. Во-первых, меньшие компьютеры имеют лучше соотношение цена-производительность, чем большие компьютеры. Типичный майнфрейм может совершать операции в 50 раз быстрее, чем персональный компьютер, но иметь стоимость в 500 раз большую. Во-вторых, если  мощности системы больше не достаточно, то сеть может быть расширена добавлением других машин (файловых серверов, принтеров и рабочих станций). Если мощность монолитной системы больше неудовлетворительна, остается только полная замена.

(3)  Большая надежность благодаря репликации. Распределенные системы имеют потенциал надежности больший, чем монолитные системы благодаря свойству их частичного выхода из строя. Это значит, что некоторые узлы системы могут выйти из строя, в то время как другие по прежнему функционируют и могут взять на себя задачи испорченных компонентов. Выход из строя монолитного компьютера действует на всю систему целиком и нет возможности продолжать вычисления в этом случае. По этой причине распределенные архитектуры представляют интерес при разработке высоко надежных компьютерных систем.
        Высоко надежная система обычно состоит из двух, трех или четырех репликационных унипроцессоров, которые исполняют прикладную программу и поддерживаются механизмом голосования, чтобы отфильтровывать результаты машин. Правильное функционирование  распределенной системы при наличии поврежденных компонент требует довольно сложной алгоритмической поддержки.

(4)  Большая производительность благодаря распараллеливанию. Наличие многих процессоров в распределенной системе открывает возможность снижения дополнительного времени для интенсивной работы с помощью разделения работы среди нескольких процессоров.
            Параллельные компьютеры разработаны специально для этой цели, но пользователи локальных сетей также могут получить пользу от параллелизма, перекладывая задачи на другие рабочие станции.

(5)  Упрощение разработки благодаря специализации. Разработка компьютерной системы может быть сложной, особенно если требуется значительная функциональность. Разработка может быть зачастую упрощена разбитием системы на модули, каждый из которых отвечает за часть функциональности и коммутируется с другими модулями.
         На уровне одной программы модульность достигается определением абстрактных типов данных и процедур для различных задач. Большая система может быть определена как набор кооперирующих процессов. В обоих случаях, модули могут быть исполнены в рамках одного компьютера. Но также возможно иметь локальную сеть с различными типами компьютеров: один снабжен специальным оборудованием для вычислений, другой – графическим оборудованием, третий – дисками и т.д.

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62