Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 22
Текст из файла (страница 22)
Θv (a) — это вектор дли6)ны N. Векторы длины n можно естественным образом упорядочить, воспользовавшись следующим отношением покомпонентного сравнения:(a1 , . . . , an) 6v (b1 , . . . , bn) ⇐⇒ ∀i (1 6 i 6 n) : ai 6 bi .(2.2)Введенный таким образом векторный порядок отличен от лексикографическогопорядка, который определен в упражнении 2.5 и является линейным порядком.Значением функции часов является вектор Θv (a) = (a1 , . . .
, aN), в котором ai —это число событий e, произошедших в процессе pi и удовлетворяющих соотношению e a. Подобно часам Лампорта, эта функция может быть вычисленараспределенным алгоритмом.Чаррон-Бост в своей работе [47] показал, что векторами меньшей длины дляэтой цели обойтись невозможно (если порядок на векторах определен соотношением (2.2)). Если события произвольного выполнения системы, состоящей из Nпроцессов, отобразить в пространство векторов длины n так, чтобы выполнялосьсоотношение (2.1), то мы неизбежно будем иметь n > N.2.4. Дополнительные допущения. СложностьДля изучения последующих глав книги вполне достаточно тех понятий, определения которых были даны в этой главе; на основе разработанной здесь моделибудет проводиться описание алгоритмов, их верификация, а также доказательстваневозможности решения распределенных задач.
В последующих главах по меренеобходимости будут использоваться дополнительные обозначения и допущения.В этом параграфе мы обсудим ряд понятий, наиболее широко используемых влитературе, посвященной распределенным алгоритмам.6) Здесь N обозначает количество процессов в рассматриваемой распределенной системе P(см.
определение 2.5) — Прим. перев.772.4.1. Топология сетиДо сих пор модель коммуникационной подсистемы была представлена у нассовокупностью сообщений, пребывающих на этапе пересылки. Кроме того, былоотмечено, что каждое сообщение имеет в качестве адресата в точности один изпроцессов системы. Однако в общем случае совсем не обязательно, чтобы каждый процесс мог отправлять сообщения любому другому процессу. Напротив, длякаждого процесса определяется подмножество других процессов (они называются соседями этого процесса), которым он может отправлять сообщения.
Еслипроцесс p может отправлять сообщения процессу q, то мы будем говорить, чтомежду процессом p и процессом q имеется канал. Если не оговорено противное, мы будем подразумевать, что каналы являются двунаправленными, т. е. тотже самый канал позволяет процессу q отправлять сообщения в адрес процессаp.
Канал, который способен поддерживать лишь одностороннюю передачу сообщений от процесса p в адрес процесса q, называется однонаправленным (илиориентированным) каналом от p к q.Совокупность, которую образуют процессы и подсистема коммуникаций, называют также сетью. Структуру коммуникационной подсистемы часто представляют в виде графа G = (V, E), вершины которого соответствуют процессам; приэтом ребро между двумя процессами существует в том и только том случае, когдаимеется канал связи между этими двумя процессами. Подобным же образом система с однонаправленными каналами представляется в виде ориентированногографа.
Указанный граф распределенной системы также называется топологиейсети.Использование графов позволяет нам обсуждать устройство коммуникационных систем в терминах теории графов (для ознакомления с соответствующейтерминологией см. гл. Б). Поскольку от топологии сети существенным образомзависят вопросы, связанные с существованием, обликом и сложностью распределенных алгоритмов, предназначенных для решения многих задач, мы бегло ознакомимся с некоторыми наиболее распространенными топологиями (их более подробное описание приведено в гл.
Б). Далее, если не оговорено противное, мыбудем подразумевать, что топология является связной, т. е. между любыми двумявершинами существует путь.1. Кольца. Кольцом размера N называется такой граф, у которого имеетсяN вершин v0 , v1 , . . . , vN−1 и при этом каждая пара вершин vi , vi+1 (индексацияпроводится по модулю N) соединена ребром. Ввиду простоты топологии кольцачасто используются в распределенных системах управления. Во многих информационных сетях, наподобие сетей с маркером (Token Ring) [182, § 4.3.3] , узлысети также образуют кольцо.2. Деревья.
Деревом с N вершинами называется связный граф, имеющийN − 1 ребро; в этом графе отсутствуют циклы. Применение деревьев в распределенных вычислениях обусловлено тем, что они позволяют проводить вычисленияс небольшими затратами на коммуникацию, и, кроме того, в каждом связномграфе можно выделить подсеть, представляющую собой остовное дерево.78Гл.
2. Модель2.4. Дополнительные допущения. Сложность3. Звезды. В звезде размера N имеется одна выделенная вершина (она называется центром звезды) и N −1 ребер, соединяющих центр звезды с каждой изN − 1 оставшихся вершин. Звезды используются при проведении централизованных вычислений, в которых один из процессоров выступает в роли контроллераи все остальные процессы могут взаимодействовать только с этим выделеннымпроцессом. К недостаткам звездной топологии можно отнести эффект «бутылочного горлышка», возникающий в центре, а также уязвимость таких систем поотношению к неисправностям в центре.vvv@v@@vv vB B BBvB B BBvvv@@v@vvvКольцоЗвездаvvBBBBvvvaa!!vL !@@La!! L @ aLa@v@!avaa !@LL@@ aLa!! L!L a @ LL @!! aa@La@vaL! @ L!!LvaL!a@ @@L a!L!L.....v!a!a@@LvКликаvvBBBBvДеревоvvvJ JJJvvvvvvvvvГиперкубРис.
2.4. Примеры наиболее употребительных топологий4. Клики. Кликой называется сеть, в которой любые две вершины соединеныребром. Это тот самый граф, который неявно подразумевается в случае, когдакаждый процесс может непосредственно взаимодействовать со всеми другимипроцессами; об этом будетговориться в гл. 13 — 16.5. Гиперкубы. Гиперкубом называется граф HCN = (V, E), имеющий N = 2nвершин. Множество вершин V состоит из всех двоичных строк длины n:V = { (b0 , . . . , bn−1) : bi ∈ {0, 1} },и две вершины b и c соединены ребром в том и только том случае, когда двоичные строки b и c отличаются всего лишь в одном разряде.
Своим названием(гиперкуб) эта разновидность графов обязана графическому представлению сетив виде n-мерного единичного куба, в вершинах которого размещаются узлы сети.Примеры сети каждого из перечисленных типов изображены на рис. 2.4. Топология может быть статичной или динамичной. Статичная топология остается79неизменной на протяжении всего распределенного вычисления. Динамичная топология допускает возможность добавления или изъятия каналов связи междупроцессами (а иногда и самих процессов) по ходу вычисления.
Эти изменения топологии можно промоделировать посредством переходов между конфигурациями;для этого достаточно, чтобы в процессах хранилась информация об их соседях(см. гл. 4).2.4.2. Свойства каналовМодель, описанную в § 2.1.2, можно уточнить, записывая в конфигурации содержимое каждого канала по отдельности, т. е. заменяя множество M совокупностью множеств Mpq для каждого (однонаправленного) канала pq. Коль скоромы постулировали, что адресат каждого сообщения определен заранее явным образом, такая модификация не влечет никаких существенных изменений модели.Зато теперь мы можем обсудить некоторые общепринятые допущения относительно взаимосвязи событий отправления и приема сообщений.1.
Надежность. Канал считается надежным, если каждое сообщение отправленное по этому каналу, непременно доставляется адресату и при этом в единственном экземпляре (при условии, что адресат способен осуществить приемэтого сообщения). Если не оговорено противное, в этой книге все каналы будут считаться надежными. На самом деле это допущение приводит к появлениюдополнительного условия (слабой) справедливости: начиная с того момента, когда сообщение было отправлено, прием этого сообщения (адресатом, которыйпребывает в подходящем для приема этого сообщения состоянии) становитсядопустимым событием.Канал, не являющийся надежным, может быть подвержен коммуникационным неисправностям; существует несколько типов таких неисправностей: потеря, искажение, дублирование, спонтанное порождение.
Эти неисправности могутбыть представлены переходами в модели согласно определению 2.6, но переходытакого рода не приводят к изменению состояний процессов.Потеря сообщения происходит в том случае, когда сообщение отправлено,но никогда не может быть получено; этот эффект можно промоделировать переходом, при котором сообщение изымается из мультимножества M. Искажениесообщения возникает, когда полученное сообщение оказывается отличным от тогосообщения, котoрое было отправлено; это можно промоделировать при помощиперехода, изменяющего одно сообщение из мультимножества M.
Дублированиесообщения приводит к тому, что сообщения принимаются чаще, чем отправляются; это можно промоделировать посредством перехода, добавляющего в M однуили несколько копий одного и того же сообщения. Спонтанное порождениесообщения происходит в том случае, когда адресат получает сообщение, которое вообще никогда не было отправлено; это моделируется переходом, которыйвставляет некоторое сообщение в мультимножество M.2. Свойство очередности.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
