Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 14

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 14)

1. Введение: распределенные системыА теперь мы проведем анализ некоторых вариантов устройства процедур управ­ления и оценим, в какой мере эти процедуры способны терять и дублироватьсообщения. Мы будем стараться построить протоколы так, чтобы они в любомслучае позволяли избежать потери сообщений.Диалог с одним сообщением. В самом простом случае NCP А после иници­ализации выполняет только одно действие, которое состоит в том, что А отправ­ляет данные без всяких изменений, уведомляет об этом процесс а и закрываетсеанс связи. В свою очередь, NCP В доставляет полученное сообщение процес­су b и после этого закрывает сеанс связи.

При работе этого протокола потерясообщения происходит всякий раз, когда сеть отказывается доставить сообще­ние по назначению, однако здесь нет никакой возможности для дублированиясообщения.Диалог с двумя сообщениями. Чтобы обезопаситься хотя бы в какой-то ме­ре от потери сообщений, в протокол вводят подтверждения. В ходе нормальногоразвития события NCP А отправляет сообщение с данными (data, т) и ожидаетполучения подтверждающего сообщения (аск) от NCP В. Как только подтвер­ждение будет получено, NCP А закрывает сеанс 19). В свою очередь, NCP В,получив сообщение (data, т ), доставляет информацию т процессу Ь, отправля­ет подтверждающее сообщение (аск) и закрывает сеанс связи.

Таким образом,в этом диалоге, обнаруживающем ошибки, происходят три события.1. NCP A send (data, т)2. NCP В receive (data, т), deliver т, send (ack), close3. NCP A receive (ack), notify, closeВ том случае, если по истечении определенного срока подтверждающее со­общение не будет получено, NCP А, принимая во внимание возможность потерисообщения, отправит сообщение (data, т) повторно. В связи с отсутствием осве­домленности о глобальном состоянии NCP А не имеет сведений о том, было липотеряно сообщение (data, т ), или сообщение (аск), или, быть может, NCP Ввышла из строя после получения сообщения (data, т) и не успела отправитьподтверждение (аск).

Для этого NCP А какое-то время ожидает поступленияподтверждающего сообщения, и если такое сообщение не будет получено, тотаймер обнаружит истечение срока ожидания (события такого рода называюттайм-аутом ). Легко видеть, что вместе со способностью процедуры к повтор­ной передаче сообщения в протокол привносится и возможность дублированиясообщения: это происходит в том случае, когда теряется не исходное сообщение,а подтверждение о его получении.'^Естественно, уведомив об этом процесс а.

— Прим, перев.1.3. Распределенные алгоритмы1.2.3.4.5.6.NCP ANCP ВDNNCP ANCP ВNCP A45send (data, m)receive (data, m), deliver m, send (ack), close(ack) is losttimeout, send (data, m)receive (data, m), deliver m, send (ack), closereceive (ack), notify, closeНо введенные таким образом подтверждения не только приводят к дублиро­ванию сообщений; на самом деле они не способны предохранить от потери со­общения, о чем свидетельствует следующий сценарий. Процесс а намереваетсяпередать две единицы информации т\ и m2 .1. NCP A send (data, tri\)2 .

NCP В receive (data, mi), deliver mi, send (ack), closeNCP A4. NCP В5. NCP A6. NCP A7.DN8. NCP A3.timeout, send (data, mi)receive (data, mi), deliver mi, send (ack), closereceive (ack) (отправленный на шаге 4) notify, closesend (data, m 2 )(data, m 2 ) is lostreceive (ack) (отправленный на шаге 2), notify, closeТак же как и в предыдущем сценарии выполнения протокола, сообщение mi дуб­лируется, но первое подтверждающее сообщение здесь было не потеряно, а всеголишь доставлено с опозданием, и в результате этого второй блок информации т 2был потерян. Замедление передачи сообщения обнаружить невозможно ввидуотсутствия глобальной шкалы времени.Задачу надежной взаимосвязи процессов можно было бы решить гораздо про­ще, если бы в нашем распоряжении имелся ослабленный вариант шкалы гло­бального времени, а именно если бы существовала верхняя оценка Т задержкипередачи всякого сообщения по сети связи.

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

Коль скоро протокол с двумя сообщениямине может предотвратить потерю и дублирование информации в случае потери илизадержки подтверждения, можно ввести в диалог третье сообщение, посредствомкоторого NCP В уведомляется о том, что NCP А уже получила подтверждение.В нормальном случае диалог должен протекать по следующему сценарию.1.NCP A send (data, m)2. NCP В receive (data, m), deliver m, send (ack)3. NCP A receive (ack), notify, send (close), close4.

NCP В receive (close), closeГл. 1. Введение: распределенные системы46Потеря сообщения (data, т) приводит к тайм-ауту в NCP А, и в этом случаеNCP А отправляет сообщение повторно. Потеря сообщения (аск) также при­водит к повторному отправлению сообщения (data, m), но это не приводит кдублированию, потому что NCP В все еще имеет открытый сеанс связи, и поэто­му процедура В способна распознать то сообщение, которое уже было полученоранее.К сожалению, и этот протокол может терять и дублировать информацию.Так как NCP В обязательно должна обладать способностью закрывать сеанссвязи, даже если будет потеряно сообщение (close), NCP В вынуждена переда­вать повторно сообщение (аск), если она не получила сообщение (close).

ТогдаNCP А откликается сообщением о том, что она не участвует в диалоге (сообще­ние (посоп)), и после этого NCP В закрывает сеанс связи. Повторно переданноесообщение (аск) может, однако, возникнуть в следующем сеансе связи NCP А,и оно будет истолковано как подтверждающее сообщение, относящееся к те­кущему сеансу.

В результате та информация, которая передается в этом сеансесвязи, может быть потеряна, о чем свидетельствует следующий сценарий диалогапроцессов.1.2.3.4.5.6.7.8.9.NCP АNCP ВNCP АDNNCP АDNNCP ВNCP АNCP Вsend (data, т i)receive (data, m i), deliver m\, send (ack)receive (ack), notify, send (close), close(close) is lostsend (data, m 2 )(data, m 2 ) is lostretransmit (ack) (для шага 2)receive (ack), notify, send (close), closereceive (close), closeИ вновь мы сталкиваемся с проблемой, поскольку сообщение, относящееся к одному сеансу связи, может перемешиваться с сообщениями, относящимисяк другому сеансу.

Это можно предотвратить путем выбора пары новых сеансовыхидентификационных номеров для каждого нового сеанса связи, один номер дляNCP А, а другой — для NCP В. Выбранные номера включаются в состав всехсообщений, относящихся к этому сеансу связи, и служат для проверки того, чтополученное сообщение относится к текущему сеансу. Нормальная работа прото­кола с тремя сообщениями протекает по следующему сценарию.1.2.3.4.NCPNCPNCPNCPAВAВsend (data, m, х )receive (data, m, х), deliver m, send (аск, х, у)receive (аск, х, у), notify, send (close, х, у), closereceive (close, x, у), closeПри такой модификации протокола с тремя сообщениями ошибочный сеанссвязи, описанный нами ранее, будет исключен, поскольку то сообщение, котороеNCP А получает на шаге 8, не будет считаться подтверждением для сообщенияс данными, отправленного на шаге 5.

Однако NCP В не проверяет правиль­ность сообщения (data, т, х), прежде чем доставляет информацию т (на шаге1.3. Распределенные алгоритмы472) процессу Ь, а это может легко привести к дублированию информации. Еслисообщение, отправленное на шаге 1, было задержано и отправлено повторно, тосообщение (data, т , х ), пришедшее позднее, вынуждает NCP В доставить ин­формацию т процессу b еще раз.Конечно, NCP В также должна проверять правильность сообщений, преждечем доставлять данные процессу.

Мы рассмотрим улучшенный вариант диалогас тремя сообщениями, в ходе которого NCP В доставляет данные на шаге 4, а нена шаге 2. Теперь NCP А отправляет уведомление, п р е ж д е ч е м NCP В доставитсообщение, но ввиду того, что NCP В уже получила переданную информацию, этовполне оправдано. Тем не менее, нужно убедиться, что NCP В будет доставлятьданные в любом случае, и даже тогда, когда сообщение (close, х , у ) может бытьпотеряно. NCP В повторно отправляет сообщение (аск, х , у ) , и на это NCP Аоткликается сообщением (посоп, х , у ) , в результате чего NCP В доставляет ин­формацию процессу b и закрывает сеанс связи, как это видно из следующегосценария.1.2.3.4.5.6.7.NCP АNCP ВNCP АDNNCP ВNCP АNCP Вsend (data, т , х )receive (data, т , х ) , send (ack, х , у )receive (ack, х , у ) , notify, send (close,(close, х, у ) is losttimeout, retransmit (ack, x, y )receive (ack, x, y ) , reply (nocon, x, y )receive (nocon, x, y ) , deliver m , closeх , у ),closeОказывается, для того чтобы избежать потери информации, NCP В должна до­ставлять данные даже тогда, когда NCP А не подтверждает своего участия в се­ансе связи с идентификационными номерами х и у .

Проверка правильности сооб­щений процедурой NCP В становится бесполезной, и это приводит к возможностидублирования информации, как видно из следующего сценария.1.2.3.4.5.6.7.8.NCPNCPNCPNCPNCPNCPNCPNCPААВАВВАВsend (data, т , х )timeout, retransmit (data, т , х )receive (data, т , х ) (отправленное на шаге 2), send (ack, х , у \ )receive (ack, х , у \ ) , notify, send (close, х, г/i), closereceive (close, х , у \ ) , deliver т , closereceive (data, m , x ) (отправленное на шаге 1), send (ack, x , у 2 )receive (ack, x , г/2 ), reply (nocon, x , г/2 )receive (nocon, x , г/2 ) in reply to (ack, x, г/2 ), deliver m , closeДиалог с четырьмя сообщениями.

Доставку той информации, которая от­носилась к предшествующим сеансам связи, можно предотвратить, если процеду­ры управления сетью смогут прийти к договоренности относительно их сеансовыхидентификационных номеров еще до того, как доставлены какие-нибудь данные.Рассмотрим следующий сценарий.Гл. 1.

Введение: распределенные системы481. NCP А2. NCP В3. NCP А4. NCP В5. NCP Аsend (data, т , х)receive (data, т, х ), send (open, т, х, у)receive (open, т, х, у), send (agree, т, х, у)receive (agree, т, х, у), deliver т, send (аск, х, у), closereceive (аск, х, у), notify, closeВ связи с тем, что приходится учитывать возможность выхода из строя NCP В ,исправление ошибок неизбежно будет проводиться так, что дублирование со­общений возникнет даже тогда, когда ни одна из NCP в действительности невыйдет из строя.

NCP В отправляет сообщение об ошибке (посоп, х, у), когдаполучено сообщение (agree, т, х, у), но никакой сеанс связи не открыт. Пред­положим, что NCP А не получает сообщения (аск, х, у) даже после несколькихповторных отправлений сообщения (agree, т, х, у); в ответ приходят только со­общения (посоп, х, у). Поскольку не исключена возможность выхода из строяNCP В перед тем, как она получила сообщение (agree, т, х, у), NCP А вы­нуждена открыть новый сеанс связи (отправив сообщение (data, т, х)), чтобыпредотвратить потерю информации т\ Но ведь NCP В могла с равным успехомуже доставить информацию т, и просто было потеряно сообщение (аск, х, у).В этом случае произойдет дублирование информации.Можно модифицировать наш протокол таким образом, чтобы NCP А отправ­ляла уведомление и закрывала сеанс связи после получения сообщения (посоп, х,это позволит избежать дублирования, но зато становится возможной потеря ин­формации, что еще менее желательно.Диалог с пятью сообщениями и сравнительный анализ.

Характеристики

Список файлов книги