Распределенные алгоритмы (стр. 18 из 85)
(1) Топологическая информация. Информация о топологии включает: количество процессов, диаметр графа сети, и топологию графа. Говорят, что сеть имеет чувство направления, если согласующаяся с направлениями разметка ребер в графе известна процессам (см. дополнение Б).
(2) Идентичность процессов. Во многих алгоритмах требуется, чтобы процессы имели уникальные имена (идентификаторы), и чтобы каждый процесс знал свое собственное имя изначально. Тогда предполагается, что процессы содержат переменную, которая инициализируется этим именем (т.е. различным для каждого процесса). Дальнейшие допущения могут быть сделаны касательно множества, из которого выбираются имена, - что имена линейно упорядочены или что они (положительные) целые. Если не утверждается обратное, в этой книге всегда будем предполагать, что процессы имеют доступ к их идентификаторам, в этом случае система называется именованной сетью. Ситуации, где это не так (анонимные сети) будут исследованы в главе 9.
(3) Идентификаторы соседей. Если процессы различаются уникальным именем, то возможно предположить, что каждый процесс знает изначально имена соседей. Это допущение называется знание соседей и, если не утверждается обратное, не будет делаться. Имена процессов могут быть полезными для цели адресации сообщений. Имя назначения сообщения дается, когда сообщение посылается с прямой адресацией. Более сильные допущения состоят в том, что каждый процесс знает весь набор имен процессов. Более слабое допущение состоит в том, что процессы знают о существовании, но не знают имен своих соседей. Прямая адресация не может использоваться в этом случае, и процессы используют локальные имена для их каналов, когда хотят адресовать сообщение, что называется непрямой адресацией. Прямая и непрямая адресация показана на рис. 2.5. Прямая адресация использует идентификатор процесса как адрес, в то время как непрямая адресация процессов р, r и s использует различные имена (а, b и c, соответственно), чтобы адресовать сообщения в назначение q.
Рис. 2.5 Прямая (а) и непрямая (b) адресация
2.4.5 Сложность распределенных алгоритмов
Самое важное свойство распределенного алгоритма – его правильность: он должен удовлетворять требованиям, налагаемым проблемой, что алгоритм
В этой главе обсуждаются два протокола, которые используются для надежного обмена данными между двумя вычислительными станциями. В идеальном случае, данными бы просто обменивались, посылая и получая сообщения. К сожалению, не всегда можно игнорировать возможность ошибок связи; сообщения должны транспортироваться через физическую среду, которая может терять, дублировать, переупорядочивать или искажать сообщения, передаваемые через нее. Эти ошибки должны быть обнаружены и исправлены дополнительными механизмами, выполняющимися на вычислительных станциях, которые традиционно называются протоколами.
Основная функция этих протоколов - передача данных, то есть, принятие информации на одной станции и получение ее на другой станции. Надежная передача данных включает повторную посылку сообщений, которые потеряны, отклонение или исправление сообщений, которые искажены, и отбрасывание дубликатов сообщений. Для выполнения этих функций протокол содержит информацию состояния, записывая, какие данные уже был посланы, какие данные считаются полученными и так далее. Необходимость использования информации состояния поднимает проблему управления соединением, то есть, инициализации и отбрасывания информации состояния. Инициализация называется открытием соединения, и отбрасывание называется закрытием соединения. Трудности управления соединением возникают из-за того, что сообщение может остаться в каналах связи, когда соединение закрыто. Такое сообщение могло бы быть получено, когда не существует никакого соединения или в течение более позднего соединения, и получение не должно нарушать правильную операцию текущего соединения.
Протоколы, обсуждаемые в этой главе разработаны для различных уровней в иерархии протокола, типа модели OSI (Подраздел 1.2.2). Они включены в эту книгу по различным причинам; первый протокол полностью асинхронный, в то время как второй протокол полагается на правильное использование таймеров. В обоих случаях заостряется внимание на требуемом свойстве безопасности, а именно на том, что приемник получит только правильные данные.
Первый протокол (Раздел 3.1) разработан для обмена данными между двумя станциями, которые имеют прямое физическое соединение (типа телефонной линии), и, следовательно, принадлежит канальному уровню модели OSI. Второй протокол (Раздел 3.2) разработан для использования двумя станциями, которые связываются через промежуточную сеть (возможно содержащую другие станции и соединяющую станции через различные пути), и этот протокол следовательно принадлежит к транспортному уровню OSI модели. Это различие отражается на функциональных возможностях, требуемых от протоколов, следующим образом.
(1) Рассматриваемые ошибки. Для двух протоколов будут рассматриваться различные классы ошибок передачи. Сообщения не могут пересекаться при физическом соединении, и они не могут быть продублированы; таким образом, в разделе 3.1 рассматривается только потеря сообщений (об искажении сообщений см. ниже). В сети сообщения могут передаваться различными путями, и, следовательно, пересекаться; также, из-за отказов промежуточных станций сообщения могут быть продублированы или потеряны. В Разделе 3.2 будут рассматриваться потеря, дублирование и переупорядочение сообщений.
(2) Управление соединением. Далее, управление соединением не будет рассматриваться для первого протокола, но будет для второго. Предполагается, что физическое соединение функционирует непрерывно в течение очень длительного времени, а не открывается и закрывается неоднократно. Для соединений с удаленными станциями это не так. Такое соединение может быть необходимо временно для обмена некоторыми данными, но обычно слишком дорого поддерживать соединение с каждой удаленной станцией неопределенно долго. Следовательно, для второго протокола будет требоваться способность открывать и закрывать соединение.
При рассмотрении первого протокола показывается, что не только механизмы, основанные на таймерах, могут обеспечить требуемые свойства безопасности протоколов передачи данных. Раздел 3.1 служит первым большим примером доказательства свойств безопасности с помощью инструментальных средств, описанных в Разделе 2.2. Многие полагают [Wat81], что правильное использование таймеров и ограничение на время, в течение которого сообщение может передаваться , необходимы для безопасного управления соединением. Таким образом, для того, чтобы доказать безопасность протоколов, нужно принимать во внимание роль таймеров в управлении соединением. Раздел 3.2 показывается, как модель распределенных систем (Определение 2.6) может быть расширена до процессов, использующих таймеры, и дает пример этого расширения.
Искажение сообщений. Естественно принять во внимание возможность того, что сообщения могут быть искажены в течение передачи. Содержание сообщения, переданного через физическое соединение, может быть повреждено из-за атмосферных шумов, плохо функционирующих модулей памяти, и т.д. Однако можно предположить, что искажение сообщения может быть обнаружено процессом-получателем, например, посредством контроля четности или более общих механизмов контрольной суммы ( [Tan88, Глава 41). Получение искаженного сообщения затем обрабатывается так, как будто не было получено никакого сообщения, и таким образом, искажение сообщения фактически вызывает его потерю. По этой причине искажение не обрабатывается явно; вместо этого всегда рассматривается возможность потери сообщения.
3.1 Сбалансированный протокол скользящего окна
В этом разделе изучается симметричный протокол, который обеспечивает надежный обмен информацией в обоих направлениях. Протокол взят из [Sch91, Глава 2]. Поскольку он используется для обмена информацией между станциями, которые непосредственно соединены через линию, можно предположить, что каналы имеют дисциплину fifo. Это предположение не используется, однако, до Подраздела 3.1.3, где показано, что числа последовательности, используемые протоколом могут быть ограничены. Протокол представлен в Подразделе 3.1.1, а в Подразделе 3.1.2 доказывается его правильность.
Два процесса связи обозначаются как p и q. Предположения, требования и протокол абсолютно симметричны. Вход p состоит из информации, которую он должен послать q, и моделируется неограниченным массивом слов inp. Выход p состоит из информации, которую он получает от q, и также моделируется неограниченным массивом слов, outp. Предполагается, что p имеет случайный доступ по чтению к inp и случайный доступ по записи к outp. Первоначально значение outp[i] не определено и представлено как udef для всех i. Вход и выход процесса q моделируется массивами inq и outq соответственно. Эти массивы нумеруются натуральными числами, т.е. они начинаются со слова с номером 0. В подразделе 3.1.3 будет показано, что произвольный доступ может быть ограничен доступом к "окну" конечной длины, передвигающемуся вдоль массива. Поэтому протокол называется протоколом «скользящего окна».
Процесс p содержит переменную sp, показывающую наименьшее нумерованное слово, которое p все еще ожидает от q. Таким образом, в любой момент времени, p уже записал слова от outp[0] до outp[sp - 1]. Значение sp никогда не уменьшается. Аналогично q содержит переменную sq. Теперь могут быть установлены требуемые свойства протокола. Свойство безопасности говорит о том, что каждый процесс передает только корректные данные; свойство живости говорит о том, что все данные когда-либо будут доставлены.