Реферат: Распределенные алгоритмы
Поведение распределенного алгоритма описывается системой переходов, как это объясняется далее. Конфигурация состоит из состояния каждого процесса и набора сообщений в процессе передачи; переходы это события процессов, которые влияют не только на состояние процесса, но также оказывают влияние (или подвергаются таковому) на набор сообщений; начальные конфигурации это конфигурации, где каждый процесс находится в начальном состоянии и набор сообщений пуст.
Определение 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 называется применимым в конфигурации g = (cP1, …, cP, …, cPN, M), если cp = c. В этом случае, e(g) определяется как конфигурация (cP1, …, d, …, cPN, M).
· Событие отправки e, заданное как e = (c, m, d) процесса p называется применимым в конфигурации g = (cP1, …, cP, …, cPN, M), если cp = c. В этом случае, e(g) определяется как конфигурация (cP1, …, d, …, cPN, M È {m}).
· Событие получения e, заданное как e = (c, m, d) процесса p называется применимым в конфигурации g = (cP1, …, cP, …, cPN, M), если cp = c и m Î M. В этом случае, e(g) определяется как конфигурация (cP1, …, d, …, cPN, M \ {m}).
Предполагается, что для каждого сообщения существует уникальный процесс, который может получить сообщение. Этот процесс называется назначением сообщения.
2.1.3 Системы с синхронной передачей сообщений
Говорят, что передача сообщений синхронная, если событие отправки и соответствующее событие получения скоординированы так, чтобы сформировать отдельный переход системы. То есть, процессу не разрешается посылать сообщение, если назначение сообщения не готово принять сообщение. Следовательно, переходы системы делятся на два типа: одни соответствуют изменениям внутренних состояний, другие соответствуют скомбинированным коммуникационным событиям двух процессов.
Определение 2.7 Система переходов, порожденная распределенным алгоритмом для процессов p1, …, pN при синхронной коммуникации, это S = (C, ®, I), где
(1) C = {(cP1, …, cPN) : "p Î P : cp Î Zp}.
(2) à = (ÈpÎP àp) È (Èp,qÎP:p¹q àpq), где
· àPi это множество пар
(cP1,
…, cPi, …, cPN), (cP1, …,
c’Pi, …, cPN),
для которых (cPi , c’Pi ) Î ^iPi ;
· àPiPj это множество пар
(…, cPi, …, cPj , …), (…, c’Pi, …, c’Pj , …),
для которых существует сообщение m Î M такое, что
(cPi , m, c’Pi ) Î ^sPi и (cPj , m, c’Pj ) Î ^rPj .
(3) I = {(cP1, …, cPN) : ("p Î P : cp Î Ip)}.
Некоторые распределенные системы допускают гибридные формы коммуникации; процессы в них имеют коммуникационные примитивы для передачи сообщений как в синхронном так и в асинхронном стиле. Имея две модели, определенные выше, нетрудно разработать формальную модель для этого типа распределенных систем. Конфигурации такой системы включают состояния процессов и набор сообщений в процессе передачи (а именно, асинхронных сообщений). Переходы включают все типы переходов представленных в определениях 2.6 и 2.7.
Синхронизм и его влияние на алгоритмы. Уже было замечено, что во многих случаях синхронная передача сообщений может рассматриваться как специальный случай асинхронной передачи сообщений. Набор исполнений ограничен в случае синхронной передачи сообщений исполнениями, где за каждым событием отправки немедленно следует соответствующее событие приема [CBMT92]. Мы поэтому рассматриваем асинхронную передачу сообщений как более общую модель, и будем разрабатывать алгоритмы в основном для этого общего случая.
Однако, нужно быть внимательным, когда алгоритм, разработанный для асинхронной передачи сообщений исполняется в системе с синхронной передачей сообщений. Пониженный недетерминизм в коммуникационной системе должен быть сбалансирован повышенным недетерминизмом в процессах, в противном случае результатом всего этого может стать тупик.
Мы проиллюстрируем это элементарным примером, в котором два процесса посылают друг другу некоторую информацию. В асинхронном случае, каждый процесс может сначала послать сообщение и впоследствии получает сообщение от другого процесса. Сообщения временно накапливаются в коммуникационной подсистеме между их отправкой и посылкой. В синхронном случае, такого накапливания невозможно, и если оба процесса должны послать их собственные сообщения перед тем как они могут получить сообщение, то никакой передачи вообще не будет. В синхронном случае, один из процессов должен получить сообщение перед тем как другой процесс отправит свое собственное сообщение. Нет нужды говорить, что, если оба процесса должны получить сообщение перед отправкой их собственных сообщений, опять же не будет никакой передачи.
Обмен двумя сообщениями будет иметь место в синхронном случае, только если одно из двух нижеследующих условий выполняется.
(1) Заранее определено, какой из двух процессов будет отправлять первым, и какой процесс будет первым получать. Во многих случаях невозможно сделать такой выбор заранее, потому что это потребует выполнения различных локальных алгоритмов в процессах.
(2) Процессы имеют право недетерминированного выбора либо отправлять сначала, потом принимать, либо получать сначала, потом – посылать. В каждом исполнении один из возможных порядков исполнения будет выбран для каждого процесса, т.е. симметрия нарушается коммуникационной системой.
Когда мы представляем алгоритм для асинхронной передачи сообщений и утверждаем, что алгоритм может также использоваться при синхронной передаче сообщений, добавление этого недетерминизма, который всегда возможен, предполагается неявно.
В некоторых случаях необходимо ограничить поведение системы так называемыми справедливыми исполнениями. Условия справедливости вводят исполнения, где события всегда (или бесконечно часто) применимы, но никогда не встречаются как переход (потому что исполнение продолжается с помощью других применимых событий).
Определение 2.8 Исполнение справедливо в слабом смысле, если нет события применимого в бесконечно многих последовательных конфигурациях без появления в исполнении. Исполнение справедливо в сильном смысле, если нет события применимого в бесконечно многих конфигурациях без появления в исполнении.
Возможно включить условия справедливости в формальную модель явно, как это сделано Манна и Пнули [MP88]. Большинство алгоритмов, с которыми мы имеем дело в этой книге, не полагаются на эти условия; поэтому мы решили не включать их в модель, а устанавливать эти условия явно, когда они используются для конкретного алгоритма или проблемы. Также, существует спор, приемлемо ли включать предположение справедливости в модели распределенных систем. Было выдвинуто утверждение, что предположение справедливости не должны производиться, более того алгоритмы не должны разрабатываться с учетом этих предположений. Дискуссия по некоторым запутанным вопросам, относящимся к предположению справедливости может быть найдена в [Fra86].
2.2 Доказательство свойств систем перехода
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105
