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

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 и другие.

Вторая фундаментальная проблема - обнаружение завершения, распознавание (процессами непосредственно) того, что распределенное вычисление завершено. Эта проблема изучается в Главе 8. Нижняя граница сложности решения этой проблемы доказана, и несколько алгоритмов обсуждены подробно. Глава включает некоторые классические алгоритмы (например., Dijkstra, Feijen, и Van Gasteren и Dijkstra и Scholten) и снова конструкция дана для получения алгоритмов для этой проблемы из волновых алгоритмов.

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

Глава 10 объясняет, как процессы системы могут вычислять глобальное "изображение", снимок состояния системы. Такой кадр полезен для определения свойств вычисления, типа того, произошел ли тупик, или как далеко вычисление прогрессировало.

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

Часть 3: Отказоустойчивость. В практических распределенных системах возможность сбоя в компоненте не может игнорироваться, и следовательно важно изучить, как хорошо алгоритм ведет себя, если компоненты терпят неудачу. Этот предмет будет обрабатываться в последней части книги; короткое введение в предмет дано в Главе 12. Отказоустойчивость асинхронных систем изучается в Главе 13. Результат Fischer и других обеспечен; показывается, что детерминированные асинхронные алгоритмы не могут справляться с даже очень скромным типом сбоя, аварийным отказом одиночного процесса. Будет также показано, что с более слабыми типами неисправностей можно иметь дело, и что некоторые задачи являются разрешимыми несмотря на сбой типа аварийного отказа. Алгоритмы Bracha и Toueg будут обеспечены: оказывается, напротив, рандомизированные асинхронные системы, способны справиться с приемлемо большим количеством сбоев. Таким образом замечено, что имеет место для надежных систем (см. Главу 9), рандомизированные алгоритмы предлагают большее количество возможностей чем детерминированные алгоритмы.