Реферат: Распределенные алгоритмы
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
Снова проблема возникла, потому что сообщения одного сеанса связи сталкивались с другим сеансом связи. Это может быть исключено выбором пары новых чисел идентификации сеанса связи для каждого нового сеанса связи, одно для 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 двумя сообщениями, который может представлять дубликаты, но может быть сделан свободным от потерь, если идентификации сеанса связи добавлены, как мы делали для протокола с тремя сообщениями, можем также использоваться.
Имелось продолжающееся исследование в распределенных алгоритмах в течение последнего двух десятилетий, и значительный прогресс был сделаны особенно в течение 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 модель, которая будет использоваться в большинстве более поздних глав, представляется. Модель является, и достаточно общей, чтобы быть подходящей для разработки и проверки алгоритмов и достаточно плотной для доказательства результатов невозможности. Это основано на понятии систем перехода, для которых правила доказательства свойств безопасности и живости могут быть даны легко. Понятие причинной связи как частичного порядока на событиях вычисления представляется, и определены логические часы.
Страницы: 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, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62
