Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 23
Текст из файла (страница 23)
Если события произвольного выполнения системы, состоящей из Nпроцессов, отобразить в пространство векторов длины п так, чтобы выполнялосьсоотношение (2.1), то мы неизбежно будем иметь п ^ N .2.4. Дополнительные допущения. СложностьДля изучения последующих глав книги вполне достаточно тех понятий, определения которых были даны в этой главе; на основе разработанной здесь моделибудет проводиться описание алгоритмов, их верификация, а также доказательстваневозможности решения распределенных задач. В последующих главах по меренеобходимости будут использоваться дополнительные обозначения и допущения.В этом параграфе мы обсудим ряд понятий, наиболее широко используемых влитературе, посвященной распределенным алгоритмам.6)Здесь N обозначает количество процессов в рассматриваемой распределенной системе Р(см.
определение 2.5)— Прим, перев.2.4. Дополнительные допущения. Сложность772.4.1. Топология сетиДо сих пор модель коммуникационной подсистемы была представлена у нассовокупностью сообщений, пребывающих на этапе пересылки. Кроме того, былоотмечено, что каждое сообщение имеет в качестве адресата в точности один изпроцессов системы. Однако в общем случае совсем не обязательно, чтобы каждый процесс мог отправлять сообщения любому другому процессу. Напротив, длякаждого процесса определяется подмножество других процессов (они называются соседями этого процесса), которым он может отправлять сообщения.
Еслипроцесс р может отправлять сообщения процессу q, то мы будем говорить, чтомежду процессом р и процессом q имеется канал. Если не оговорено противное, мы будем подразумевать, что каналы являются двунаправленными, т. е. тотже самый канал позволяет процессу q отправлять сообщения в адрес процессар. Канал, который способен поддерживать лишь одностороннюю передачу сообщений от процесса р в адрес процесса q, называется однонаправленным (илиориентированным) каналом от р к q.Совокупность, которую образуют процессы и подсистема коммуникаций, называют также сетью. Структуру коммуникационной подсистемы часто представляют в виде графа G = ( V, Е), вершины которого соответствуют процессам; приэтом ребро между двумя процессами существует в том и только том случае, когдаимеется канал связи между этими двумя процессами.
Подобным же образом система с однонаправленными каналами представляется в виде ориентированногографа. Указанный граф распределенной системы также называется топологиейсети.Использование графов позволяет нам обсуждать устройство коммуникационных систем в терминах теории графов (для ознакомления с соответствующейтерминологией см. гл. Б). Поскольку от топологии сети существенным образомзависят вопросы, связанные с существованием, обликом и сложностью распределенных алгоритмов, предназначенных для решения многих задач, мы бегло ознакомимся с некоторыми наиболее распространенными топологиями (их более подробное описание приведено в гл.
Б). Далее, если не оговорено противное, мыбудем подразумевать, что топология является связной, т. е. между любыми двумявершинами существует путь.1. Кольца. Кольцом размера N называется такой граф, у которого имеетсяN вершин vo, vi,, v n - i и при этом каждая пара вершин щ, yi + 1 (индексацияпроводится по модулю N) соединена ребром.
Ввиду простоты топологии кольцачасто используются в распределенных системах управления. Во многих информационных сетях, наподобие сетей с маркером (Token Ring) [182, §4.3.3], узлысети также образуют кольцо.2. Деревья. Деревом с N вершинами называется связный граф, имеющийN —1 ребро; в этом графе отсутствуют циклы. Применение деревьев в распределенных вычислениях обусловлено тем, что они позволяют проводить вычисленияс небольшими затратами на коммуникацию, и, кроме того, в каждом связномграфе можно выделить подсеть, представляющую собой остовное дерево.78Гл. 2.
Модель3.Звезды. В звезде размера N имеется одна выделенная вершина (она называется центром звезды ) и N —1 ребер, соединяющих центр звезды с каждой изN — 1 оставшихся вершин. Звезды используются при проведении централизованных вычислений, в которых один из процессоров выступает в роли контроллераи все остальные процессы могут взаимодействовать только с этим выделеннымпроцессом. К недостаткам звездной топологии можно отнести эффект «бутылочного горлышка», возникающий в центре, а также уязвимость таких систем поотношению к неисправностям в центре.Рис. 2.4. Примеры наиболее употребительных топологий4.
Клики. Кликой называется сеть, в которой любые две вершины соединеныребром. Это тот самый граф, который неявно подразумевается в случае, когдакаждый процесс может непосредственно взаимодействовать со всеми другимипроцессами; об этом будетговориться в гл. 13— 16.5. Гиперкубы.
Гиперкубом называется граф ЯСдг = (V, Е), имеющий N = 2пвершин. Множество вершин V состоит из всех двоичных строк длины п:V = {(b0 t. . . , b n. i ) : b , e { 0 , 1}},и две вершины б и с соединены ребром в том и только том случае, когда двоичные строки б и с отличаются всего лишь в одном разряде. Своим названием(гиперкуб) эта разновидность графов обязана графическому представлению сетив виде я-мерного единичного куба, в вершинах которого размещаются узлы сети.Примеры сети каждого из перечисленных типов изображены на рис. 2.4. Топология может быть статичной или динамичной.
Статичная топология остается2.4. Дополнительные допущения. Сложность79неизменной на протяжении всего распределенного вычисления. Динамичная топология допускает возможность добавления или изъятия каналов связи междупроцессами (а иногда и самих процессов) по ходу вычисления. Эти изменения топологии можно промоделировать посредством переходов между конфигурациями;для этого достаточно, чтобы в процессах хранилась информация об их соседях(см. гл. 4).2.4.2. Свойства каналовМодель, описанную в §2.1.2, можно уточнить, записывая в конфигурации содержимое каждого канала по отдельности, т.
е. заменяя множество М совокупностью множеств Mpq для каждого (однонаправленного) канала pq. Коль скоромы постулировали, что адресат каждого сообщения определен заранее явным образом, такая модификация не влечет никаких существенных изменений модели.Зато теперь мы можем обсудить некоторые общепринятые допущения относительно взаимосвязи событий отправления и приема сообщений.1.
Надежность. Канал считается надежным, если каждое сообщение отправленное по этому каналу, непременно доставляется адресату и при этом в единственном экземпляре (при условии, что адресат способен осуществить приемэтого сообщения). Если не оговорено противное, в этой книге все каналы будут считаться надежными. На самом деле это допущение приводит к появлениюдополнительного условия (слабой) справедливости: начиная с того момента, когда сообщение было отправлено, прием этого сообщения (адресатом, которыйпребывает в подходящем для приема этого сообщения состоянии) становитсядопустимым событием.Канал, не являющийся надежным, может быть подвержен коммуникационным неисправностям’, существует несколько типов таких неисправностей: потеря, искажение, дублирование, спонтанное порождение.
Эти неисправности могутбыть представлены переходами в модели согласно определению 2.6, но переходытакого рода не приводят к изменению состояний процессов.Потеря сообщения происходит в том случае, когда сообщение отправлено,но никогда не может быть получено; этот эффект можно промоделировать переходом, при котором сообщение изымается из мультимножества М. Искажениесообщения возникает, когда полученное сообщение оказывается отличным от тогосообщения, которое было отправлено; это можно промоделировать при помощиперехода, изменяющего одно сообщение из мультимножества М.
Дублированиесообщения приводит к тому, что сообщения принимаются чаще, чем отправляются; это можно промоделировать посредством перехода, добавляющего в М однуили несколько копий одного и того же сообщения. Спонтанное порождениесообщения происходит в том случае, когда адресат получает сообщение, которое вообще никогда не было отправлено; это моделируется переходом, которыйвставляет некоторое сообщение в мультимножество М.2.
Свойство очередности. Канал, сохраняющий порядок передаваемых понему сообщений, называется очередью. Это означает, что если процесс р отправляет два сообщения т\ и т г в адрес процесса q и при этом отправление80Гл. 2. Модельсообщения т\ происходит раньше чем отправление сообщения m 2 , то получение сообщения т\ также происходит раньше,чем получение сообщения m 2 . Еслине оговорено противное, мы будем полагать, что рассматриваемые в этой книгеканалы не являются очередями.Очереди хорошо согласуются с определением 2.6; их можно легко представить, заменив совокупность сообщений М множеством очередей, по одной длякаждого канала связи.
Отправление сообщения приводит к тому, что это сообщение помещается в конец очереди, а в результате события приема сообщениеизвлекается из начала очереди. Когда возникают очереди, появляется и новыйтип коммуникационных неисправностей, а именно нарушение очередности сообщений в канале; его можно промоделировать с помощью перехода, изменяющегопорядок расположения сообщений в очереди.Иногда случается так, что распределенный алгоритм извлекает определеннуювыгоду из свойства очередности событий в канале; примером тому может служитькоммуникационный протокол, приведенный в §3.3.1.
Воспользовавшись тем, чтопри приеме сообщений соблюдается очередность, можно уменьшить объем информации, который должен передаваться в каждом сообщении. Однако во многихслучаях алгоритм должен быть устроен так, чтобы он функционировал правильно (и эффективно) даже тогда, когда изменяется порядок расположения событийв канале. В общем случае реализация свойства очередности может уменьшитьприсущий вычислению параллелизм, поскольку принимающий процесс долженобеспечить буферизацию сообщений перед их обработкой.
По этой причине мыпредпочли не использовать в этой книге неявного предположения об очередностисообщений.Более слабое предположение было предложено в работе Ахуджи [5]; выровненным каналом называется канал, в котором сохраняется очередность только тех сообщений, которые были особо отмечены при их отправлении. Можно рассмотреть и более сильные допущения. Щипер и др. в работе [172] дали следующее определение передачи сообщений, сохраняющей причинноследственный порядок. Если в процессах р\ и р 2 происходят события е\ и еготправления сообщений т\ и m 2 процессу q и при этом справедливо соотношение е\ -< в2 , то q получает событие т\ раньше, чем событие m 2 .
Иерархияразличных предположений о порядке доставки сообщений, включающая полную асинхронность, передачу с сохранением причинно-следственного порядка,доставку по очереди и синхронную коммуникацию, была исследована в работеЧаррон-Боста и др. [48].3.Пропускная способность каналов. Пропускной способностью канала называется количество сообщений, которые могут одновременно пребыватьв канале на этапе пересылки. Канал считается переполненным в тех конфигурациях, в которых число содержащихся в нем сообщений в точности равно егопропускной способности.
Событие отправления допустимо только в тех случаях,когда канал не является переполненным.В определении 2.6 рассматривается модель, каналы которой имеют неограниченную пропускную способность и никогда не переполняются. В нашей книге2.4. Дополнительные допущения. Сложность81мы всегда будем считать, что пропускная способность каналов является неограниченной.2.4.3. Допущения реального времениВажнейшее свойство рассматриваемых моделей — это, безусловно, их распределенность, т. е.
абсолютная независимость событий, происходящих в разныхпроцессах, о чем свидетельствует теорема 2.19. Это свойство утрачивается, кактолько мы вводим модель в рамки реального времени и придаем процессам способность отсчитывать физическое время (встраиваем в процессы таймер). В самом деле, если истекает реальное время, то оно истекает во всех процессах,и течение времени отражается на часах каждого процесса.В нашу модель можно ввести часы реального времени, снабдив каждый процесс вещественной переменной (часами); течение реального времени моделируется посредством перехода, который продвигает вперед показания часов каждогопроцесса (см. §3.3.2). Наряду с наличием часов реального времени обычно предполагается, что время доставки сообщения (отрезок времени между осуществлением событий отправления и приема сообщения) ограничено.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
