ref (Распределенные алгоритмы), страница 8

В Главе 14 отказоустойчивость синхронных алгоритмов будет изучаться. Алгоритмы Lamport и другие показали, что детерминированные синхронные алгоритмы могут допустить нетривиальные сбои. Таким образом замечено, что, в отличие от случая надежных систем (см Главу 11), синхронные системы предлагают большее количество возможностей чем асинхронные системы. Даже большее число неисправностей может допускаться, если процессы способны "подписаться" на связь к другим процессам. Следовательно, выполнение синхронизма в ненадежной системе больше усложнено, чем в надежном случае. И последний раздел Главы 14 будет посвящен этой проблеме.

Другой подход к надежности, а именно через само-стабилизацию алгоритмов, сопровождается в Главе 15. Алгоритм стабилизируется, если, независимо от начальной конфигурации, он сходится в конечном счете к предназначенному поведению. Некоторая теория относительно стабилизации алгоритмов будет разработана, и ряд алгоритмов стабилизации будет обеспечен. Эти алгоритмы включают протоколы для нескольких алгоритмов графа типа вычисления дерева поиска в глубину (как в Разделе 6.4) и вычисления таблиц маршрутизации (как в Главе 4). Также, стабилизационные алгоритмы для передачи данных (как в Главе 3) были предложены. Это может означать, что все компьютерные сети могут быть выполнены, c использованием стабилизационых алгоритмов.

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

2 Модель

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

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

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

Разделы 2.2 и 2.3 рассматривают следствия и свойства модели, описанной в разделе 2.1. Раздел 2.2 имеет дело с вопросом о том, как могут быть доказаны желаемые свойства данного распределенного алгоритма. В разделе 2.3 обсуждается очень важное понятие, а именно: каузальное отношение между событиями в исполнении. Это отношение вызывает отношение эквивалентности, определенное на исполнениях; вычисление это класс эквивалентности, порожденный этим отношением. Определены часы, и представлены логические часы как первый распределенный алгоритм, обсуждаемый в этой книге. И наконец, в разделе 2.4 будут обсуждаться дальнейшие допущения и нотация, не включенные в основную модель.

2.1 Системы перехода и алгоритмы

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

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

Процессы в распределенной системе сообщаются либо с помощью доступа с разделяемым переменным либо при помощи передачи сообщений. Мы примем более ограниченный взгляд и рассмотрим только распределенные системы, где процессы сообщаются при помощи обмена сообщениями. Распределенные системы, где сообщение производится посредством разделяемых переменных, будут обсуждаться в главе 15. Читатель, интересующийся сообщением посредством разделяемых переменных, может проконсультироваться в поворотной статье Дейкстры [Dij68] или Овицкий и Грайс [OG76].

Сообщения в распределенных системах могут передаваться либо синхронно, либо асинхронно. Основной упор в этой книге делается на алгоритмы для систем, где сообщения передаются асинхронно. Во многих случаях синхронная передача сообщений может рассматриваться как специальный случай асинхронной передачи сообщений, как это было продемонстрировано Чаррон-Бост и др. [CBMT92]. Подраздел 2.1.2 описывает модель асинхронной передачи сообщений точно; в подразделе 2.1.3 модель адаптируется к системам, использующим синхронную передачу сообщений. В подразделе 2.1.4 кратко обсуждается справедливость.

2.1.1 Системы переходов

Система переходов состоит из множества всех возможных состояний системы, переходов («ходов»), которые система совершает в этом множестве, и подмножества состояний, в которых системе позволено стартовать. Чтобы избежать беспорядка между состояниями отдельного процесса и состояниями алгоритма целиком («глобальных состояний»), последние теперь будут называться конфигурациями.

Определение 2.1 Система переходов есть тройка S = (C, , I), где С это множество конфигураций,  это бинарное отношение перехода на C, и I это подмножество С начальных конфигураций.

Отношение перехода это подмножество С х С. Вместо (, )   будет использоваться более удобная нотация   .

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

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

Определение 2.3 Конфигурация  достижима из , нотация   , если существует последовательность  = ₀, ₁, ₂, …, _k =  c _i  _i+1 для всех 0  i < k. Конфигурация  достижима, если она достижима из начального состояния.

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

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

Определение 2.4 Локальный алгоритм процесса есть пятерка (Z, I, ⁱ, ^s, ^r), где Z это множество состояний, I это подмножество Z начальных состояний, ⁱ это отношение на Z x Z, и ^s и ^r это отношения на Z x M x Z. Бинарное отношение  на Z определяется как

c  d  (c, d)  ⁱ  m  M((c, m, d)  ^s  ^r ).

Отношения ⁱ , ^s , ^r соответствуют переходам состояния, соотносящихся с внутренними сообщениями, сообщениями отправки и сообщениями получения, соответственно. Впоследствии мы будем обозначать процессы через p, q, r, p₁, p₂ и т.д., и обозначать множество процессов системы P. Определение 2.4 служит как теоретическая модель для процессов; конечно, алгоритмы в этой книге не описываются только перечислением их состояний и событий, но также средствами удобного псевдокода (см. приложение А). Исполнения процесса есть исполнения системы переходов (Z, , I). Нас, однако, будут интересовать исполнения системы целиком, и в таком исполнении исполнения процессов координируются через коммуникационную систему. Чтобы описать координацию, мы определим распределенную систему как систему переходов, где множество конфигураций, отношение перехода, и начальные состояния строятся из соответствующих компонентов процессов.

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

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

Определение 2.6 Система переходов, порожденная распределенным алгоритмом для процессов p₁, …, p_N при асинхронной коммуникации, (где локальный алгоритм для процесса p_i это есть (Z, I, ⁱ, ^s, ^r)), это S = (C, , I), где

(1) C = {(c_P1, …, c_PN, M) : (p  P : c_p  Z_p) и M  M(M)}.

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

(c_P1, …, c_Pi, …, c_PN, M₁), (c_P1, …, c’_Pi, …, c_PN, M₂),

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

• (c_Pi , c’_Pi )  ⁱ_Pi и M₁ = M₂;

• для некоторого m  M, (c_Pi , m, c’_Pi )  ^s_Pi и M₂ = M₁  {m};

• для некоторого m  M, (c_Pi , m, c’_Pi )  ^r_Pi и M₁ = M₂  {m}.

(3) I = {(c_P1, …, c_PN, M) : (p  P : c_p  I_p)  M = }.

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

• Внутреннее событие е заданное как е = (c, d) процесса p называется применимым в конфигурации  = (c_P1, …, c_P, …, c_PN, M), если c_p = c. В этом случае, e() определяется как конфигурация (c_P1, …, d, …, c_PN, M).

• Событие отправки e, заданное как e = (c, m, d) процесса p называется применимым в конфигурации  = (c_P1, …, c_P, …, c_PN, M), если c_p = c. В этом случае, e() определяется как конфигурация (c_P1, …, d, …, c_PN, M  {m}).

• Событие получения e, заданное как e = (c, m, d) процесса p называется применимым в конфигурации  = (c_P1, …, c_P, …, c_PN, M), если c_p = c и m  M. В этом случае, e() определяется как конфигурация (c_P1, …, d, …, c_PN, M \ {m}).

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