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

Комбинация недостатка знания относительно глобального состояния, недостаток глобального кадра времени, и недетерменизм делает проект распределенных алгоритмов запутанным ремеслом, потому что три аспекта вмешиваются несколькими способами. Понятия времени и состояния очень связаны; в централизованных системах понятие времени может быть определено, рассматривая последовательность состояний, принятых системой в течение выполнения. Даже при том, что в распределенной системе глобальное состояние может быть определено, и выполнение может рассматриваться как последовательность глобальных состояний (Определение 2.2), это представление имеет ограниченное использование, так как выполнение может также быть описано другими последовательностями глобальных состояний (Теорема 2.21). Те альтернативные последовательности обычно состоят из различных глобальных состояний; это придает утверждению "система, принимала это или то состояние в течение выполнения " очень сомнительное значение. Недостаток знания относительно глобального состояния мог бы компенсироваться, если было возможно предсказать это глобальное состояние из алгоритма, который выполняется. К сожалению, это не возможно из-за свойственного недетерменизма в выполнении распределенных систем.

Рис. 1.5 Упрощенная сетевая архитектура

1.3.2 Пример: Связь с одиночным сообщением

Мы проиллюстрируем трудности, налагаемые недостатком знания относительно глобального состояния и недостатка глобального кадра, с помощью примера, обсужденного Beisnes [Bel76l, а именно надежный обмен информацией через ненадежную среду. Рассмотрим два процесса a и b, связанных сетью передачи данных, которая передает сообщения от одного процесса до другого. Сообщение может быть получено в произвольно длительное время после того, как оно послано, оно может также быть потеряно в целом в сети. Надежность связи увеличивается при использовании сетевых процедур управления (NCPs), через который a и b обращаются к сети. Процесс a инициализирует связь, передавая информационный модуль m к NCP A. Взаимодействие между NCPs (через сеть передачи данных, DN) должно гарантировать, что информация m передана в процесс b (NCP B), после которого a уведомляется относительно доставки (через NCP A). Структура связи изображена в Рисунке 1.5. Даже если только одиночный информационный модуль должен транспортироваться от a до b, ненадежность сети вынуждает NCP A и NCP B вовлекаться в сеанс связи, состоящий из нескольких сообщений. Они поддерживают информацию состояния относительно этого сеанса связи, но потому что число возможных партнеров сеанса связи для каждого процесса большое, то требуется, чтобы информация состояния была отброшена после того, как обмен сообщениями завершен. Инициализация информации состояния называется открытие, и ее отбрасывание называется закрытием сеанса связи. Заметьте, что после закрытия сеанса связи, NGP находится в точно том же самом состоянии как и перед открытием его; это называется закрытым состоянием. Информационный модуль m., говорят, потерян, если a получил уведомление от b, но модуль фактически не был никогда передан к b. Модуль m, говорят, дублирован если он был передан дважды. Надежные механизмы связи предотвращают и потери и дублирования. Принимается, что NCPs могут терпеть неудачу, после которой они перезапускаются в закрытом состоянии (действительно теряя всю информацию относительно открытого в настоящее время сеанса связи).

Никакая надежная связь не достижима. Как первое наблюдение, может быть показано, что независимо от того, как запутанно NCPs разработаны, не возможно достигнуть полностью надежной связи. Это наблюдение может быть сделано независимо от проекта сети передачи данных или NCPs и только полагается на предположение, что NCP может терять информацию относительно активного сеанса связи. Чтобы видеть это, предположим, что после того, как инициализация связи a, NCP и NCP В запускает разговор(сеанс связи), в течение которого NCP В доставляет м. b после получения сообщения М. из NCP A. Рассмотрите случай где NCP В сбоями и перезапущен в закрытом состоянии после того, как NCP послал сообщение, м. В этой ситуации, ни NCP ни NCP В не может сообщать, был ли м. уже поставлен, когда NCP В потерпел крах; NCP, потому что это не может наблюдать события в NCP В (недостаток знания относительно глобального состояния) и NCP В, потому что это потерпело крах и было перезапущено в закрытом состоянии. Независимо от того, как NCPs продолжают их разговор(сеанс связи), ошибку можно представлять. Если NCP посылает сообщение NCP В, снова и NCP В доставляет сообщение, дублирование может возникать. Если сообщение к дано без поставки, потеря может возникать. Мы теперь оценим несколько возможных проектов NCPs относительно возможности потери или дублирования сообщений. Мы пробуем разрабатывать протоколы таким способом, которым потерь избегают в любом случае.

Cеанс связи с одним сообщением. В самом простом возможном проекте, NCP А посылает данные, неизменные через сеть, сообщает об этом a, и закрывается, в одиночном действии после инициализации. NCP В всегда доставляет сообщение, которое он получает, к b и закрывается после каждой доставки. Этот протокол представляет потерю всякий раз, когда сеть отказывается доставлять сообщение, но не имеется никакой возможности введения дублирований.

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)