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

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

В свою очередь, NCP B доставляет полученное сообщение процессу b и после этого закрывает сеанс связи. При работе этого протокола потерясообщения происходит всякий раз, когда сеть отказывается доставить сообщение по назначению, однако здесь нет никакой возможности для дублированиясообщения.Диалог с двумя сообщениями. Чтобы обезопаситься хотя бы в какой-то мере от потери сообщений, в протокол вводят подтверждения.

В ходе нормальногоразвития события NCP A отправляет сообщение с данными hdata, mi и ожидаетполучения подтверждающего сообщения hacki от NCP B. Как только подтверждение будет получено, NCP A закрывает сеанс 19) . В свою очередь, NCP B,получив сообщение hdata, mi, доставляет информацию m процессу b, отправляет подтверждающее сообщение hacki и закрывает сеанс связи.

Таким образом,в этом диалоге, обнаруживающем ошибки, происходят три события.1. NCP A send hdata, mi2. NCP B receive hdata, mi, deliver m, send hacki, close3. NCP A receive hacki, notify, closeВ том случае, если по истечении определенного срока подтверждающее сообщение не будет получено, NCP A, принимая во внимание возможность потерисообщения, отправит сообщение hdata, mi повторно.

В связи с отсутствием осведомленности о глобальном состоянии NCP A не имеет сведений о том, было липотеряно сообщение hdata, mi, или сообщение hacki, или, быть может, NCP Bвышла из строя после получения сообщения hdata, mi и не успела отправитьподтверждение hacki. Для этого NCP A какое-то время ожидает поступленияподтверждающего сообщения, и если такое сообщение не будет получено, тотаймер обнаружит истечение срока ожидания (события такого рода называюттайм-аутом). Легко видеть, что вместе со способностью процедуры к повторной передаче сообщения в протокол привносится и возможность дублированиясообщения: это происходит в том случае, когда теряется не исходное сообщение,а подтверждение о его получении.19) Естественно,уведомив об этом процесс a. — Прим.

перев.1.3. Распределенные алгоритмы1.2.3.4.5.6.NCP ANCP BDNNCP ANCP BNCP A45send hdata, mireceive hdata, mi, deliver m, send hacki, closehacki is losttimeout, send hdata, mireceive hdata, mi, deliver m, send hacki, closereceive hacki, notify, closeНо введенные таким образом подтверждения не только приводят к дублированию сообщений; на самом деле они не способны предохранить от потери сообщения, о чем свидетельствует следующий сценарий. Процесс a намереваетсяпередать две единицы информации m1 и m2 .1.2.3.4.5.6.7.8.NCP ANCP BNCP ANCP BNCP ANCP ADNNCP Asend hdata, m1 ireceive hdata, m1 i, deliver m1 , send hacki, closetimeout, send hdata, m1 ireceive hdata, m1 i, deliver m1 , send hacki, closereceive hacki (отправленный на шаге 4) notify, closesend hdata, m2 ihdata, m2 i is lostreceive hacki (отправленный на шаге 2), notify, closeТак же как и в предыдущем сценарии выполнения протокола, сообщение m 1 дублируется, но первое подтверждающее сообщение здесь было не потеряно, а всеголишь доставлено с опозданием, и в результате этого второй блок информации m 2был потерян.

Замедление передачи сообщения обнаружить невозможно ввидуотсутствия глобальной шкалы времени.Задачу надежной взаимосвязи процессов можно было бы решить гораздо проще, если бы в нашем распоряжении имелся ослабленный вариант шкалы глобального времени, а именно если бы существовала верхняя оценка T задержкипередачи всякого сообщения по сети связи. Условия такого рода называются глобальными допущениями о времени, потому что эти допущения приводят к появлению определенных отношений по времени между событиями, происходящимив разных узлах сети (в данном случае между событием отправления сообщенияNCP A и событием получения сообщения NCP B). В рассмотренном нами протоколе получение сообщений, относящихся к более ранним сеансам связи, можнопредотвратить, если NCP A будет закрывать сеанс связи 2T единиц времениспустя после получения последнего сообщения.Диалог с тремя сообщениями. Коль скоро протокол с двумя сообщениямине может предотвратить потерю и дублирование информации в случае потери илизадержки подтверждения, можно ввести в диалог третье сообщение, посредствомкоторого NCP B уведомляется о том, что NCP A уже получила подтверждение.В нормальном случае диалог должен протекать по следующему сценарию.1.2.3.4.NCPNCPNCPNCPABABsend hdata, mireceive hdata, mi, deliver m, send hackireceive hacki, notify, send hclosei, closereceive hclosei, close46Гл.

1. Введение: распределенные системыПотеря сообщения hdata, mi приводит к тайм-ауту в NCP A, и в этом случаеNCP A отправляет сообщение повторно. Потеря сообщения hacki также приводит к повторному отправлению сообщения hdata, mi, но это не приводит кдублированию, потому что NCP B все еще имеет открытый сеанс связи, и поэтому процедура B способна распознать то сообщение, которое уже было полученоранее.К сожалению, и этот протокол может терять и дублировать информацию.Так как NCP B обязательно должна обладать способностью закрывать сеанссвязи, даже если будет потеряно сообщение hclosei, NCP B вынуждена передавать повторно сообщение hacki, если она не получила сообщение hclosei. ТогдаNCP A откликается сообщением о том, что она не участвует в диалоге (сообщение hnoconi), и после этого NCP B закрывает сеанс связи.

Повторно переданноесообщение hacki может, однако, возникнуть в следующем сеансе связи NCP A,и оно будет истолковано как подтверждающее сообщение, относящееся к текущему сеансу. В результате та информация, которая передается в этом сеансесвязи, может быть потеряна, о чем свидетельствует следующий сценарий диалогапроцессов.1.2.3.4.5.6.7.8.9.NCP ANCP BNCP ADNNCP ADNNCP BNCP ANCP Bsend hdata, m1 ireceive hdata, m1 i, deliver m1 , send hackireceive hacki, notify, send hclosei, closehclosei is lostsend hdata, m2 ihdata, m2 i is lostretransmit hacki (для шага 2)receive hacki, notify, send hclosei, closereceive hclosei, closeИ вновь мы сталкиваемся с проблемой, поскольку сообщение, относящееся к одному сеансу связи, может перемешиваться с сообщениями, относящимисяк другому сеансу.

Это можно предотвратить путем выбора пары новых сеансовыхидентификационных номеров для каждого нового сеанса связи, один номер дляNCP A, а другой — для NCP B. Выбранные номера включаются в состав всехсообщений, относящихся к этому сеансу связи, и служат для проверки того, чтополученное сообщение относится к текущему сеансу. Нормальная работа протокола с тремя сообщениями протекает по следующему сценарию.1.2.3.4.NCPNCPNCPNCPABABsend hdata, m, xireceive hdata, m, xi, deliver m, send hack, x, yireceive hack, x, yi, notify, send hclose, x, yi, closereceive hclose, x, yi, closeПри такой модификации протокола с тремя сообщениями ошибочный сеанссвязи, описанный нами ранее, будет исключен, поскольку то сообщение, котороеNCP A получает на шаге 8, не будет считаться подтверждением для сообщенияс данными, отправленного на шаге 5.

Однако NCP B не проверяет правильность сообщения hdata, m, xi, прежде чем доставляет информацию m (на шаге1.3. Распределенные алгоритмы472) процессу b, а это может легко привести к дублированию информации. Еслисообщение, отправленное на шаге 1, было задержано и отправлено повторно, тосообщение hdata, m, xi, пришедшее позднее, вынуждает NCP B доставить информацию m процессу b еще раз.Конечно, NCP B также должна проверять правильность сообщений, преждечем доставлять данные процессу. Мы рассмотрим улучшенный вариант диалогас тремя сообщениями, в ходе которого NCP B доставляет данные на шаге 4, а нена шаге 2. Теперь NCP A отправляет уведомление, прежде чем NCP B доставитсообщение, но ввиду того, что NCP B уже получила переданную информацию, этовполне оправдано.

Тем не менее, нужно убедиться, что NCP B будет доставлятьданные в любом случае, и даже тогда, когда сообщение hclose, x, yi может бытьпотеряно. NCP B повторно отправляет сообщение hack, x, yi, и на это NCP Aоткликается сообщением hnocon, x, yi, в результате чего NCP B доставляет информацию процессу b и закрывает сеанс связи, как это видно из следующегосценария.1.2.3.4.5.6.7.NCP ANCP BNCP ADNNCP BNCP ANCP Bsend hdata, m, xireceive hdata, m, xi, send hack, x, yireceive hack, x, yi, notify, send hclose, x, yi, closehclose, x, yi is losttimeout, retransmit hack, x, yireceive hack, x, yi, reply hnocon, x, yireceive hnocon, x, yi, deliver m, closeОказывается, для того чтобы избежать потери информации, NCP B должна доставлять данные даже тогда, когда NCP A не подтверждает своего участия в сеансе связи с идентификационными номерами x и y.

Проверка правильности сообщений процедурой NCP B становится бесполезной, и это приводит к возможностидублирования информации, как видно из следующего сценария.1.2.3.4.5.6.7.8.NCPNCPNCPNCPNCPNCPNCPNCPAABABBABsend hdata, m, xitimeout, retransmit hdata, m, xireceive hdata, m, xi (отправленное на шаге 2), send hack, x, y 1 ireceive hack, x, y1 i, notify, send hclose, x, y1 i, closereceive hclose, x, y1 i, deliver m, closereceive hdata, m, xi (отправленное на шаге 1), send hack, x, y 2 ireceive hack, x, y2 i, reply hnocon, x, y2 ireceive hnocon, x, y2 i in reply to hack, x, y2 i, deliver m, closeДиалог с четырьмя сообщениями. Доставку той информации, которая относилась к предшествующим сеансам связи, можно предотвратить, если процедуры управления сетью смогут прийти к договоренности относительно их сеансовыхидентификационных номеров еще до того, как доставлены какие-нибудь данные.Рассмотрим следующий сценарий.48Гл.

1. Введение: распределенные системы1.2.3.4.5.NCPNCPNCPNCPNCPABABAsend hdata, m, xireceive hdata, m, xi, send hopen, m, x, yireceive hopen, m, x, yi, send hagree, m, x, yireceive hagree, m, x, yi, deliver m, send hack, x, yi, closereceive hack, x, yi, notify, closeВ связи с тем, что приходится учитывать возможность выхода из строя NCP B,исправление ошибок неизбежно будет проводиться так, что дублирование сообщений возникнет даже тогда, когда ни одна из NCP в действительности невыйдет из строя. NCP B отправляет сообщение об ошибке hnocon, x, yi, когдаполучено сообщение hagree, m, x, yi, но никакой сеанс связи не открыт.