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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

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

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

Алгоритм консенсуса.........................................................................................53753753916.4. Реализация детекторов неисправности.....................................................................16.4.1. Синхронные системы: совершенное обнаруж ени е..............................541542Оглавление1116.4.2.

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

54316.5.ГлаваУпражнения к главе 1 6 .................................................................................................17.Стабилизация54454617.1. В в е д е н и е .............................................................................................................................17.1.1. О пределения........................................................................................................17.1.2. Коммуникация в стабилизирующихся с и с т е м а х ......................................17.1.3. Пример Дейкстры: кольцо с м ар кер ам и...................................................54754754955017.2.

Графовые алгоритмы........................................................................................................17.2.1. Ориентация к о л е ц .............................................................................................17.2.2. Максимальное покры тие.................................................................................17.2.3.

Выборы лидера и построение остовных д е р е в ь е в .................................55355355756017.3. Общие методы стабилизации......................................................................................17.3.1. Композиция протоколов....................................................................................17.3.2. Вычисление минимальных п у т е й ..................................................................17.3.3.

Заключительные выводы и обсуж дение......................................................56356357057717.4. Упражнения к главе 1 7 ...................................................................................................577ПриложениеА.Соглаш ения об использовании псевдокода579ПриложениеБ.Графы и сети584Б.1.Определения и термины.................................................................................................Б. 1.1. Неориентированные графы.............................................................................Б. 1.2. Ориентированные г р а ф ы ................................................................................Б.

1.3. Взвешенные графы ............................................................................................Наиболее распространенныевиды графов...............................................................Б.2.1. Кольца....................................................................................................................Б .2.2. Деревья, леса и з в е з д ы ...................................................................................Б .2.3. К л и к и ....................................................................................................................Б .2.4. Решетки и тор ы ..................................................................................................Б .2.5. Гиперкубы..............................................................................................................584584586586587587588590591592Б.З.Восприятие направления..............................................................................................593Б .4.Упражнения к главе Б .................................................................................................597Литература............................................................................................................................................600Предметный у к а за т ел ь ....................................................................................................................615Б .2.ПРЕДИСЛОВИЕВ последние годы все большее внимание уделяется распределенным систе­мам и распределенной обработке информации, и почти в каждом университетеесть хотя бы один курс лекций по разработке распределенных алгоритмов.

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

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

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

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

Я получил также полезные предложения от студентов, посещавших курслекций «Расределенные алгоритмы» в осеннем семестре в Утрехтском универ­ситете. Факультет вычислительной математики снабдил меня всем необходимымдля обработки и печати текстов. Редакторскую работу выполнила Сьюзан Пар­кинсон.ГЛАВА1ВВЕДЕНИЕ: РАСПРЕДЕЛЕННЫЕ СИСТЕМЫВ этой главе объясняется, почему нужно изучать распределенные алгоритмы.Мы начнем с того, что рассмотрим вкратце основные типы электронной аппарату­ры и программного обеспечения, для которых были разработаны распределенныеалгоритмы. Под распределенной системой мы понимаем всякую вычислительнуюсистему, в которой несколько компьютеров или процессоров так или иначе всту­пают во взаимодействие.

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

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

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

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