Предыдущая страница реферата | 9  10  11  12  13  14  15  16  17  18  19 | Следующая страница реферата

Определение 2.2 Пусть S = (C, (, I) это система переходов. Исполнение S это есть максимальная последовательность E = ((0, (1, (2,…), где (0 ( I, и для всех i ( 0, (i ( (i+1.

Терминальная конфигурация это конфигурация (, для которой не существует
( такой, что ( ( (. Нужно помнить, что последовательность E = ((0, (1,
(2,…) с (i ( (i+1 для всех i максимальна, если она либо бесконечна, либо заканчивается в терминальной конфигурации.

Определение 2.3 Конфигурация ( достижима из (, нотация ( ( (, если существует последовательность ( = (0, (1, (2, …, (k = ( c (i ( (i+1 для всех 0 ( i < k. Конфигурация ( достижима, если она достижима из начального состояния.

2.1.2 Системы с асинхронной передачей сообщений

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

Определение 2.4 Локальный алгоритм процесса есть пятерка (Z, I, (i, (s,
(r), где Z это множество состояний, I это подмножество Z начальных состояний, (i это отношение на Z x Z, и (s и (r это отношения на Z x M x
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 служит как теоретическая модель для процессов; конечно, алгоритмы в этой книге не описываются только перечислением их состояний и событий, но также средствами удобного псевдокода (см. приложение А). Исполнения процесса есть исполнения системы переходов (Z, (, I). Нас, однако, будут интересовать исполнения системы целиком, и в таком исполнении исполнения процессов координируются через коммуникационную систему. Чтобы описать координацию, мы определим распределенную систему как систему переходов, где множество конфигураций, отношение перехода, и начальные состояния строятся из соответствующих компонентов процессов.

Определение 2.5 Распределенный алгоритм для набора P = {p1, …, pN} процессов это набор локальных алгоритмов, одного для каждого процесса в P.

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

Определение 2.6 Система переходов, порожденная распределенным алгоритмом для процессов p1, …, pN при асинхронной коммуникации, (где локальный алгоритм для процесса pi это есть (Z, I, (i, (s, (r)), это S =
(C, (, I), где

(1) C = {(cP1, …, cPN, M) : ((p ( P : cp ( Zp) и M ( M(M)}.

(2) ( = ((p(P (p), где (p это переходы соответствующие изменениям состояния процесса p; (Pi это множество пар

(cP1, …, cPi, …, cPN, M1), (cP1, …, c’Pi, …, cPN, M2),

для которых выполняется одно из следующих трех условий:

. (cPi , c’Pi ) ( (iPi и M1 = M2;

. для некоторого m ( M, (cPi , m, c’Pi ) ( (sPi и M2 = M1 ( {m};

. для некоторого m ( M, (cPi , m, c’Pi ) ( (rPi и M1 = M2 ( {m}.

(3) I = {(cP1, …, cPN, M) : ((p ( P : cp ( Ip) ( M = (}.

Исполнение распределенного алгоритма это исполнение его, породившее систему переходов. События исполнения выполняются явно с помощью следующей нотации. Пары (c, d) ( (ip называются (возможными) внутренними событиями процесса p, и тройки в (sp и (rp называются событиями отправки и событиями получения процесса.

. Внутреннее событие е заданное как е = (c, d) процесса p называется применимым в конфигурации ( = (cP1, …, cP, …, cPN, M), если cp = c.

В этом случае, e(() определяется как конфигурация (cP1, …, d, …, cPN, M).

. Событие отправки e, заданное как e = (c, m, d) процесса p называется применимым в конфигурации ( = (cP1, …, cP, …, cPN, M), если cp = c.

В этом случае, e(() определяется как конфигурация (cP1, …, d, …, cPN, M ( {m}).

. Событие получения e, заданное как e = (c, m, d) процесса p называется применимым в конфигурации ( = (cP1, …, cP, …, cPN, M), если cp = c и m ( M. В этом случае, e(() определяется как конфигурация (cP1, …, d, …, cPN, M {m}).

Рекомендуем скачать другие рефераты по теме: педагогические рефераты, реферат машини.



Предыдущая страница реферата | 9  10  11  12  13  14  15  16  17  18  19 | Следующая страница реферата

Поделитесь этой записью или добавьте в закладки