Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 15
Текст из файла (страница 15)
Бельснес в своей работе [26] описал протокол с пятью сообщениями, который предотвращаетпотерю информации и допускает дублирование только тогда, когда одна из NCPдействительно выходит из строя. В свете того, что в этом параграфе нами былаустановлена невозможность абсолютно надежной коммуникации, этот протоколявляется самым лучшим из всех возможных. Но из-за слишком больших накладных расходов (NCP совершают пять обменов сообщениями, чтобы передатьодну единицу информации) можно усомниться в том, что протокол с пятью сообщениями более предпочтителен, чем гораздо более простой протокол с двумясообщениями. Действительно, ввиду того что даже протокол с пятью сообщениями может дублировать информацию (в случае выхода из строя одной из NCP),с этим типом ошибок нужно уметь как-то справляться на уровне процессов. Таким образом, вполне пригодным будет и наш протокол с двумя сообщениями,который может приводить к дублированию, но не допускает потери информации,если к сообщениям добавлять сеансовые идентификационные номера, как этобыло сделано для протокола с тремя сообщениями.1.3.3.
Область исследованийИнтенсивное изучение распределенных алгоритмов продолжается уже болеетрех десятилетий. Наиболее значительный прогресс в исследованиях, определивший становление этого раздела информатики, был достигнут на рубеже вось1.4. Обзор содержания книги49мидесятых и девяностых годов.
В предыдущих параграфах мы обратили внимание читателей на некоторые технические разработки (проектирование глобальныхи локальных сетей, создание многопроцессорных компьютеров), которые стимулировали исследования в области распределенных алгоритмов. Первоначальноэти исследования были в значительной мере сосредоточены на алгоритмах, предназначенных для глобальных сетей, но в настоящее время в этой области разработаны четкие математические модели, позволяющие применять полученныеметоды и результаты к более широкому классу распределенных систем. Тем неменее, исследователи в области распределенных алгоритмов пристально следятза техническими разработками в области телекоммуникаций, поскольку многиеалгоритмические результаты зависят от изменений, которым подвергается сетевая модель.
Например, с появлением общедоступных дешевых микропроцессоровоткрылась возможность построения систем, состоящих из большого числа совершенно идентичных процессоров, и это, в свою очередь, послужило стимуломк изучению «анонимных сетей» (см. гл. 9).Существует несколько журналов и ежегодных конференций, тематика которых ограничена исключительно результатами в области распределенных алгоритмов и распределенных вычислений. В целом ряде других журналов и конференций, имеющих более широкую тематику, также представлено немало публикаций в этой области.
Ежегодный симпозиум «Principles of Distributed Computing (PoDC)» проводится в Северной Америке начиная с 1982 г. и до настоящего времени; труды симпозиума публикуются Ассоциацией по вычислительнойтехнике (ACM20)). Международная конференция «Workshops on Distributed Algorithms (WDAG)» проводилась впервые в Оттаве (1985), затем в Амстердаме(1987), в Ницце (1989), и, начиная с 1990 г, она стала ежегодным научным форумом, труды которого публикуются издательством Springer-Verlag в серии LectureNotes on Computer Science.
В 1998 г. эта конференция изменила название на«Distributed Computing» (DISC). Ежегодные симпозиумы по теории вычисленийSToC21) и FoC S22) охватывают все фундаментальные аспекты теории вычислений, и нередко в трудах этих конференций появляются работы, посвященныераспределенным вычислениям.
Труды SToC публикуются Ассоциацией по вычислительной технике, а труды FoCS — Институтом инженеров по электротехнике и электронике. В журналах «Journal of Parallel and Distributed Computing (JPDC)», «Distributed Computing», а также «Information Processing Letters(IPL)» регулярно публикуются статьи, посвященные распределенным алгоритмам.1.4. Обзор содержания книгиПри написании этой книги автор преследовал три цели.1.Ознакомить читателей с теми методами, которые применяются для изучения свойств заданных распределенных алгоритмов, для анализа и решения задач,^ A sso c ia tio n for Com puting Machinery — Прим, перев.21*Simposium on the Theory of Computing. — Прим, перев.22*Conference on the Foundations of Computer Science.
— Прим, перев.50Гл. 1. Введение: распределенные системывозникающих в связи с разработкой и использованием распределенных систем,или для оценки достоинств той или иной сетевой модели.2. Дать читателю ясное представление о том, каковы возможности тех илииных моделей распределенных систем. В §3.3.2, а также в гл.
12 и 15 рассказывается о том, какую роль играет глобальная шкала времени. В гл. 9 речь пойдет отом, насколько существенной оказывается осведомленность процессов об их отличительных признаках. В гл. 8 изучается вопрос о том, насколько существеннымявляется требование завершаемости вычислений. Третья часть книги посвящена изучению проблем, возникающих в связи с возможностью выхода из строяотдельных процессов системы.3. Рассказать о разнообразии современных распределенных алгоритмов, проведя при этом их верификацию, а также анализ их сложности.Если какой-то вопрос нельзя осветить во всех подробностях, в книге приводятсяссылки на наиболее важные публикации по этому вопросу.
Книга состоит из трехчастей: «Протоколы», «Фундаментальные алгоритмы», «Отказоустойчивость».Первая часть. Протоколы. Эта часть книги посвящена коммуникационнымпротоколам, которые используются при построении коммуникационных сетей длявзаимосвязи компьютеров; здесь также описываются некоторые методы, которыезатем используются в других частях книги.В гл. 2 вводится модель, которая будет использоваться в большинстве последующих глав. Эта модель является, с одной стороны, достаточно общей длятого, чтобы ее можно было с успехом применять при разработке и верификацииалгоритмов, а с другой стороны, достаточно строгой для того, чтобы ею можнобыло воспользоваться для доказательства невозможности построения некоторыхалгоритмов.
В основу этой модели положено понятие системы переходов, котороесопровождается простыми правилами для доказательства свойств безопасностии живости. Также определяется отношение причинно-следственной зависимости,задающее частичный порядок на множестве событий вычисления, и вводятся логические часы.В гл. 3 изучается проблема передачи сообщений между двумя узлами. Вначалемы ознакомим читателей с семейством протоколов обмена пакетами информациипо единственному каналу связи и приведем, следуя работе Щуна, доказательство корректности этих протоколов. Затем рассматривается протокол Флетчераи Ватсона, корректность которого зависит от правильного использования таймеров. Изучение этого протокола позволяет узнать, как можно применять методыверификации к протоколам, в которых задействованы таймеры.Глава 4 посвящена проблеме маршрутизации в вычислительных сетях. В первуюочередь, в ней приведены некоторые теоретические предпосылки для решения за дачи маршрутизации, а также описан алгоритм Туэга вычисления таблиц маршрутизации.
Далее рассмотрен алгоритм Netchange, предложенный Таджибнаписом,и обоснование его корректности, предложенное Лампортом. В заключение описаны алгоритмы компактной маршрутизации, в том числе алгоритмы интервальной и префиксной маршрутизация. Эти алгоритмы маршрутизации называются1.4. Обзор содержания книги51компактными алгоритмами маршрутизации, потому что в каждом узле сети имтребуется совсем немного памяти.Глава 5 завершает обсуждение протоколов для вычислительных сетей.
В нейдается описание стратегий предотвращения блокировки хранения-продвиженияв сетях с пакетной коммутацией пакетов. В основе этих стратегий лежит построение ациклических ориентированных графов на множестве буферов, принадлежащих узлам сети. Читатели узнают, как можно построить такие графы, используясравнительно небольшое число буферов в каждом узле.Вторая часть. Фундаментальные алгоритмы. В этой части книги представлен широкий набор алгоритмических «строительных блоков», которые используются в качестве процедур во многих распределенных прикладных программах,и приведены теоретические результаты, устанавливающие ту роль, которая отводится в вычислениях различным допущениям об устройстве сети.В гл.
6 определяется понятие «волнового алгоритма», представляющего собойобобщенную схему посещения всех узлов сети. При помощи волновых алгоритмов можно распространять информацию по всей сети, проводить синхронизациюее узлов, вычислять функцию, значение которой зависит от информации, распределенной между всеми узлами сети. Как станет ясно из последующих глав, многиезадачи распределенного управления можно решать при помощи алгоритмическихсхем достаточно общего вида, использующих волновой алгоритм в качестве одного из своих компонентов. В этой главе также дается определение сложностипо времени для распределенных алгоритмов и исследуется сложность по времени и по числу обменов сообщениями целого ряда распределенных алгоритмовпоиска в глубину.Одной из фундаментальных проблем, возникающих в распределенных системах, является задача избрания лидера : требуется выбрать один-единственныйпроцесс, которому отводится особая роль в последующем вычислении.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
