Реферат: Распределенные алгоритмы
(2) Свойство fifo. Говорят, что канал является fifo, если он соблюдает порядок сообщений, посланных через него. То есть, если р посылает два сообщения m1 и m2 процессу q и отправка m1 происходит раньше в р, чем отправка m2, то получение m1 происходит раньше в q, чем получение m2. Если не утверждается обратное, fifo каналы не будут предполагаться в этой книге.
Fifo каналы могут быть представлены в модели определения 2.6 при помощи замены набора М на множество очередей, одной для каждого канала. Отправка осуществляется добавлением сообщения к концу очереди, и событие получения удаляет сообщение с головы. Когда предполагаются каналы fifo, появляется новый тип коммуникационных сбоев, а именно, переупорядочивание сообщений в канале. Это может быть смоделировано переходом, который обменивает два сообщения в очереди.
Иногда случается, что распределенный алгоритм получает пользу от свойства fifo каналов, см., например, коммуникационный протокол в разделе 3.1. Использование порядка получение сообщений снижает количество информации, которая должна транспортироваться в каждом сообщении. Во многих случаях, однако, алгоритм может быть разработан так, чтобы функционировать правильно (и эффективно) даже, если сообщения могут быть переупорядочены в канале. В общем, реализация свойства fifo расределенных систем может понизить свойственный параллелизм вычислений, т.к. это может потребовать буферизации сообщений (на стороне получателя в канале) перед тем как сообщение будет обработано. По этой причине мы не выбираем предположение свойства fifo неявно в этой книге.
Более слабое допущение было предложено Ахуджа [Ahu90]. Выталкивающий канал – это канал, который соблюдает порядок только сообщений, для которых это было указано отправителем. Могут быть также определены более сильные допущения. Шипер и др. [SES89] определили каузально упорядоченную доставку сообщений, как описывается далее. Если р1 и р2 посылают сообщения m1 и m2 процессу q в событиях е1 и е2 и е1 í е2 , то q получает m1 перед m2 . Иерархия допущений доставки, состоящая из полного асинхронизма, каузально упорядоченной доставки, fifo, и синхронных коммуникаций, обсуждалась Чаррон-Бостом и др. [CBMT92].
(3) Емкость канала. Емкость – это число сообщений, которое может передаваться по каналу одновременно. Канал полон в каждой конфигурации, в которой он действительно содержит количество сообщений, равное его емкости. Событие посылки применимо, только если канал не полон.
Определение 2.6 моделирует каналы с неограниченной емкостью, т.е. каналы, которые никогда не наполняются. В этой книге всегда будет предполагаться, что емкость каналов не ограничена.
2.4.3 Допущения реального времени
Основное свойство представленной модели есть, конечно, ее распределенность: полная независимость событий в различных процессах, как выражает теорема 2.19. Это свойство теряется, когда предполагается кадр глобального времени и способность процессов наблюдать физическое время (устройство физических часов). В самом деле, когда некоторое реальное время истекает, это время истекает во всех процессах, и это проявится на часах каждого процесса.
Часы реального времени могут быть встроены при помощи снабжения каждого процесса переменной часов реального времени. Течение реального времени моделируется переходом, который передвигает вперед часы каждого процесса, см. раздел 3.2. Обычно, принимается ограничение на время передачи сообщения (время между отправкой и получением сообщения) вкупе с доступностью часов реального времени. Это ограничение может быть также включено в общую модель системы переходов.
Если не утверждается обратное, допущения реального времени не делаются в этой книге, т.е. мы предполагаем полностью асинхронные системы и алгоритмы. Допущения отсчета времени будут использованы в разделе 3.2, главе 11 и главе 14.
Изначальные знания процесса – это термин, используемый для обращения к информации о распределенной системе, которая представляется в начальных состояниях процессов. Если алгоритму сказано полагаться на такую информацию, то предполагается, что релевантная информация правильно сохраняется в процессах, прежде чем начнется исполнение системы. Примеры таких знаний включают следующую информацию.
(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, 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, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105
