Реферат: Распределенные алгоритмы

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

Распределенные системы с часами реального времени не удовлетворяют определению 2.6, потому что физические свойства часов синхронизируют изменения состояний в разных процессах. Время идет во всех процессах, и это порождает переходы, которые меняют состояние (а именно, считыванием часов) всех процессов. Оказывается, что эти «глобальные переходы» ужасно меняют  свойства модели. В самом деле, теорема 2.19 больше не действует, если приняты часы реального времени. Распределенные системы с часами реального времени используются на практике, однако, и они будут рассматриваться в этой книге (см. раздел 3.2) и главы 11 и 14.

Алгоритм 2.3 Логические часы Лампорта

(3)  Логические часы Лампорта. Лампорт [Lam78] представил часовую функцию, которая приписывает событию а длину k самой длинной последовательности (е1, …, еk) событий, удовлетворяющей

е1 í е2 í … íеk = a

В самом деле, если а í b, эта последовательность может быть расширена, чтобы показать, что QL(a)  < QL(b). Значение QL может быть вычислено для каждого события распределенным алгоритмом, базируясь на следующих отношениях.

(а) Если а есть внутреннее событие или событие посылки, и а’ – предыдущее событие в том же процессе, то QL(a) = QL(a’) + 1.

(b) Если а – событие получение, а’ – предыдущее событие в том же процессе, и b –событие посылки, соответствующее а, то QL(a) = max(QL(a’), QL(b)) + 1.

В обоих случаях QL(a’) предполагается нулевым, если а – первое событие в процессе.

Чтобы вычислить значения часов распределенным алгоритмом, значение часов последнего события процесса р сохраняется в переменной qр (инициализируемой в 0). Для того, чтобы вычислить значение часов события получения, каждое сообщение m содержит значение часов qm события е, при котором оно было послано. Логически часы Лампорта даны как алгоритм 2.3. Для события е в процессе р, QL(е) есть значение qр сразу же после появления е, т.е. в момент, когда происходит изменение состояния процесса р. Оставлена для упражнения демонстрация того, что с этим определением QL является часами.

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

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

a í b Û Q(а) < Q(b).                                                    (2.1)

Существование конкурирующих событий подразумевает, что область таких часов (множество Х) – не-полностью-упорядоченное множество.

В векторных часах Маттерна [Mat89b] X = NN, т.е. Qv(a) есть вектор длины N. Вектора длины n естественным образом упорядочены векторным порядком, определенным следующим образом:

(а1, …, аn) £v (b1, …, bn) Û "i (1 £ i £ n) : ai £ bi.                               (2.2)

(Векторный порядок отличается от лексикографического порядка, определенного в упражнении 2.5, последний порядок  абсолютен). Часы, определяемые Qv(a) = (а1, …, аN), аi – это число событий е в процессе р1, для которого е í а. Как и часы Лампорта, эта функция может быть вычислена распределенным алгоритмом.

Чаррон-Бост [CB89] показал, что невозможно использовать более короткие векторы (с векторным порядком как в (2.2)). Если события произвольного исполнения из N процессов отображаются на вектора длины n таких, что (2.1) удовлетворяется, то n ³ N.

2.4 Дополнительные допущения, сложность

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

Набор процессов и коммуникационная подсистема также упоминается как сеть. Структура коммуникационной подсистемы часто представляется как граф G = (V, E), в котором вершины – это процессы, и ребра между двумя процессами существуют, если и только если канал существует канал между двумя процессами. Система с однонапрвленными каналами может подобным образом представлена направленными графом. Граф распределенной системы также называется ее сетевой топологией.

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

(1)  Кольца. N-вершинное кольцо – граф на вершинах от v0  до vN-1 c ребрами v0vN-1 (индексы – по модулю N). Кольца часто используются для распределенного управления вычислениями, потому что они просты. Также, некоторые физические сети, такие как Token Rings [Tan88, раздел 3.4], распределяют узлы в кольцо.

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

(3)  Звезды. Звезда на N вершинах имеет одну специальную вершину (центр) и N-1 ребер, соединяющих каждую из N-1 вершин с центром. Звезды используются в централизованных вычислениях, где один процесс действует как контроллер и все другие процессы сообщаются только с этим специальным процессом. Недостатки звездной топологии это узкое место, каким может стать центр и уязвимость такой системы из-за повреждений в центре.

(4)  Клики. Клика – это сеть, в которой ребро существует между любыми двумя вершинами.

(5)  Гиперкубы. Гиперкуб – это граф HCN = (V, E) на N = 2n вершинах. Здесь V – множество битовых строк длины n:

V = {(b0 , ..., bn-1) : bi Î {0, 1}},

и ребро существует между двумя вершинами b и с, тогда и только тогда, когда битовые строки b и с различаются точно на один бит. Имя гиперкуба относится к графическому представлению сети как n-размерного куба, углы которого – вершины.

Рис. 2.4 Примеры часто используемых топологий

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

2.4.2 Свойства каналов

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

(1)  Надежность. Говорят, что канал надежен, когда каждое сообщение, которое посылается в канал принимается точно один раз (обеспечив назначению возможность получить сообщение). Если не утверждается обратное, всегда предполагается в этой книге, что каналы надежны. Это допущение фактически добавляет (слабое) условие справедливости. В самом деле, после того как сообщение послано, получение этого сообщения (в приемлемом для назначения состоянии) применимо.

Канал, который ненадежен, может проявлять коммуникационные сбои, которые могут быть нескольких типов, например, утеря, искажение, дублирование, порождение. Эти сбои могут быть представлены переходами в модели определения 2.6, но эти  переходы не соответствуют изменениям состояния процесса.

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

(2)  Свойство fifo. Говорят, что канал является fifo,  если он соблюдает порядок сообщений, посланных через него. То есть, если р посылает два сообщения m1 и m2 процессу q и отправка m1 происходит раньше в р, чем отправка m2, то получение m1 происходит раньше в q, чем получение m2. Если не утверждается обратное, fifo каналы не будут предполагаться в этой книге.

Fifo каналы могут быть представлены в модели определения 2.6 при помощи замены набора М на множество очередей, одной для каждого канала. Отправка осуществляется добавлением сообщения к концу очереди, и событие получения удаляет сообщение с головы. Когда предполагаются каналы fifo, появляется новый тип коммуникационных сбоев, а именно, переупорядочивание сообщений в канале. Это может быть смоделировано переходом, который обменивает два сообщения в очереди.

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

Более слабое допущение было предложено Ахуджа [Ahu90]. Выталкивающий канал – это канал, который соблюдает порядок только сообщений, для которых это было указано отправителем. Могут быть также определены более сильные допущения. Шипер и др. [SES89] определили каузально упорядоченную доставку сообщений, как описывается далее. Если р1 и р2  посылают сообщения m1 и m2 процессу q в событиях е1 и е2 и е1 í е2 , то q получает m1 перед m2 . Иерархия допущений доставки, состоящая из полного асинхронизма, каузально упорядоченной доставки, fifo, и синхронных коммуникаций, обсуждалась Чаррон-Бостом и др. [CBMT92].

(3)  Емкость канала. Емкость – это число сообщений, которое может передаваться по каналу одновременно. Канал полон в каждой конфигурации, в которой он действительно содержит количество сообщений, равное его емкости. Событие посылки применимо, только если канал не полон.

Определение 2.6 моделирует каналы с неограниченной емкостью, т.е. каналы, которые никогда не наполняются. В этой книге всегда будет предполагаться, что емкость каналов не ограничена.

2.4.3 Допущения реального времени

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

Часы реального времени могут быть встроены при помощи снабжения каждого процесса переменной часов реального времени. Течение реального времени моделируется переходом, который передвигает вперед часы каждого процесса, см. раздел 3.2. Обычно, принимается ограничение на время передачи сообщения (время между отправкой и получением сообщения) вкупе с доступностью часов реального времени. Это ограничение может быть также включено в общую модель системы переходов.

Если не утверждается обратное, допущения реального времени не делаются в этой книге, т.е. мы предполагаем полностью асинхронные системы и алгоритмы. Допущения отсчета времени будут использованы в разделе 3.2, главе 11 и главе 14.

2.4.4 Знания процессов

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

(1)  Топологическая информация. Информация о топологии включает: количество процессов, диаметр графа сети, и топологию графа. Говорят, что сеть имеет чувство направления, если согласующаяся с направлениями разметка ребер в графе известна процессам (см. дополнение Б).

(2)  Идентичность процессов. Во многих алгоритмах требуется, чтобы процессы имели уникальные имена (идентификаторы), и чтобы каждый процесс знал свое собственное имя изначально. Тогда предполагается, что процессы содержат переменную, которая инициализируется этим именем (т.е. различным для каждого процесса). Дальнейшие допущения могут быть сделаны касательно множества, из которого выбираются имена, - что имена линейно упорядочены или  что они (положительные) целые. Если не утверждается обратное, в этой книге всегда будем предполагать, что процессы имеют доступ к их идентификаторам, в этом случае система называется именованной сетью. Ситуации, где это не так (анонимные сети) будут исследованы в главе 9.

(3)  Идентификаторы соседей. Если процессы различаются уникальным именем, то возможно предположить, что каждый процесс знает изначально имена соседей. Это допущение называется знание соседей и, если не утверждается обратное, не будет делаться. Имена процессов могут быть полезными для цели адресации сообщений. Имя назначения сообщения дается, когда сообщение посылается с прямой адресацией. Более сильные допущения состоят в том, что каждый процесс знает весь набор имен процессов. Более слабое допущение состоит в том, что процессы знают о существовании, но не знают имен своих соседей. Прямая адресация не может использоваться в этом случае, и процессы используют локальные имена для их каналов, когда хотят адресовать сообщение, что называется непрямой адресацией. Прямая и непрямая адресация показана на рис. 2.5. Прямая адресация использует идентификатор процесса как адрес, в то время как непрямая адресация процессов р, r и s использует различные имена (а, b и c, соответственно), чтобы адресовать сообщения в назначение q.

Рис. 2.5 Прямая (а) и непрямая (b) адресация

2.4.5 Сложность распределенных алгоритмов

Самое важное свойство распределенного алгоритма – его правильность: он должен удовлетворять требованиям, налагаемым проблемой, что алгоритм

3 Протоколы Связи

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

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

Протоколы, обсуждаемые в этой главе разработаны для различных уровней в иерархии протокола, типа модели OSI (Подраздел 1.2.2). Они включены в эту книгу по различным причинам; первый протокол полностью асинхронный, в то время как второй протокол полагается на правильное использование таймеров. В обоих случаях заостряется внимание на требуемом свойстве безопасности, а именно на том, что приемник получит только правильные данные.

Первый протокол (Раздел 3.1) разработан для обмена данными между двумя станциями, которые имеют прямое физическое соединение (типа телефонной линии), и, следовательно, принадлежит канальному уровню модели OSI. Второй протокол (Раздел 3.2) разработан для использования двумя станциями, которые  связываются через промежуточную сеть (возможно содержащую другие станции и соединяющую станции через различные пути), и этот протокол следовательно принадлежит к транспортному уровню OSI модели. Это различие отражается на  функциональных возможностях, требуемых от протоколов, следующим образом.

(1) Рассматриваемые ошибки. Для двух протоколов будут рассматриваться различные классы ошибок передачи. Сообщения не могут пересекаться при физическом соединении, и они не могут быть продублированы; таким образом, в разделе 3.1 рассматривается только потеря сообщений (об искажении сообщений см. ниже). В сети сообщения могут передаваться различными путями, и, следовательно, пересекаться; также, из-за отказов промежуточных станций сообщения могут быть продублированы или потеряны. В Разделе 3.2 будут рассматриваться потеря, дублирование и переупорядочение сообщений.

(2) Управление соединением. Далее, управление соединением не будет рассматриваться для первого протокола, но будет для второго. Предполагается, что физическое соединение  функционирует непрерывно в течение очень длительного времени, а не открывается и закрывается неоднократно. Для соединений с удаленными станциями это не так. Такое соединение может быть необходимо временно для обмена некоторыми данными, но обычно слишком дорого поддерживать соединение с каждой удаленной станцией неопределенно долго. Следовательно, для второго протокола будет требоваться способность открывать и закрывать соединение.

При рассмотрении первого протокола показывается, что не только механизмы, основанные на таймерах, могут обеспечить требуемые свойства безопасности протоколов передачи данных. Раздел 3.1 служит первым большим примером доказательства свойств безопасности с помощью инструментальных средств, описанных в Разделе 2.2. Многие полагают [Wat81], что правильное использование таймеров и ограничение на время, в течение которого сообщение может передаваться ,  необходимы для безопасного управления соединением. Таким образом, для того, чтобы доказать безопасность протоколов, нужно принимать во внимание роль таймеров в управлении соединением. Раздел 3.2 показывается, как модель распределенных систем (Определение 2.6) может быть расширена до процессов, использующих таймеры, и дает пример этого расширения.

Искажение сообщений. Естественно принять во внимание возможность того, что сообщения могут быть искажены в течение передачи. Содержание сообщения, переданного через физическое соединение, может быть повреждено из-за атмосферных шумов, плохо функционирующих модулей памяти, и т.д. Однако можно предположить, что искажение сообщения может быть обнаружено процессом-получателем, например, посредством контроля четности или более общих механизмов контрольной суммы ( [Tan88, Глава 41). Получение искаженного сообщения затем обрабатывается так, как будто не было получено никакого сообщения, и таким образом, искажение сообщения фактически вызывает его потерю. По этой причине искажение не обрабатывается явно; вместо этого всегда рассматривается возможность потери сообщения.

3.1 Сбалансированный протокол скользящего окна

В этом разделе изучается симметричный протокол, который обеспечивает надежный обмен информацией в обоих направлениях. Протокол взят из [Sch91, Глава 2]. Поскольку он используется для обмена информацией между станциями, которые непосредственно соединены через линию, можно предположить, что каналы имеют дисциплину fifo. Это предположение не используется, однако, до Подраздела 3.1.3, где показано, что числа последовательности, используемые протоколом могут быть ограничены. Протокол представлен в Подразделе 3.1.1, а в Подразделе 3.1.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