(3) Емкость канала. Емкость – это число сообщений, которое может передаваться по каналу одновременно. Канал полон в каждой конфигурации, в которой он действительно содержит количество сообщений, равное его емкости. Событие посылки применимо, только если канал не полон.
Определение 2.6 моделирует каналы с неограниченной емкостью, т.е. каналы, которые никогда не наполняются. В этой книге всегда будет предполагаться, что емкость каналов не ограничена.
2.4.3 Допущения реального времени
Основное свойство представленной модели есть, конечно, ее распределенность: полная независимость событий в различных процессах, как выражает теорема 2.19. Это свойство теряется, когда предполагается кадр глобального времени и способность процессов наблюдать физическое время (устройство физических часов). В самом деле, когда некоторое реальное время истекает, это время истекает во всех процессах, и это проявится на часах каждого процесса.
Часы реального времени могут быть встроены при помощи снабжения каждого процесса переменной часов реального времени. Течение реального времени моделируется переходом, который передвигает вперед часы каждого процесса, см. раздел 3.2. Обычно, принимается ограничение на время передачи сообщения (время между отправкой и получением сообщения) вкупе с доступностью часов реального времени. Это ограничение может быть также включено в общую модель системы переходов.
Если не утверждается обратное, допущения реального времени не делаются в этой книге, т.е. мы предполагаем полностью асинхронные системы и алгоритмы. Допущения отсчета времени будут использованы в разделе 3.2, главе 11 и главе 14.
2.4.4 Знания процессов
Изначальные знания процесса – это термин, используемый для обращения к информации о распределенной системе, которая представляется в начальных состояниях процессов. Если алгоритму сказано полагаться на такую информацию, то предполагается, что релевантная информация правильно сохраняется в процессах, прежде чем начнется исполнение системы. Примеры таких знаний включают следующую информацию.
(1) Топологическая информация. Информация о топологии включает: количество процессов, диаметр графа сети, и топологию графа. Говорят, что сеть имеет чувство направления, если согласующаяся с направлениями разметка ребер в графе известна процессам (см. дополнение Б).
(2) Идентичность процессов. Во многих алгоритмах требуется, чтобы процессы имели уникальные имена (идентификаторы), и чтобы каждый процесс знал свое собственное имя изначально. Тогда предполагается, что процессы содержат переменную, которая инициализируется этим именем (т.е. различным для каждого процесса). Дальнейшие допущения могут быть сделаны касательно множества, из которого выбираются имена, - что имена линейно упорядочены или что они (положительные) целые. Если не утверждается обратное, в этой книге всегда будем предполагать, что процессы имеют доступ к их идентификаторам, в этом случае система называется именованной сетью. Ситуации, где это не так (анонимные сети) будут исследованы в главе 9.
(3) Идентификаторы соседей. Если процессы различаются уникальным именем, то возможно предположить, что каждый процесс знает изначально имена соседей. Это допущение называется знание соседей и, если не утверждается обратное, не будет делаться. Имена процессов могут быть полезными для цели адресации сообщений. Имя назначения сообщения дается, когда сообщение посылается с прямой адресацией. Более сильные допущения состоят в том, что каждый процесс знает весь набор имен процессов. Более слабое допущение состоит в том, что процессы знают о существовании, но не знают имен своих соседей. Прямая адресация не может использоваться в этом случае, и процессы используют локальные имена для их каналов, когда хотят адресовать сообщение, что называется непрямой адресацией. Прямая и непрямая адресация показана на рис. 2.5. Прямая адресация использует идентификатор процесса как адрес, в то время как непрямая адресация процессов р, r и s использует различные имена (а, b и c, соответственно), чтобы адресовать сообщения в назначение q.
Рис. 2.5 Прямая (а) и непрямая (b) адресация
2.4.5 Сложность распределенных алгоритмов
Самое важное свойство распределенного алгоритма – его правильность: он должен удовлетворять требованиям, налагаемым проблемой, что алгоритм
3 Протоколы Связи
В этой главе обсуждаются два протокола, которые используются для надежного обмена данными между двумя вычислительными станциями. В идеальном случае, данными бы просто обменивались, посылая и получая сообщения. К сожалению, не всегда можно игнорировать возможность ошибок связи; сообщения должны транспортироваться через физическую среду, которая может терять, дублировать, переупорядочивать или искажать сообщения, передаваемые через нее. Эти ошибки должны быть обнаружены и исправлены дополнительными механизмами, выполняющимися на вычислительных станциях, которые традиционно называются протоколами.
Основная функция этих протоколов - передача данных, то есть, принятие информации на одной станции и получение ее на другой станции. Надежная передача данных включает повторную посылку сообщений, которые потеряны, отклонение или исправление сообщений, которые искажены, и отбрасывание дубликатов сообщений. Для выполнения этих функций протокол содержит информацию состояния, записывая, какие данные уже был посланы, какие данные считаются полученными и так далее. Необходимость использования информации состояния поднимает проблему управления соединением, то есть, инициализации и отбрасывания информации состояния. Инициализация называется открытием соединения, и отбрасывание называется закрытием соединения. Трудности управления соединением возникают из-за того, что сообщение может остаться в каналах связи, когда соединение закрыто. Такое сообщение могло бы быть получено, когда не существует никакого соединения или в течение более позднего соединения, и получение не должно нарушать правильную операцию текущего соединения.
Протоколы, обсуждаемые в этой главе разработаны для различных уровней в иерархии протокола, типа модели 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 доказывается его правильность.
Страницы: 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, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90
