Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 16
Текст из файла (страница 16)
В § 2.5.1 мы определим распределенные вычисления на основе понятия системы переходов, которое приведетнас к понятию достижимой конфигурации и к конструктивному определению множества выполнений, порождаемых алгоритмом. Система становится «распределенной» благодаря тому обстоятельству, что при выполнении каждого переходаприходится иметь дело только с частью конфигурации, а именно с (локальным) состоянием одного процесса (или с локальными состояниями некоторогоподмножества взаимодействующих процессов.)Сама модель определена в § 2.5.1; в § 2.5.2 и 2.5.3 рассматриваются ее основные свойства.
Параграф 2.5.2 посвящен вопросам построения доказательств для55обоснования требуемых свойств заданных распределенных алгоритмов. В § 2.5.3обсуждается такое важное понятие, как отношение причинно-следственной связимежду событиями при выполнении алгоритмов. Это отношение дает возможностьввести отношение эквивалентности на всем множестве выполнений; по определению вычислением в этом случае называется класс эквивалентности выполнений.Определяется понятие часов, и в качестве первого распределенного алгоритмарассматривается алгоритм логических часов.
В заключительном § 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. Системы переходов и алгоритмы2.1.1. Системы переходовСистема переходов состоит из множества всех возможных состояний системы, переходов («действий»), которые система может совершать в этих состояниях, и подмножества состояний, в которых система может пребывать в самом начале. Чтобы не путать состояния отдельных процессов и состояния всегоалгоритма (так называемые «глобальные состояния»), условимся в дальнейшемназывать глобальные состояния конфигурациями.Определение 2.1. Системой переходов называется тройка S = (C , →, I),в которой C — это множество конфигураций, → — двуместное отношение переходов на C , и I — некоторое подмножество множества C , элементы которогоназываются начальными конфигурациями.Отношение переходов — это некоторое подмножество декартова произведения C ×C .
Однако вместо записи ( , ) ∈ → мы будем использовать более удобноеобозначение → .Определение 2.2. Пусть S = (C , →, I) — это система переходов. Выполнением системы S назовем максимальную последовательность E = ( 0 , 1 , 2 , . . .),в которой 0 ∈ I и для каждого i, i > 0, выполняется отношение i → i+1 .Заключительной конфигурацией назовем такую конфигурацию , для которой не существует конфигурации , удовлетворяющей отношению → . Следуетзаметить, что последовательность E = ( 0 , 1 , 2 , .
. .), в которой для каждого iвыполняется отношение i → i+1 , будет максимальной, если она либо являетсябесконечной, либо оканчивается заключительной конфигурацией.внутренними событиями) имеются также события отправления и события приема, которые порождают или изымают сообщения. Обозначим символомM множество всех возможных сообщений; для обозначения совокупности всехмультимножеств с элементами из M будем использовать запись M (M).Определение 2.4. Локальным алгоритмом процесса называется пятерка(Z, I, `i , `s , `r), в которой Z — множество состояний, I — это некоторое подмножество множества Z, элементы которого называются начальными состояниями, `i — отношение на множестве Z × Z, а `s и `r — отношения на множествеZ ×M× Z. Двуместное отношение ` на множестве Z определяется соотношениемc ` d ⇐⇒ (c, d) ∈ `i ∨ ∃m ∈ M ( (c, m, d) ∈ `s ∪ `r ) .Отношения `i , `s и `r представляют переходы между состояниями, связанныесоответственно с внутренними событиями, с событиями передачи сообщений и ссобытиями приема сообщений.
Далее мы будем обозначать процессы буквами p,q, r, p1 , p2 , и т. п., а множество процессов системы будем обозначать буквой P.Определение 2.4 будет служить нам теоретической моделью процессов. В этойкниге при описании алгоритмов мы не будем, конечно, заниматься перечислениемсостояний и событий, а воспользуемся удобным псевдокодом (см.
гл. A). Выполнениями процесса будут называться выполнения системы переходов (Z, `, I).Нас, однако, будут интересовать выполнения всей системы в целом, и в каждом таком выполнении коммуникационная система будет координировать выполнения отдельных процессов. Для того чтобы описать, как осуществляется этакоординация, мы будем рассматривать распределенную систему как систему переходов, в которой множество конфигураций, отношение переходов и начальныесостояния формируются из соответствующих компонентов процессов.Определение 2.5. Распределенным алгоритмом для семейства процессовP = {p1 , . .
. , pN } будет называться совокупность локальных алгоритмов, каждыйиз которых соответствует в точности одному процессу из P.Определение 2.3. Конфигурация считается достижимой из конфигурации (для обозначения этого будем использовать запись), если существуетпоследовательность конфигураций 0 , 1 , 2 , . . . , k , в которой = 0 , k =и для каждого i, 0 6 i < k, выполняется отношение i → i+1 . Всякая конфигурация , достижимая из некоторой начальной конфигурации, будет называтьсяпросто достижимой.572.1.2. Системы с асинхронным обменом сообщениямиРаспределенная система состоит из совокупности процессов и коммуникационной подсистемы. Каждый процесс сам по себе является системой переходов, с тем лишь условием, что он может взаимодействовать с коммуникационнойподсистемой.
Чтобы избежать терминологической путаницы между свойствами,присущими всей распределенной системе в целом, и атрибутами отдельных процессов, мы будем придерживаться следующего соглашения. Термины «переход»и «конфигурация» будут использоваться применительно ко всей распределеннойсистеме в целом, тогда как термины «событие» и «состояние», обозначающиеравносильные понятия, будут использоваться, если речь идет о процессах системы. Чтобы взаимодействовать с коммуникационной подсистемой, в распоряжениипроцесса помимо обычных событий (которые мы в дальнейшем будут называтьПоведение распределенного алгоритма описывается посредством системы переходов следующего вида.
Каждая конфигурация системы определяется состояниями всех процессов, а также совокупностью сообщений, которые еще недостигли адресатов. Переходами являются все события процессов, которые нетолько изменяют состояния самих процессов, но способны как оказывать влияние на совокупность сообщений, так и претерпевать воздействия этой совокупности сообщений. Начальными конфигурациями считаются все те конфигурации,в которых все процессы пребывают в начальных состояниях, а множество сообщений пусто.Определение 2.6. Пусть задано семейство процессов p1 , .
. . , pN и локальный алгоритм каждого процесса pi представлен пятеркой (Zpi , Ipi , `ipi , `spi , `rpi).Тогда будем говорить, что система переходов S = (C , →, I) порождена распределенным алгоритмом для семейства асинхронно взаимосвязанных процессов p1 , . . . , pN , если выполнены следующие соотношения:1) C = { (cp1 , . . . , cpN , M) : (∀p ∈ P : cp ∈ Zp) и M ∈ M (M) };58Гл.
2. Модель2) → = (∪p∈P →p), где символом →p обозначены переходы, соответствующие изменениям состояния процесса p; иначе говоря, → pi — это множество всех пар вида(cp1 , . . . , cpi , . . . , cpN , M1), (cp1 , . . . , c0pi , . . . , cpN , M2),для которых выполняется одно из трех условий:• (cpi , c0pi) ∈ `ipi и M1 = M2 ;• для некоторого сообщения m ∈ M имеется событие (c pi , m, c0pi) ∈ `spi ,и при этом M2 = M1 ∪ {m};• для некоторого сообщения m ∈ M имеется событие (c pi , m, c0pi) ∈ `rpi ,и при этом M1 = M2 ∪ {m};4) I = { (cp1 , .
. . , cpN , M) : (∀p ∈ P : cp ∈ Ip) ∧ M = ∅}.Выполнением распределенного алгоритма будет называться всякое выполнение системы переходов, порожденной этим алгоритмом. Чтобы иметь возможность явно описывать события того или иного выполнения, мы введем следующие обозначения. Пары (c, d) ∈ `ip будем называть (возможными) внутреннимисобытиями процесса p, а тройки, из которых состоят отношения ` sp и `rp , будем называть событиями отправления и приема (сообщения) соответствующимпроцессом.• Внутреннее событие e процесса p, представленное парой e = (c, d), считается допустимым в конфигурации = (cp1 , . .
. , cp , . . . , cpN , M), если cp == c. Тогда запись e( ) будет обозначать конфигурацию (c p1 , . . . , d, . . . , cpN , M).• Событие e отправления сообщения процессом p, представленное тройкой=(c, m, d), считается допустимым в конфигурацииe= (cp1 , . . . , cp , . . . , cpN , M), если cp = c. Тогда запись e( ) будет обозначать конфигурацию (cp1 , . . . , d, . . . , cpN , M ∪ {m}).• Событие e приема сообщения процессом p, представленное тройкой e ==(c, m, d),считаетсядопустимымвконфигурации= (cp1 , . .
. , cp , . . . , cpN , M), если cp = c и m ∈ M. Тогда запись e( )будет обозначать конфигурацию (cp1 , . . . , d, . . . , cpN , M \ {m}).Предполагается, что для каждого сообщения имеется единственный процесс,который может получать это сообщение. Этот процесс будем называть адресатом данного сообщения.2.1.3. Системы с синхронным обменом сообщениямиОбмен сообщениями называется синхронным, если событие отправления сообщения и соответствующее ему событие приема сообщения скоординированытак, что образуют единый переход в системе. Иначе говоря, процессу не дозволено отправлять сообщение, до тех пор пока адресат этого сообщения не будетготов к его приему.
В соответствии с этим переходы в системе разделяются надва типа: переходы первого типа связаны с изменением внутренних состоянийпроцесса, а переходы второго типа связаны с комбинированным осуществлениемсобытий отправления-приема сообщения двумя процессами.2.1. Системы переходов и алгоритмы59Определение 2.7. Пусть задано семейство процессов p1 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
