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

состояния (см. Подраздел 2.1.2), а не на выполнении команд, принимаемых из

предписанного набора. Конечно, неизбежно, чтобы там, где мы представили

алгоритмы, требовалась некоторая формальная запись; запись

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

этом подразделе мы описываем некоторые из конструкций, которые можно

наблюдать в фактических языках программирования, разработанных для

распределенных систем. Мы ограничиваемся здесь кратким описанием этих

конструкций; Для большего количества деталей и примеров фактических языков,

которые используют различные конструкции, см., например, Bal [Bal90]. Язык

для программирования распределенных прикладных программ, должен обеспечить

средства, чтобы выразить параллелизм, обрабатывать взаимодействие, и

недетерминизм. Параллелизм, конечно, требуется для программирования

различных узлов системы таким способом, которым узлы выполнят их часть

программы одновременно. Связь между узлами должна также быть поддержана в

соответствии с языком программирования. Недетерминизм необходим, потому что

узел должен иногда быть способен получить сообщение от различных узлов, или

быть способным либо посылать, либо получать сообщение.

Параллелизм. Наиболее соответствующая степень параллелизма в

распределенной прикладной программе зависит от отношения(коэффициента)

между стоимостью связи и стоимостью вычисления. Меньшая степень

параллелизма учитывает более быстрое выполнение, но также и требует

большего количества связи, так, если связь дорога, усиление в

быстродействии вычисления может быть потеряно в дополнительной стоимости

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

где каждый процесс является последовательным объектом с собственным

пространством состояния. Язык может или предлагать возможность статического

определения совокупности процессов или позволять динамическое создание и

завершение процессов. Также возможно выразить параллелизм посредством

параллельных инструкций или в функциональном языке программирования.

Параллелизм не всегда явен в языке; выделение разделов кода в параллельные

процессы может выполняться сложным транслятором.

Связь. Связь между процессами свойственна распределенным системам: если

процессы не связываются, каждый процесс функционирует в изоляции от других

процессов и должен изучаться в изоляции, a не как часть распределенной

системы. Когда процессы сотрудничают в вычислении, связь необходима, если

один процесс нуждается в промежуточном результате, произведенном другим

процессом. Также, синхронизация необходима, потому что вышеупомянутый

процесс должен быть приостановлен, пока результат не доступен. Прохождение

cообщения затрагивает, и связь и синхронизацию; общедоступная память

затрагивает только связь: дополнительная осторожность должна быть

предусмотрена для синхронизации процессов, которые сообщаются c

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

передачу сообщения, доступны операции "посылать" и "получать". Связь

происходит выполнением посылающейся операции в одном процессе

(следовательно названным процессом отправителя) и получающейся операцией в

другом процессе (процесс приемника). Параметры посылающей операции - адрес

приемника и дополнительные данные, формирующие содержание сообщения. Эти

дополнительные данные становятся доступными приемнику, когда получающая

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

операция может быть завершена только после того, как посылающая операция

была выполнена, что и осуществляет синхронизацию. В некоторых языках

получающая операция не доступна явно; вместо этого, процедура или операция

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

синхронное прохождение сообщения, когда посылающая операция завершена

только после выполнения получающей операции.

Другими словами, отправитель блокирован, пока сообщение не было

получено, и имеет место двухсторонняя синхронизация между результатами

приемника и отправителем. Сообщения могут быть посланы двухточечно, то

есть, от одного отправителя на один приемник, или широковещательно, когда

то же самое сообщение получено всеми приемниками. Термин мультиприведение

также используется, чтобы обратиться к сообщениям, которые посланы

совокупности (не обязательно всех) процессов. Несколько более

структурированный примитив связи - удаленный вызов процедуры (RPC). Чтобы

связываться с процессом b, процедура a обращается к процедуре,

представленной в процессе b, посылая параметры процедуры в сообщении; а

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

сообщении. Вариант для прохождения сообщения - использование общедоступной

памяти для связи; один процесс пишет значение переменной, и другой процесс

читает значение. Синхронизация между процессами тяжелее, чтобы ее

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

чем переменная была записана. При использовании примитивов синхронизации

типа семафоров [Dij68] или мониторов [Hoa78], возможно выполнить передачу

сообщения, в среде общедоступных переменных. И наоборот, также возможно

выполнить (виртуальную) общедоступную память в передающей сообщения среде,

но это очень неэффективно.

Недетерменизм. В многих точках в выполнении процесс может быть способен

продолжиться различными способами. Получающая операция часто

недетерминирована, потому что это позволяет получение сообщений от

различных отправителей. Дополнительные способы выражать недетерменизм

основаны на охраняемых командах. Охраняемая команда в наиболее общей форме

- список инструкций, каждый предшествованный булевым выражением (его

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

которых соответствующая защита оценивается истиной. Защита может содержать

получающую операцию, когда она оценивается истиной, если имеется сообщение,

доступное, чтобы быть полученным.

1.3 Распределенные Алгоритмы

Предыдущие разделы дали причины для использования распределенных

компьютерных систем и объяснили характер этих систем; потребность

программировать эти системы возникает как следствие. Программирование

распределенных систем должно быть основано на использовании правильных,

гибких, и эффективных алгоритмов. В этом разделе обсуждается, что

разработка распределенных алгоритмов - ремесло, совершенно различное по

характеру от ремесла, используемого в разработке централизованных

алгоритмов. Распределенные и централизованные системы отличаются по ряду

существенных отношений, обрабатываемых в Подразделе 1.3.1 и иллюстрируемых

в 1.3.2 Подразделе. Распределенное исследование алгоритмов следовательно

развилось как независимое поле научного исследования; см. 1.3.3 Подраздел.

Эта книга предназначена, чтобы представить читателю это поле исследования.

Цели книги и выбора результатов, включенных в книгу установлены в

Подразделе 1.3.4.

1.3.1 Распределенный против Централизованных Алгоритмов

Распределенные системы отличаются от централизованных компьютерных

систем по трем существенным отношениям, которые мы теперь обсуждаем.

(1) Недостаток знания глобального состояния. В централизованных

решениях управление алгоритмом может быть сделано основанным на наблюдениях

состояния системы. Даже при том, что к всему состоянию обычно нельзя

обращаться в одиночной машинной операции, программа может осматривать

переменные один за другим, и принимать решение, в конце концов релевантная

информация будет расценена. Никакие данные не изменяются между проверкой и

решением, и это гарантирует целостность решения. Узлы в распределенной

системе имеют доступ только к их собственному состоянию и не к глобальному

состоянию всей системы. Следовательно, не возможно делать решение

управления основанным на глобальном состоянии. Это имеет место тот факт,

что узел может получать информацию относительно состояния других узлов и

базировать решения управления на этой информации. В отличие от

централизованных систем, факт, что полученная информация является старой,

может стать причиной получения недопустимой информации, потому что

состояние другого узла, возможно, изменилось между посылкой информации

состояния и решения, основанного на этом. Состояние подсистемы связи (то

есть, какие сообщения находятся в транзите в некоторый момент) никогда

непосредственно не наблюдается узлами. Эта информация может только быть

выведена косвенно, сравнивая информацию относительно сообщений, посланных

и полученных узлами. Недостаток глобального кадра времени. События,

составляющие выполнение централизованного алгоритма полностью

упорядочиваются естественным способом их временным появлением; для каждой

пары событий, каждое происходит ранее или позже чем другое. Временное

отношение, вызванное на событиях, составляющих выполнение распределенного

алгоритма - не общее количество; Для некоторых пар событий может иметься

причина для решения, что каждое происходит перед другим, но для других пар

имеет место, что ни одно из событий не происходит перед другим [Lam78].

Взаимное исключение может быть достигнуто в централизованной системе

требующих его, если доступ процесса p к ресурсу начинается позже чем доступ

процесса q, то доступ процесса p начался после того, как доступ процесса q

закончился. Действительно, все такие события (старт и окончание доступа

процессов p и q) полностью упорядочиваются отношением временного

предшествования; в распределенной системе они - не упорядочиваются, и та же

самая стратегия не достаточна. Процессы p и q могут начать обращаться к

ресурсу, в то время как начало одного не предшествует началу другой.

(3) Недетерменизм. Централизованная программа может описывать

вычисления, поскольку они разворачиваются из некоторого ввода

недвусмысленно; имея данную программу и ввод, только одиночное вычисление

возможно. Напротив, выполнение распределенной системы обычно не

-детерминировано, из-за возможных различий в быстродействии выполнения

компонентов системы.

Рассмотрим ситуацию, где процесс сервера может получать запросы из

неизвестного числа процессов пользователя. Сервер не может приостановить

обработку запросов, пока все запросы не были получены, потому что не

известно, сколько сообщений прибудет. Следовательно, каждый запрос должен

быть обработан немедленно, и порядок обработки - порядок, в который запросы

прибывают. Порядок, в котором клиентура посылает их запросы, может быть

известен, но поскольку задержки передачи не известны, запросы могут

прибывать в различном порядке.

Комбинация недостатка знания относительно глобального состояния,

недостаток глобального кадра времени, и недетерменизм делает проект

распределенных алгоритмов запутанным ремеслом, потому что три аспекта

вмешиваются несколькими способами. Понятия времени и состояния очень

связаны; в централизованных системах понятие времени может быть определено,

рассматривая последовательность состояний, принятых системой в течение

выполнения. Даже при том, что в распределенной системе глобальное состояние

может быть определено, и выполнение может рассматриваться как

последовательность глобальных состояний (Определение 2.2), это

представление имеет ограниченное использование, так как выполнение может

также быть описано другими последовательностями глобальных состояний

(Теорема 2.21). Те альтернативные последовательности обычно состоят из

различных глобальных состояний; это придает утверждению "система, принимала

это или то состояние в течение выполнения " очень сомнительное значение.

Недостаток знания относительно глобального состояния мог бы

компенсироваться, если было возможно предсказать это глобальное состояние

из алгоритма, который выполняется. К сожалению, это не возможно из-за

свойственного недетерменизма в выполнении распределенных систем.

[pic]

Рис. 1.5 Упрощенная сетевая архитектура

1.3.2 Пример: Связь с одиночным сообщением

Мы проиллюстрируем трудности, налагаемые недостатком знания

относительно глобального состояния и недостатка глобального кадра, с

помощью примера, обсужденного Beisnes [Bel76l, а именно надежный обмен

информацией через ненадежную среду. Рассмотрим два процесса a и b,

связанных сетью передачи данных, которая передает сообщения от одного

процесса до другого. Сообщение может быть получено в произвольно длительное

время после того, как оно послано, оно может также быть потеряно в целом в

сети. Надежность связи увеличивается при использовании сетевых процедур

управления (NCPs), через который a и b обращаются к сети. Процесс a

инициализирует связь, передавая информационный модуль m к NCP A.

Взаимодействие между NCPs (через сеть передачи данных, DN) должно

гарантировать, что информация m передана в процесс b (NCP B), после

которого a уведомляется относительно доставки (через NCP A). Структура

связи изображена в Рисунке 1.5. Даже если только одиночный информационный

модуль должен транспортироваться от a до b, ненадежность сети вынуждает NCP

A и NCP B вовлекаться в сеанс связи, состоящий из нескольких сообщений. Они

поддерживают информацию состояния относительно этого сеанса связи, но

потому что число возможных партнеров сеанса связи для каждого процесса

большое, то требуется, чтобы информация состояния была отброшена после

того, как обмен сообщениями завершен. Инициализация информации состояния

называется открытие, и ее отбрасывание называется закрытием сеанса связи.

Заметьте, что после закрытия сеанса связи, NGP находится в точно том же

самом состоянии как и перед открытием его; это называется закрытым

состоянием. Информационный модуль m., говорят, потерян, если a получил

уведомление от b, но модуль фактически не был никогда передан к b. Модуль

m, говорят, дублирован если он был передан дважды. Надежные механизмы

связи предотвращают и потери и дублирования. Принимается, что NCPs могут

терпеть неудачу, после которой они перезапускаются в закрытом состоянии

(действительно теряя всю информацию относительно открытого в настоящее

время сеанса связи).

Никакая надежная связь не достижима. Как первое наблюдение, может быть

показано, что независимо от того, как запутанно NCPs разработаны, не

возможно достигнуть полностью надежной связи. Это наблюдение может быть

сделано независимо от проекта сети передачи данных или NCPs и только

полагается на предположение, что NCP может терять информацию относительно

активного сеанса связи. Чтобы видеть это, предположим, что после того, как

инициализация связи a, NCP и NCP В запускает разговор(сеанс связи), в

течение которого NCP В доставляет м. b после получения сообщения М. из NCP

A. Рассмотрите случай где NCP В сбоями и перезапущен в закрытом состоянии

после того, как NCP послал сообщение, м. В этой ситуации, ни NCP ни NCP В

не может сообщать, был ли м. уже поставлен, когда NCP В потерпел крах; NCP,

потому что это не может наблюдать события в NCP В (недостаток знания

относительно глобального состояния) и NCP В, потому что это потерпело крах

и было перезапущено в закрытом состоянии. Независимо от того, как NCPs

продолжают их разговор(сеанс связи), ошибку можно представлять. Если NCP

посылает сообщение NCP В, снова и NCP В доставляет сообщение, дублирование

может возникать. Если сообщение к дано без поставки, потеря может

возникать. Мы теперь оценим несколько возможных проектов NCPs относительно

возможности потери или дублирования сообщений. Мы пробуем разрабатывать

протоколы таким способом, которым потерь избегают в любом случае.

Cеанс связи с одним сообщением. В самом простом возможном проекте, NCP

А посылает данные, неизменные через сеть, сообщает об этом a, и

закрывается, в одиночном действии после инициализации. NCP В всегда

доставляет сообщение, которое он получает, к b и закрывается после каждой

доставки. Этот протокол представляет потерю всякий раз, когда сеть

отказывается доставлять сообщение, но не имеется никакой возможности

введения дублирований.

Cеанс связи с двумя сообщениями. Ограниченная защита против потери

сообщений предлагается добавлением подтверждений к протоколу. В нормальном

сеансе связи, NCP А посылает сообщение данных (данные, m) и ждет получения

сообщения подтверждения (ack) из NCP B. Когда это сообщение получено, NCP А

закрывает сеанс связи. NCP B, после получения сообщения (данные, m),

доставляет m к b, отвечает сообщением (ack), и закрывается. Подводя итоги,

можно сказать, что свободный от ошибок сеанс связи состоит из трех событий.

1. NCP А send (данные, m)

2. NCP B receive (данные, m), deliver m., send (ack), close

3. NCP А receive (ack), notify, close.

Возможность потери сообщения данных вынуждает NCP А посылать (данные,

m) снова, если подтверждение не получено после некоторого времени. (Из-за

недостатка знания относительно глобального состояния, NCP А не может

наблюдать, были ли (данные, m) потеряны, (ack) был потерян, или NCP B

потерпел крах между получением (данные, m) и посылкой (ack).) К этому

моменту, NCP A ждет получения подтверждения в течение ограниченного

количества времени, и если никакое такое сообщение не получено, таймер

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

опция перепередачи представляет возможность дубликата, а именно, если не

первоначальное сообщение данных, а подтверждение было потеряно, как в

следующем сценарии:

1. NCP A send ( data, m)

2. NCP B receive (data, m), deliver m, send (ack), close

3. DN ( ack ) is lost

4. NCP A timeout, send ( data, m)

5. NCP B receive (data, m), deliver m, send (ack), close

6. NCP A receive (ack), notify, close

Но подтверждения представляют не только возможность дубликатов, они

также терпят неудачу, чтобы уберечь против потерь, как следующий сценарий

показывает. Процесс а предлагает два информационных модуля, m1 и m2, для

передачи.

1. NCP A send ( данные, m1 )

2. NCP B receive (данные, m1), deliver m1, send (ack), close

3. NCP A timeout, send ( данные, m1 )

4. NCP B receive (данные, m1), deliver m1, send (ack), close

5. NCP A receive (ack), notify, close

6. NCP A send ( данные, m2)

7. DN ( данные, m2 ) is lost

8. NCP A receive (ack) (step 2), notify, close

Сообщение m1 дублировано как в предыдущем сценарии, но первое

подтверждение было доставлено медленно, а не потеряно, вызывая потерю более

позднего информационного модуля. Медленная доставка не обнаружена из-за

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

может быть решена более легко, если принято слабое понятие глобального

времени, а именно, существует верхняя граница T задержки передачи любого

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

синхронизации, потому что это порождает временное отношение между событиями

в различных узлах (а именно, посылка NCP А и получение NCP B). Получение

сообщений от более ранних сеансов связи может быть предотвращено в этом

протоколе закрытием сеанса связи в NCP А только через 2T после посылки

последнего сообщения.

Cеанс связи с тремя сообщениями. Поскольку протокол с двумя сообщениями

теряет или дублирует информационный модуль, когда подтверждение потеряно

или отсрочено, можно рассматривать добавление третьего сообщения к сеансу

связи для информирования NCP В, что NCP А получил подтверждение. Нормальный

сеанс связи затем состоит из следующих событий.

1. NCP A send (data, m)

2. NCP B receive (data, m), deliver m, send (ack)

3. NCP A receive (ack), notify, send (close), close

4. NCP B receive (close), close

Потеря сообщения (данные, m) вызывает таймаут в NCP A, когда NCP A

повторно передает сообщение. Потеря сообщения (ack) также вызывает

перепередачу (данные, m), но это не ведет к дублированию, потому что NCP В

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

К сожалению, протокол может все еще терять и дублировать информацию.

Потому что NCP В должен быть способен закрыться даже, когда сообщение

(close) потеряно, NCP В должен повторно передать (ack) сообщение, если он

не получает никакого сообщения (close). NCP A отвечает, говоря, что он не

имеет никакого сеанса связи ( сообщение (nocon)), после которого NCP В

закрывается. Перепередача (ack) может прибывать, однако, в следующем сеансе

связи NCP A и интерпретироваться как подтверждение в том сеансе связи,

вызывая тот факт, что следующий информационный модуль будет потерян, как в

следующем сценарии.

1. NCP A send ( data, m1 )

2. NCP B receive (data, m1), deliver m1, send (ack)

3. NCP A receive (ack), notify, send (close), close

4. DN ( close ) is lost

5. NCP A send ( data, m2 )

6. DN ( data, m2) is lost

7. NCP B retransmit (ack) (step 2)

8. NCP A receive (ack), notify, send (close), close

9. NCP B receive (close), close

щК(¶VП¤ёVУб№сХ«№SЧy№Щ®єEЬиЅ^ЮСА›ЬnБЇЧюї?ТѕюПРјС?ЅкХWАҐЪтБ5ЪА‰ХEј„Р‘єMО=ј

=ОЫѕьМтѕ¤Й?јЖЎєVЖb»,ЙXѕ^Н:В?ТpЖXЩјЛІвJТiмkШіу-

Ьхц:ЭсцвЬхПЫ{тґЪрбЩ”мuЧ)еЧСъЪВК?СAЕbК4БГr»

єяІE±« Снова проблема возникла, потому что сообщения одного сеанса связи

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

новых чисел идентификации сеанса связи для каждого нового сеанса связи,

одно для NCP A и одно для NCP B. Выбранные числа включены во все сообщения

сеанса связи, и используются, чтобы проверить, что полученное сообщение

действительно принадлежит текущему сеансу связи. Нормальный сеанс связи

протокола с тремя сообщениями следующий.

1. NCP A send ( data, m, x)

2. NCP B receive ( data, m, x), deliver m, send ( ack, x, у )

3. NCP A receive (ack, x, y), notify, send (close, x, y), close

4. NCP B receive ( close, x, y ), close

Эта модификация протокола с тремя сообщениями исключает ошибочный

сеанс связи, данный ранее, потому что сообщение, полученное NCP A в шаге 8

не принято как подтверждение для сообщения данных, посланного в шаге 5.

Однако, NCP B не проверяет проверку правильности (данные, m, x) перед

доставкой m (в шаге 2), что легко ведет к дублированию информации. Если

сообщение, посланное в шаге 1 отсрочено и перетранслировано, позже

прибывающее сообщение (данные, m, x) заставляет NCP B доставлять

информацию m снова. Конечно, NCP B должен также проверять правильность

сообщений, которые он получает, перед доставкой данных. Мы рассматриваем

модификацию сеанса связи с тремя сообщениями, в котором NCP B доставляет

данные в шаге 4, a не в шаге 2. Уведомление теперь передается от NCP A

перед доставкой от NCP B, но потому что NCP B уже получил информацию, это

кажется оправданным. Должно быть обеспечено, тем не менее, что NCP B теперь

доставит данные в любом случае; в частности когда сообщение (close, x, y)

потеряно. NCP B повторяет сообщение (ack, x, y) , на которое NCP А отвечает

с сообщением (nocon, x, y) , заставляя NCP B доставить и закрыться, как в

следующем сценарии.

1. NCP A send (data,m,x)

2. NCP B receive ( data, m, x ), send ( ack, x, y )

3. NCP A receive (ack,x,y), notify, send (close, x, y), close

4. DN ( close, x, y ) is lost

5. NCP B timeout, retransmit ( ack, x, y )

6. NCP A receive (ack, x, y), reply (nocon, x, y)

7. NCP B receive (nocon, x, y), deliver m, close

Оказалось, чтобы избегать потери информации NCP B должен доставлять

данные, даже если NCP А не подтверждает, что имеет подключение с

идентификаторами x и y. Это делает механизм проверки правильности

бесполезным для NCP B, ведя к возможности дублирования информации как в

следующем сценарии.

1. NCP A send (data, m, x )

2. NCP A timeout, retransmit ( data, m, x)

3. NCP B receive ( data, m, a:) (sent in step 2), send (ack, x,y1 )

4. NCP A receive ( ack, x, y1 ), notify, send { close, x, y1 ),

close

5. NCP B receive (close, x, yi ), deliver m, close

6. NCP B receive (data, m, x ) (sent in step 1), send ( ack, x, у2)

7. NCP A receive ( ack, x, y2), reply { nocon, x, y2)

8. NCP B receive ( nocon, x,y2) in reply to ( ack, x, y2 ), deliver

m, close

Сеанс связи с четырьмя сообщениями. Доставки информации из старых

сеансов связи можно избегать при наличии NCPs, взаимно согласующих их числа

идентификации сеанса связи прежде, чем любые данные будут поставлены, как в

следующем сеансе связи.

1. NCP A send ( data, m, x )

2. NCP B receive ( data, m, x ), send ( open, x, у )

3. NCP A receive ( open, x, у ), send ( agree, x, у )

4. NCP B receive (agree, x, y), deliver m, send (ack, x, y), close

5. NCP A receive (ack, x, y), notify, close

Возможность аварийного отказа NCP В вынуждает обработку ошибок быть

такой, что дубликат может все еще происходить, даже, когда никакой NCP

фактически не терпит крах. Сообщение об ошибках (nocon, x, y) послано NCP В

когда сообщение (agree, x, y) получено, и никакой сеанс связи не открыт.

Предположим, что NCP A не получает сообщение (ack, x, y), даже после

несколько перепередач {agree, x, y) ; только сообщения (nocon, x, y)

получены. Так как возможно, что NCP В потерпел крах прежде, чем он получил

(agree, x, y), NCP вынужден запустить новый сеанс связи (посылая {data, m,

x}) чтобы предотвратить потерю m! Но также возможно, что NCP В уже доставил

m, и сообщение (ack, x, y) было потеряно, тогда появляется дубликат.

Возможно изменить протокол таким образом, что NCP A уведомляет и

закрывается после получения сообщения {nocon, x, y); это предотвращает

дубликаты, но может представлять потерю, которая рассматривается даже менее

желательной.

Сеанс связи c пятью сообщениями и сравнение. Beisnes [Bel76] дает

протокол с пятью сообщениями, который не теряет информацию, и это

представляет дубликаты только, если NCP фактически терпит крах.

Следовательно, это - самый лучший возможный протокол, рассматриваемый в

свете того наблюдения, что никакая надежная связь не является возможной,

ранее в этом подразделе. Из-за чрезмерных накладных расходов (пять

сообщений проходят через NCPs, чтобы передать один информационный модуль),

должно быть подвергнуто сомнению, должен ли протокол с пятью сообщениями

действительно быть предпочтен намного более простому протоколу с двумя

сообщениями. Действительно, потому что даже протокол с пятью сообщениями

может представлять дубликаты (когда сбоят NCP), уровень процесса должны

иметь дело с ними так или иначе. Так получается, что протокол c двумя

сообщениями, который может представлять дубликаты, но может быть сделан

свободным от потерь, если идентификации сеанса связи добавлены, как мы

делали для протокола с тремя сообщениями, можем также использоваться.

1.3.3 Область исследования

Имелось продолжающееся исследование в распределенных алгоритмах в

течение последнего двух десятилетий, и значительный прогресс был сделаны

особенно в течение 80-x. В предыдущих разделах мы указали на некоторые

технические достижения, которые стимулировали исследование в распределенных

алгоритмах, а именно, разработка компьютерных сетей (и глобальных и

локальных) и многопроцессорные компьютеры. Первоначально исследование было

очень нацелено к прикладному применению алгоритмов в глобальных сетях, но в

настоящее время разработаны четкие математические модели, позволяющие

прикладное применение результатов и методов к более широким классам

распределенных сред. Однако, исследование поддерживает плотные связи с

достижениями техники в методах связи, потому что результаты в алгоритмах

часто чувствительны к изменениям в сетевой модели. Например, доступность

дешевых микропроцессоров сделала возможным создать системы с многими

идентичными процессорами, которые стимулировали изучение " анонимных сети "

(см. Главу 9).

Имеются несколько журналов и ежегодных конференций, которые

специализируются на результатах распределенных алгоритмов и распределенных

вычислений. Некоторые другие журналы и конференции не специализируются

исключительно по этому предмету, но тем не менее содержат много публикаций

в этой области. Ежегодный симпозиум по Принципам распределенного вычисления

(PoDC) организовывался каждый год начиная с 1982 до времени записи в

Северной Америке, и слушания изданы Ассоциацией для Вычисления Машин.

Международные Симпозиумы по распределенным алгоритмам (WDAG) были проведены

в Оттаве (1985), Амстердаме (1987), Ницце (1989), Bari (1990), Delphi

(1991), Хайфе (1992), Lausanne (1993), и Terschelling (1994). С 1989,

симпозиумы проводились ежегодно и слушания были изданы Springer-Verlag в

сериях Примечания по лекциям по информатике. Ежегодные симпозиумы на теории

вычисления (SToC) и основ информатики (FoCS) покрывают все фундаментальные

области информатики, и часто несут статьи об распределенном вычислении.

Слушания SToC встреч изданы Ассоциацией для Вычисления Машин, и таковых

FoCS встреч институтом IEEE. Журнал Параллельного и Распределенного

Вычисления (JPDC) и Распределенного Вычисления издает распределенные

алгоритмы регулярно, и делает Письма по обработке информации (IPL).

1.3.4 Иерархическая структура книги

Эта книга была написана со следующими тремя целями в памяти.

(1) Сделать читателя знакомым с методами, которые могут использоваться,

чтобы исследовать свойства данного распределенного алгоритма, анализировать

и решать проблему которая возникает в контексте распределенных систем, или

оценивать качества специфической сетевой модели.

(2) чтобы обеспечить понимание в свойственных возможностях и

невозможности нескольких моделей системы. Воздействие доступности

глобального кадра времени изучается в Разделе 3.2 и в Главах 11 и 14.

Воздействие знания процессами их идентичности изучается в Главе 9.

Воздействие требования завершения процесса изучается в Главе 8. Воздействие

сбоев процесса изучается в части 3.

(3) Представлять совокупность недавнего современного состояния

распределенных алгоритмов, вместе с их проверкой и анализом их сложности.

Где предмет не может обрабатываться в полных подробностях, ссылки к

релевантной научной литературе даны. Материал, собранный в книге разделен в

три части: Протоколы, Фундаментальные Алгоритмы, и Отказоустойчивость.

Часть 1: Протоколы. Эта часть имеет дело с протоколами связи,

используемыми в реализации компьютерных сетей связи и также представляет

методы, используемые в более поздних частях. В Главе 2 модель, которая

будет использоваться в большинстве более поздних глав, представляется.

Модель является, и достаточно общей, чтобы быть подходящей для разработки и

проверки алгоритмов и достаточно плотной для доказательства результатов

невозможности. Это основано на понятии систем перехода, для которых правила

доказательства свойств безопасности и живости могут быть даны легко.

Понятие причинной связи как частичного порядока на событиях вычисления

представляется, и определены логические часы.

В Главе 3 проблема передачи сообщения между двумя узлами

рассматривается. Сначала семейство протоколов для обмена пакетами над

одиночной связью обеспечено, и доказательство правильности, по Schoone,

дано. Также, протокол по Fletcher и Watson рассматривается, правильность

которого полагается на правильное использование таймеров. Обработка этого

протокола показывается, как метод проверки может применяться к протоколам,

основанным на использовании таймеров. Глава 4 рассматривает проблему

маршрутизации в компьютерных сетях. Она сначала представляет некоторую

общую теорию относительно маршрутизации и алгоритма Toueg для вычисления

маршрутизации таблиц. Также обрабатываемый - Netchange алгоритм Tajibnapis

и доказательства правильности для этого алгоритма, данного Lamport. Эта

глава заканчивается компактными алгоритмами маршрутизации, включая интервал

и префиксную маршрутизацию. Эти алгоритмы названы компактными алгоритмами

маршрутизации, потому что они требуют только маленького количества памяти в

каждом узле сети. Обсуждение протоколов для компьютерных сетей

заканчивается некоторыми стратегиями для ухода от тупиков с промежуточным

накоплением в компьютерных сетях с коммутацией пакетов в Главе 5. стратегии

основаны при определении свободных от циклов направленных графов на буферах

в узлах сети, и показано, как такой граф может быть создан, используя

только скромное количество буферов в каждом узле.

Часть 2: Фундаментальные Алгоритмы. Эта часть представляет ряд

алгоритмических "строительных блоков", которые используются как процедуры

во многих распределенных прикладных программах, и разрабатывает теорию

относительно вычислительной мощности различных сетевых предложений. Глава 6

определяет понятие " волновой алгоритм ", который является обобщенной

схемой посещения всех узлов сети. Волновые алгоритмы используются, чтобы

распространить информацию через сеть, синхронизировать узлы, или вычислять

функцию, которая зависит от распространения информации над всеми узлами.

Поскольку это соберется в более поздних главах, много проблем

распределенного управления могут быть решены в соответствии с очень общими

алгоритмическими схемами, в которых волновой алгоритм используется как

компонент. Эта глава также определяет сложность времени распределенных

алгоритмов и исследует время и сложность сообщения ряда распределенных

алгоритмов поиска в глубину.

Фундаментальная проблема в распределенных системах - выбор: Выбор

одиночного процесса, который должен запустить различаемую роль в

последующем вычислении. Эта проблема изучается в Главе 7. Сначала проблема

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

проблемы - O (NlogN) сообщений (на кольце N процессоров). Проблема также

изучается для общих сетей, и некоторые конструкции показываются, к которым

алгоритмы выбора могут быть получены из волновых алгоритмов и алгоритмов

обхода. Эта глава также обсуждает алгоритм для конструкции охвата дерева

Gallager и другие.

Вторая фундаментальная проблема - обнаружение завершения,

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18