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

В этой главе также дается определение сложностипо времени для распределенных алгоритмов и исследуется сложность по времени и по числу обменов сообщениями целого ряда распределенных алгоритмовпоиска в глубину.Одной из фундаментальных проблем, возникающих в распределенных системах, является задача избрания лидера: требуется выбрать один-единственныйпроцесс, которому отводится особая роль в последующем вычислении. Эта задачаизучается в гл. 7. Вначале мы ограничимся случаем кольцевых сетей и покажем,что для этой задачи сложность по числу обменов сообщениями составляет величину Θ (N log N) (для колец с N процессорами).

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

В этой главе рассматриваются несколько классических алгоритмов (в том числе алгоритм Дейкстры, Фейджена и Ван Гастерена, а такжеалгоритм Дейкстры и Шолтена) и, как и в предыдущей главе, описывается способполучения алгоритмов решения этой задачи на основе волновых алгоритмов.Глава 9 посвящена изучению вычислительных возможностей систем, процессы которых не имеют индивидуальных отличительных признаков.

Как было уста-52Гл. 1. Введение: распределенные системыновлено Англуином, в этом случае многие вычислительные задачи нельзя решитьпри помощи детерминированных алгоритмов. В этой главе мы введем вероятностные алгоритмы и исследуем, какие задачи можно решить при помощи этихалгоритмов.В главе 10 рассказывается о том, как процессы системы могут сформироватьглобальную «картину вычисления», т е. так называемое моментальное состояние системы.

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

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

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

14 изучаются вопросы отказоустойчивости асинхронных распределенных систем. Приводится результат, полученный Фишером и др., который свидетельствует о том, что детерминированные асинхронные системы не могут справиться даже со сравнительно простыми неисправностями, как то: выход из строяодного-единственного процесса. Но также будет показано, что последствия неисправностей более слабого типа можно устранить и некоторые задачи разрешимы,несмотря на выход из строя некоторых компонентов системы. Мы представим алгоритмы Брачи и Туэга, которые показывают, что рандомизованные асинхронныесистемы способны справиться с достаточно большим числом неисправностей. Таким образом, мы видим, что, как и в случае с надежными системами, описаннымив гл.

9, вычислительные возможности рандомизованных алгоритмов превосходятвозможности детерминированных алгоритмов.В гл. 15 изучаются вопросы отказоустойчивости синхронных систем. Алгоритмы, разработанные Лампортом и др., демонстрируют устойчивость детерми-1.4. Обзор содержания книги53нированных синхронных алгоритмов по отношению к сложным неисправностям.Таким образом, мы видим, что, в отличие от надежных систем, рассмотренныхв гл.

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

Этой задаче посвящена гл. 15.В гл. 16 изучаются свойства общих приемов (их называют детектораминеисправностей), которые позволяют процессам системы оценить, какие процессы вышли из строя, а какие остались исправными. Мы расскажем о том, какможно реализовать эти приемы, а также о том, как их можно использовать дляреализации спецификаций в неисправной вычислительной среде.В гл. 17 рассматривается другой подход к повышению надежности систем засчет использования самостабилизирующихся алгоритмов. Алгоритм называетсястабилизирующимся, если независимо от начальной конфигурации, с которой начинается его вычисление, оно рано или поздно сходится к требуемому поведению.Мы разработаем некоторые элементы теории стабилизирующихся алгоритмов иприведем ряд примеров стабилизирующихся алгоритмов. К числу этих алгоритмов относятся протоколы для некоторых алгоритмов на графах (вычисления деревьев поиска в глубину, описанные в § 6.6.4, вычисления таблиц маршрутизацииописанные в гл.

4). Кроме того, были предложены стабилизирующиеся алгоритмы для задачи передачи данных, которая рассматривается в гл. 3, и это означает,что всякую вычислительную сеть можно реализовать при помощи стабилизирующихся алгоритмов.Приложения. В гл. A объясняется та система обозначений, которая используется в этой книге для описания распределенных алгоритмов. В гл. Б содержитсярад общих сведений из теории графов, включая используемую в этой книге терминологию из теории графов. В конце книги приводится список литературы ипредметный указатель.2.1.

Системы переходов и алгоритмыГЛАВА 2МОДЕЛЬПри изучении распределенных алгоритмов наиболее часто используются несколько различных моделей распределенной обработки информации. Конкретнаямодель обычно выбирается в зависимости от исследуемой задачи из области распределенных вычислений, а также от представленной разновидности алгоритма(или доказательства отсутствия такового). Хотя в этой книге рассматриваетсяширокий спектр распределенных алгоритмов и относящихся к ним теоретическихрезультатов, автор предпринял попытку представить весь материал, насколькоэто возможно, в рамках одной-единственной общей модели, описанной в этойглаве.Для того чтобы позволить получать отрицательные результаты (доказательство невозможности построения алгоритмов решения той или иной задачи), модель должна быть очень точной.

Отрицательный результат — это утверждение,относящееся ко всем возможным алгоритмам системы; поэтому модель должна быть настолько точна, чтобы в ее рамках можно было описать существенные свойства всех допустимых алгоритмов. И все же вычислительная модель —это нечто большее, чем подробное описание конкретной вычислительной машины или языка программирования. Существует много разных вычислительных систем, и нам хотелось бы, чтобы выбранная модель была применима к целомуклассу родственных систем, наделенных теми специальными важными качествами, благодаря которым эти системы становятся «распределенными». Наконец,выбранная модель должна быть достаточно компактной, поскольку мы вправеожидать, что ее можно будет всесторонне рассмотреть при проведении доказательств. Таким образом, модель должна точно и кратко описывать наиболеесущественные аспекты некоторого класса вычислительных систем.Распределенное вычисление обычно рассматривается в виде совокупностидискретных событий, каждое из которых представляет собой небольшое изменение конфигурации (состояния всей системы).