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

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

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

В заключительном §2.4 обсужда­ются понятия и обозначения, оставшиеся за пределами базовой модели.2.1. Системы переходов и алгоритмыОбычно системы, состояния которых изменяются дискретными шагами (этишаги называются переходами или событиями), удобно описывать с привлечени­ем понятия системы переходов. При изучении распределенных алгоритмов этопонятие применяется как ко всей распределенной системе в целом, так и к от­дельным процессам, которые взаимодействуют в алгоритме. Поэтому концепциясистемы переходов очень важна при изучении распределенных алгоритмов, и ееопределению посвящен §2.1.1.В распределенных системах переходы оказывают влияние только на частьконфигурации (глобального состояния системы). Каждая конфигурация пред­ставляется некоторым кортежем, и в каждом переходе задействованы тольконекоторые компоненты этого кортежа.

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

На­ше изложение не будет столь всеобъемлющим, и мы ограничимся рассмотрени­ем только таких распределенных систем, в которых процессы взаимодействуютпосредством обменов сообщениями. Распределенные системы, в которых взаи­модействие достигается с использованием разделяемых переменных, будут рас­смотрены в гл. 17.

Читатель, интересующийся взаимодействием посредством раз­деляемых переменных, может обратиться к замечательной работе Дейкстры [60]или к работе Овицкого и Гриса [155]; из недавних работ по этой теме можновыделить книгу Аттьи и Велча [12].В распределенных системах сообщения могут передаваться либо синхронно,либо асинхронно. В этой книге основное внимание уделено алгоритмам для си­стем, в которых сообщения передаются асинхронно. Как было показано в работеЧаррона-Боста и его коллег [48], во многих случаях синхронный обмен сооб­щениями можно рассматривать как специальную разновидность асинхронногообмена сообщениями. В §2.1.2 дано строгое описание модели асинхронного об­мена сообщениями; в §2.1.3 эта модель адаптирована к системам, использующимсинхронный обмен сообщениями.

В §2.1.4 мы кратко обсудим такое явление, каксправедливость.56Гл. 2. Модель2.1.1. Системы переходовСистема переходов состоит из множества всех возможных состояний систе­мы, переходов («действий»), которые система может совершать в этих состо­яниях, и подмножества состояний, в которых система может пребывать в са­мом начале.

Чтобы не путать состояния отдельных процессов и состояния всегоалгоритма (так называемые «глобальные состояния»), условимся в дальнейшемназывать глобальные состояния к о н ф и г у р а ц и я м и .Определение 2.1. С и с т е м о й п е р е х о д о в называется тройка S = (С, — I),в которой С — это множество к о н ф и г у р а ц и й , —*•— двуместное о т н о ш е н и е п е ­р е х о д о в на С, и I — некоторое подмножество множества С, элементы которогоназываются н а ч а л ь н ы м и к о н ф и г у р а ц и я м и .Отношение переходов — это некоторое подмножество декартова произведе­ния С х С .

Однако вместо записи (у, 8)6 —*• мы будем использовать более удобноеобозначение у —» 8.Определение 2.2. Пусть S = (С, — I ) — это система переходов. В ы п о л н е ­системы S назовем максимальную последовательность Е = (уо, y i, уг, • • •),в которой у0 € 1 и для каждого /, / > 0, выполняется отношение у,- —*• y,+i .ниемЗ а к л ю ч и т е л ь н о й конфигурацией назовем такую конфигурацию у, для кото­рой не существует конфигурации 8, удовлетворяющей отношению у —*• 8. Следуетзаметить, что последовательность Е = (уо, yi, уг, . . .), в которой для каждого iвыполняется отношение у; —>y,+i, будет максимальной, если она либо являетсябесконечной, либо оканчивается заключительной конфигурацией.Определение 2.3.

Конфигурация 8 считается д о с т и ж и м о й и з конфигура­ции у (для обозначения этого будем использовать запись у8), если существуетпоследовательность конфигураций у о , yi, уг, ■■■, J k , в которой у = уо, у* = 8и для каждого i, 0 ^ i < k, выполняется отношение у; —> у;+ь Всякая конфи­гурация 8, достижимая из некоторой начальной конфигурации, будет называтьсяпросто достижимой.2.1.2. Системы с асинхронным обменом сообщениямиРаспределенная система состоит из совокупности процессов и к о м м у н и к а ­подсистемы.

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

Чтобы взаимодействовать с коммуникационной подсистемой, в распоряжениипроцесса помимо обычных событий (которые мы в дальнейшем будут называтьционной2.1. Системы переходов и алгоритмы57внутренними событиями) имеются также события отправления и собы­тия приема , которые порождают или изымают сообщения. Обозначим символомМ множество всех возможных сообщений; для обозначения совокупности всехмультимножеств с элементами из М будем использовать запись М(Л4).Определение 2.4.

Локальным алгоритмом процесса называется пятерка(Z, /, Р , Р , К ) , в которой Z — множество состояний, / — это некоторое под­множество множества Z, элементы которого называются начальными состоя­ниями, Р — отношение на множестве Z х Z, а И и К — отношения на множествеZ х Л4 х Z. Двуместное отношение Ь на множестве Z определяется соотношениемс Ь d <*=>■ (с, cf)€ РV З т е Л 4 ((с, m, d)€ Р U К ) .Отношения Рг, Ps и Р представляют переходы между состояниями, связанныесоответственно с внутренними событиями, с событиями передачи сообщений и ссобытиями приема сообщений. Далее мы будем обозначать процессы буквами р,q, г, р\, р 2 , и т.

п., а множество процессов системы будем обозначать буквой Р.Определение 2.4 будет служить нам теоретической моделью процессов. В этойкниге при описании алгоритмов мы не будем, конечно, заниматься перечислениемсостояний и событий, а воспользуемся удобным псевдокодом (см. гл. А). Выпол­нениями процесса будут называться выполнения системы переходов (Z, р /).Нас, однако, будут интересовать выполнения всей системы в целом, и в каж­дом таком выполнении коммуникационная система будет координировать выпол­нения отдельных процессов. Для того чтобы описать, как осуществляется этакоординация, мы будем рассматривать распределенную систему как систему пе­реходов, в которой множество конфигураций, отношение переходов и начальныесостояния формируются из соответствующих компонентов процессов.Определение 2.5. Распределенным алгоритмом для семейства процессовР = {р 1 , .

. . , Pn } будет называться совокупность локальных алгоритмов, каждыйиз которых соответствует в точности одному процессу из Р.Поведение распределенного алгоритма описывается посредством системы пе­реходов следующего вида. Каждая конфигурация системы определяется состо­яниями всех процессов, а также совокупностью сообщений, которые еще недостигли адресатов. Переходами являются все события процессов, которые нетолько изменяют состояния самих процессов, но способны как оказывать влия­ние на совокупность сообщений, так и претерпевать воздействия этой совокуп­ности сообщений. Начальными конфигурациями считаются все те конфигурации,в которых все процессы пребывают в начальных состояниях, а множество сооб­щений пусто.Определение 2.6.

Пусть задано семейство процессов р\, ... , рм и локаль­ный алгоритм каждого процесса pi представлен пятеркой (ZPi, IPi, \-lp., b*., \-p.).Тогда будем говорить, что система переходов S = (С, — I ) порождена распре­деленным алгоритмом для семейства асинхронно взаимосвязанных про­цессов р 1, . . . , рх, если выполнены следующие соотношения:1) С = {{сРх,cPN, М) : (Vp е Р : ср € Zp) и М е М(А4)};58Гл. 2. Модель2) —*• = (Upep —»р), где символом —*>р обозначены переходы, соответствую­щие изменениям состояния процесса р; иначе говоря, ~^Pi — это множе­ство всех пар видаОcP i , •••> с Р п ■■■> c P n ' M i ) ,(cPi> •••> c p i > •••> c p n > ^ 2 ) .для которых выполняется одно из трех условий:• (cPi, 4_)е Ьф.

и Mi = М2;• для некоторого сообщения т Е М имеется событиеи при этом М 2 = M i U { т } \• для некоторого сообщения т Е М имеется событиеи при этом М 1 = М 2 U { т } \4) I = {(сР1, . . . , cPN, М ) : (Ур € Р : ср Е I p ) А М = 0}.(сРп т , ср.)Е1-*.,(сРп т , ср.)Е \-р .,Выполнением распределенного алгоритма будет называться всякое выполне­ние системы переходов, порожденной этим алгоритмом.

Чтобы иметь возмож­ность явно описывать события того или иного выполнения, мы введем следую­щие обозначения. Пары (с, d ) E \~1р будем называть (возможными) в н у т р е н н и м исобытиями процесса р , а тройки, из которых состоят отношения Ь* и \-г бу­дем называть событиями о т п р а в л е н и я и п р и е м а (сообщения) соответствующимпроцессом.• Внутреннее событие е процесса р , представленное парой е = (с, d ), счита­ется д о п у с т и м ы м в конфигурации у = (с Р1, .

. . , ср , . . . , cPN, М ), если ср == с. Тогда запись е ( у ) будет обозначать конфигурацию (сР1, . . . , d , . . . , cPN,• Событие е отправления сообщения процессом р , представленное тройкойе=(с, т , d ),считаетсядопуст им ы мв конфигурацииу = (Ср!, . .. , ср, ... , cPN, М), если ср = с. Тогда запись е(у) будет обозна­чать конфигурацию (сР1, . . . , d, . . . , cPN, М U { т } ) .• Событие е приема сообщения процессом р, представленное тройкой е ==(с, т, d ),считаетсядопустимымвконфигурацииу = (Сррср,, сРы, М), если ср = с и т Е М. Тогда запись е { у )будет обозначать конфигурацию (сР1, . .. , d, .

.. , cPN, М \ {т}).Предполагается, что для каждого сообщения имеется единственный процесс,который может получать это сообщение. Этот процесс будем называть а д р е с а ­т о м данного сообщения.2.1.3. Системы с синхронным обменом сообщениямиОбмен сообщениями называется синхронным, если событие отправления со­общения и соответствующее ему событие приема сообщения скоординированытак, что образуют единый переход в системе. Иначе говоря, процессу не дозво­лено отправлять сообщение, до тех пор пока адресат этого сообщения не будетготов к его приему.

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

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