Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 24
Текст из файла (страница 24)
е.протяженность отрезка времени между событием отправления и событиемприема сообщения не превосходит одной единицы;Сложностью алгоритма по времени будет считаться время, которое требуетсядля проведения вычисления в рамках указанных выше допущений. Следует обратить внимание, что эти допущения были выдвинуты исключительно для того,чтобы ввести определение сложности по времени для распределенных алгоритмов.
Корректность асинхронных алгоритмов должна быть доказана независимоот этих допущений4. Сложность по объему памяти. Сложность алгоритма по объему памятиравна количеству единиц памяти, необходимой отдельному процессу для выполнения этого алгоритма. В нашем случае этот объем равен логарифму от числасостояний процесса.Так как функционирование распределенных алгоритмов является недетерминированным, не исключены случаи, когда допустимыми оказываются сразунесколько вычислений, имеющих различные меры сложности. Поэтому мы будем проводить различие между сложностью в среднем и сложностью в наихудшем случае. Сложность алгоритма в наихудшем случае определяется наибольшейсложностью среди всех возможных вычислений алгоритма. Сложность алгоритмав среднем, как следует из названия, представляет собой среднюю сложность по84Гл.
2. Модельвсем возможным вычислениям, но, чтобы провести ее оценку, нужно определитьраспределение вероятностей по всем возможным вычислениям.2.5. Упражнения к главе 22.5. Упражнения к главе 285Упражнение 2.5. Докажите, что в множестве (Nn , 6l), где n > 2, имеетсятакой элемент, который превосходит бесконечно много элементов этого множества.Докажите, что множество (Nn , 6l) является фундированным.2.5.32.5.1Упражнение 2.1. Предложите определение модели распределенной системы, в которой возможен как синхронный, так и асинхронный обмен сообщениями.2.5.2Вниманию читателей предлагаются три упражнения, в которых речь идет о том,в чем состоит различие между инвариантом и всюду истинным предикатом, дизъюнктивными и конъюнктивными свойствами инвариантов и производных, а такжео том, как себя ведут инварианты при параллельной композиции программ.Упражнение 2.2.
Приведите пример такой системы переходов S и такогоутверждения P, что P всегда истинно в системе S, но при этом не является инвариантом этой системы.(Подсказка: пример системы с тремя конфигурациями приведен в работе [99] .Можно ли отыскать пример системы с двумя конфигурациями?)Упражнение 2.3. Предположим, что P1 и P2 — это инварианты системы S.Докажите, что (P1 ∨ P2) и (P1 ∧ P2) также являются инвариантами.Предположим, что P1 и P2 — это Q-производные системы S. Докажите, что(P1 ∨ P2) и (P1 ∧ P2) также являются Q-производными системы S.Для систем переходов с одним и тем же множеством конфигураций и одинаковыми начальными конфигурациями можно определить композицию их отношенийпереходов.
Так, например, параллельной композицией систем S 1 = (C , →1 , I)и S2 = (C , →2 , I) называется такая система S = (C , →, I), у которой → == (→1 ∪ →2).Упражнение 2.4. Пусть S — параллельная композиция систем S1 и S2 .Докажите, что всякий инвариант P систем S1 и S2 также является инвариантом системы S.Докажите, что всякая Q-производная P систем S1 и S2 также является Qпроизводной системы S.Приведите пример утверждения P, которое является всегда истинным в обеихсистемах S1 и S2 , но не является таковым в системе S.В следующем упражнении речь идет о фундированных множествах. Множество может быть фундированным даже в том случае, если для некоторого элемента в множестве содержится бесконечно много элементов, меньших этого элемента.
Лексикографический порядок для векторов a = (a1 , a2 , . . . , an) и b == (b1 , b2 , . . . , bn) определяется следующим соотношением:a < l b ⇐⇒ a1 < b1 ∨ ( a1 = b1 ∧ (a2 , . . . , an) < l (b2 , . . . , bn) ).Упражнение 2.6. Определите, каковы будут показания логических часовЛампорта для всех событий выполнения, представленного на рис.
2.1.Определите, каковы будет показания часов Маттерна для этих событий.Выделите некоторые пары параллельных событий и проверьте, будут ли упорядочены показания часов для этих событий.Упражнение 2.7. Предложите распределенный алгоритм (подобный алгоритму 2.3), который вычисляет для каждого события показания векторных часовМаттерна.Упражнение 2.8. Можно ли доказать теорему 2.21 путем последовательногоприменения теоремы 2.19 к событиям выполнения E?Упражнение 2.9. Докажите теорему 2.24.Упражнение 2.10.
Подберите подходящее определение для причинно-следственного порядка переходов системы с синхронным обменом сообщениями. Предложите определение часов для систем такого рода и постройте распределенныеалгоритмы для вычисления показаний этих часов.87ГЛАВА 3КОММУНИКАЦИОННЫЕ ПРОТОКОЛЫВ этой главе мы рассмотрим два протокола, которые используются для обеспечения надежного обмена данными между двумя вычислительными станциями.В идеальном случае обмен данными можно было бы осуществлять просто путемотправления и приема сообщений. Но, к сожалению, мы не можем игнорироватьвозможность возникновения ошибок при передаче данных; передача сообщенийдолжна проводиться в реальной физической среде, и вследствие этого может происходить потеря или дублирование передаваемых сообщений, изменение порядкаих следования, появление фиктивных сообщений.
Для обнаружения и устранения этих ошибок вычислительные станции используют дополнительные средства,которые принято назвать протоколами.Основным назначением этих протоколов является передача данных, т. е. получение информации от одной станции и доставка ее по назначению другой станции. Надежная передача данных предполагает повторную передачу тех сообщений, которые были потеряны, избавление от дублирующих сообщений, исправление поврежденных сообщений и устранение фиктивных сообщений. Для этогов протоколе ведется учет состояния информации; в нем отмечается, какие данные уже были отправлены, какие данные были зарегистрированы как полученныеи пр. В связи с необходимостью использования состояния информации возникаетвопрос об управлении соединением, т.
е. инициализации и аннулировании состояния информации. Инициализация называется установлением соединения,а аннулирование — завершением соединения. Трудность управления соединением вызвана тем обстоятельством, что при завершении соединения не исключенавероятность того, что в каналах связи могут еще оставаться сообщения. Приемтаких сообщений может произойти вне всякого соединения связи или в рамкахпоследующих соединений, и получение этих сообщений не должно нарушать правильность проведения очередных соединений.Протоколы, которые будут рассмотрены в этой главе, относятся к разнымуровням иерархии протоколов согласно классификации на основе базовой модели OSI (см.
§ 1.2.2). Эти протоколы включены в книгу по разным причинам;первый из этих протоколов вполне асинхронный, в то время как во втором предусматривается правильное использование таймеров. Во обоих случаях при верификации этих протоколов внимание будет сосредоточено на проверке свойствабезопасности, которое выражает требование доставки получателю всех правильных данных.Первый протокол, описанный в § 3.3.1, предназначен для обмена даннымимежду двумя станциями, которые имеют прямое физическое соединение (напри-мер, по телефонной линии); этот протокол относится к уровню управления передачей данных — второму уровню модели OSI.
Второй протокол, описанныйв § 3.3.2, предназначен для организации связи между двумя станциями в том случае, когда эта связь осуществляется через промежуточную сеть, которая включает в себя другие станции и допускает соединение конечных станций по различныммаршрутам; этот протокол относится к транспортному уровню модели OSI. Эторазличие между протоколами оказывает двоякое влияние на их функциональныевозможности.1. Обрабатываемые ошибки. Для этих двух протоколов будут рассмотрены различные классы ошибок передачи данных. Сообщения не могут обгонятьдруг друга при физическом соединении, и они также не могут дублироваться;поэтому в § 3.3.1 рассматриваются только ошибки потери сообщения (об искажении сообщений говорится чуть ниже).
В сетях сообщения могут перемещатьсяпо разным маршрутам, и поэтому они могут обгонять друг друга; кроме того,вследствие неисправностей в работе промежуточных станций сообщения могуткак дублироваться, так и утрачиваться. Поэтому в § 3.3.2 будут рассматриватьсяошибки утраты, дублирования и переупорядочения сообщений.2. Управление соединением. Мы не будем рассматривать управление соединением для первого протокола, этот вопрос существен для второго протокола.Предполагается, что физическое соединение обычно функционирует непрерывнов течение очень долгого времени, а не устанавливается и завершается периодически. Совсем по-другому происходит соединение с удаленными станциями.Потребность в таком соединении возникает на короткий срок для обмена некоторыми данными, но обычно поддерживать неопределенно долгое время соединение с каждой удаленной станцией — это слишком накладно. Поэтому второйпротокол должен обладать способностью устанавливать и завершать соединения.Изучение первого протокола показывает, что добиться требуемых свойствбезопасности протоколов передачи данных можно без привлечения таймеров.В § 3.3.1 представлен первый развернутый пример обоснования свойств безопасности, опирающегося на те методы доказательства, которые были описаныв § 2.5.2.
Принято считать (см. [199]), что для безопасного управления соединением необходимо использовать таймеры и устанавливать срок пребывания сообщения на этапе пересылки. Поэтому при обосновании свойств безопасностипротоколов управления соединением нужно принимать в расчет ту роль, которую в них играют таймеры. В § 3.3.2 мы покажем, как можно ввести таймерыв модель распределенных систем (определение 2.6), и приведем пример одной изтаких расширенных моделей.Искажение сообщений. Вполне естественно, что во внимание должна бытьпринята вероятность того, что при передаче сообщения подвергаются искажениям. Содержание сообщения, передаваемого по физическому каналу связи, можетбыть повреждено вследствие атмосферных помех, нарушений работы устройствпамяти и т. п.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
