Главная » Просмотр файлов » Введение в распределённые алгоритмы. Ж. Тель (2009)

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

Файл №1185665 Введение в распределённые алгоритмы. Ж. Тель (2009) (Введение в распределённые алгоритмы. Ж. Тель (2009).pdf) 16 страницаВведение в распределённые алгоритмы. Ж. Тель (2009) (1185665) страница 162020-08-25СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 16)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Система становится «распреде­ленной» благодаря тому обстоятельству, что при выполнении каждого переходаприходится иметь дело только с частью конфигурации, а именно с (локаль­ным) состоянием одного процесса (или с локальными состояниями некоторогоподмножества взаимодействующих процессов.)Сама модель определена в §2.5.1; в §2.5.2 и 2.5.3 рассматриваются ее основ­ные свойства. Параграф 2.5.2 посвящен вопросам построения доказательств для2.1. Системы переходов и алгоритмы55обоснования требуемых свойств заданных распределенных алгоритмов.

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

Характеристики

Тип файла
PDF-файл
Размер
18,19 Mb
Тип материала
Высшее учебное заведение

Список файлов книги

Свежие статьи
Популярно сейчас
Зачем заказывать выполнение своего задания, если оно уже было выполнено много много раз? Его можно просто купить или даже скачать бесплатно на СтудИзбе. Найдите нужный учебный материал у нас!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6487
Авторов
на СтудИзбе
303
Средний доход
с одного платного файла
Обучение Подробнее