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

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

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

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

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

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

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

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

распознавание (процессами непосредственно) того, что распределенное

вычисление завершено. Эта проблема изучается в Главе 8. Нижняя граница

Страницы: 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