Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 27
Текст из файла (страница 27)
Допустим, что существует вычисление С, в которомзначения переменных sp и sq увеличиваются лишь конечное число раз, и пустьор я ад — наибольшие значения, которые могут принимать эти переменные походу вычисления С. Согласно доказанному утверждению либо отправление пакета (pack, inp[aq], Од) процессом р, либо отправление пакета (pack, inq[ap], ор)процессом q допустимо бесконечно долго, после того как переменные sp, sq, ари ач примут свои окончательные значения.
Таким образом, согласно допущениюF1 один из этих пакетов отправляется бесконечно часто, а согласно допущениюF2 он должен приниматься также бесконечно часто. Flo поскольку получениепроцессом р пакета с порядковым номером sp приводит к тому, что значение spувеличивается (и то же самое справедливо для процесса q), возникает противоречие с предположением о том, что значения переменных sp и sq больше не будутувеличиваться.
Этим завершается доказательство теоремы 3.4□В заключение этого параграфа мы обсудим коротко допущения F1 и F2. Д опущение F2 представляет собой минимальное требование, которое предъявляетсяк качеству канала связи, соединяющего процессы р и q, для того чтобы по этомуканалу мог осуществляться обмен данными. Очевидно, что если какое-нибудьслово inp[i] нельзя передать по этому каналу, то обеспечить его неизбежную доставку невозможно. Допущение F1 обычно реализуется в протоколе посредствомусловия тайм-аута: если значение переменной ар не увеличивается на протяжении определенного отрезка времени, то сообщение inp[ap\ передается повторно.Как уже было упомянуто во введении в настоящую главу, обосновать свойствобезопасности для рассматриваемого протокола можно без привлечения понятиявремени.3.1.3.
Обсуждение протоколаОграничение памяти процессов. Алгоритм 3.1 в том виде, в котором он былпредставлен, непригоден для реализации в компьютерных сетях, ввиду того чтов каждом процессе хранится бесконечный объем информации (массивы in и out),а так же потому, что в нем используются неограниченные порядковые номера.^ Доказательство проведено не вполне корректно. Из приведенных рассуждений всего лишь следует, что в каждом вычислении значение хотя бы одной из переменных sp или s q будет увеличиватьсябесконечно часто, в то время как нам нужно показать, что это будет иметь место сразу для обеих переменных.
Все дело в том, что в предложенном доказательстве «от противного» было сделаноневерное допущение. Правильнее было бы предположить, что существует вычисление С, в которомзначения хотя бы одной из переменных sp и Sg увеличиваются лишь конечное число раз. Тогда,согласно лемме 3.3 значение другой переменной также не может увеличиваться бесконечно часто.Далее по тексту.— Прим, перев.3.1. Симметричный протокол раздвижного окна95На самом деле, как будет показано далее, в каждый момент времени процессамдостаточно хранить лишь ограниченное количество слов. Пусть L = lp + lq.Лемма 3.6. Из инварианта Р следует, что отправление пакета {pack, w, i)процессом р допустимо только тогда, когда i < ар + L.Д о к а з а т е л ь с т в о .
Действие S^, сопровождается логическим условиемi < sp + lp, выполнимость этого условия, как следует из леммы 3.3, влечет засобой выполнимость неравенства i < ар + L.□Лемма 3.7. Из инварианта Р следует, что в том случае, когда outp [г] ф= udef, выполняется неравенство i < sp + L.Д о к а з а т е л ь с т в о . Согласно свойству (2р) справедливо соотношениеар > i — lq. Выполнимость соотношения i < ар + lq, как следует из леммы 3.3,влечет выполнимость неравенства i < ар + L.□Эти две леммы приводят нас к следующей схеме, изображенной на рис. 3.2.Процесс р должен хранить в памяти только слова из отрезка inp[ap..sp + lp — 1],поскольку он может отправлять только эти слова.
Указанный отрезок назовемокном передачи процесса р (на рис. 3.2 оно обозначено буквами S). Как только значение переменной ар увеличивается, р избавляется от тех слов, которыевыходят за рамки окна передачи (на рис. 3.2 они обозначено буквами А). Кактолько значение переменной sp увеличивается, р прочитывает следующие словав окне отправления из того источника, который генерирует эти слова.
Согласнолемме 3.6 окно отправления процесса р содержит не более L слов.А = Сброшенный входw = Записанные словаS = Окно передачиR = Принятые словаu = Неопределенные значенияii= Окно передачи/приемаI________IРис. 3.2. Протокол раздвижного окнаПодобного же рода доводы позволяют ограничить объем памяти, необходимый процессу р для хранения массива outp. Коль скоро значения тех элементовoutp[i\, для которых выполняется неравенство i < sp, остаются неизменными,Гл.
3. Коммуникационные протоколы96можно предположить, что процесс р проводит окончательную выдачу этих слови перестает хранить их в памяти (на рис. 3.2 эти слова обозначены буквами W).Коль скоро outp[i] = udef для всех тех г, для которых выполняется неравенство/ ^ sp + L , эти элементы массива outp[i] также не нужно хранить в памяти процесса.
Отрезок массива outp[sp..sp + L — 1] назовем окном приема процесса р.Окно приема обозначено на рис. 3.2 буквами и для тех элементов, значение которых еще не определено, и буквами R для тех слов, которые уже были получены.В памяти процесса хранятся только те слова, которые находятся в рамках окнаприема. Леммы 3.6 и 3.7 свидетельствуют о том, что каждый процесс в любоймомент времени хранит не более 2L слов.Ограничение порядковых номеров.
Наконец, мы покажем, что в том случае, если каналы поддерживают очередность передачи сообщений, порядковыеномера слов также можно ограничить. Воспользовавшись гипотезой об очередности передачи сообщений, можно показать, что порядковый номер пакета, который получает процесс р, отстоит от значения переменной sp не более чем на 2L.Мы обращаем внимание читателей на то, что это первый случай, когда нам пришлось обратиться к допущению об очередности передачи сообщений.Лемма 3.8.
Утверждение Р', определяемое следующей формулой:Р '= РA {pack, да,A {pack, да,A {pack, да,A {pack, да,i)i)i)i)следует за {pack, да', /') в очереди Qp =*> i > i' —Lследует за {pack, да', /') в очереди Qq =>• i > i ' - LeQp ==> i > ap - lpeQ q ==> i ^ aq - lq,(4p)(4q)(5p)(5y)является инвариантом алгоритма 3.1.Д о к а з а т е л ь с т в о . Так как ранее нам удалось показать, что утверждение Р является инвариантом, можно ограничиться обоснованием того, что свойства (4р), (4q), (5р) и (5q) выполняются в начальных конфигурациях и сохраняются при каждом переходе. Заметим, что в каждой начальной конфигурацииочереди сообщений пусты, и поэтому свойства (4р), (4q), (5р) и (5q), очевидно,выполняются. Остается показать, что они сохраняются при переходах системы.Sp: Чтобы убедиться, что действие Sp сохраняет выполнимость условий (4р)и (5р), заметим, что Sp не добавляет новых пакетов в очередь Qp и не изменяетзначения переменной ар.Чтобы убедиться, что действие Sp сохраняет выполнимость условия (5q), заметим, что если Sр добавляет пакет (pack, да, /) в очередь Qq, то / > ар.
Согласнолемме 3.3 отсюда следует, что i Д aq — lq.Чтобы убедиться, что действие Sp сохраняет выполнимость условия (4q), заметим, что если пакет (pack, да', /') уже находится в очереди Qq, то согласносвойству (lq) имеет место неравенство /' < sp + 1Р. Поэтому если Sp добавляетв очередь пакет (pack, да, г) с порядковым номером / > ар, то согласно лемме 3.3будет выполняться неравенство г' < ар + L ^ / + L.3.1. Симметричный протокол раздвижного окна97Rp: Чтобы убедиться, что действие Rp сохраняет выполнимость условий (4р)и (4q), заметим, что Rp не добавляет никаких пакетов ни в очередь Qp, ни вочередь Qq.Чтобы убедиться, что действие Rp сохраняет выполнимость условия (5р), заметим, что при увеличении значения переменной ар (после приема пакета (pack, да',до величины /' —lq + 1 для всех оставшихся пакетов (pack, да, г) из очереди Qpбудет выполняться неравенство i > i' —L (в силу свойства (4р)).
Следовательно, неравенство / > ар —1Р сохраняет свою выполнимость и после увеличениязначения переменной ар.Чтобы убедиться, что действие R,, сохраняет выполнимость условия (5q), заметим, что Rp не изменяет состава очереди Qq и значения переменной aq.Lp: Действие Lp не добавляет никаких пакетов в очереди Qp и Qq и не изменяет значений переменных ар и aq. Поэтому оно сохраняет выполнимость условий(4р), (4q), (5р) и (5q).Как следует из симметричности рассматриваемого протокола, действия S^, R9и Ц также сохраняют справедливость утверждения Р ' .□Лемма 3.9. Из утвержденияР'вытекают следующие соотношения:{pack, да, г) е Qp ==^ sp - L ^ г < sp + Lи{pack, да, г) е Qq =>• s q - L ^ / < sq + L.Д о к а з а т е л ь с т в о .
Рассмотрим пакет (pack, да, i)eQ p. Согласно свойству (1р) имеем неравенство i < sq + lq, из которого по лемме 3.3 следует неравенство i < sp + L. Согласно свойству (5р) имеем неравенство i ^ ар - 1Р, изкоторого по лемме 3.3 следует неравенство i ^ sp — L. Аналогичным образомдоказывется соотношение о пакетах из очереди Qq.□Как видно из этой леммы, достаточно, чтобы нумерация пакетов проводиласьпо модулю k, где k ^ 2L. Действительно, располагая значением переменной sp,а также значением переменной i по модулю k, процесс р может вычислить номер i.Выбор параметров.
Эффективность протокола в значительной степени зависит от выбора констант 1Р и lq. Вероятностный анализ зависимости пропускнойспособности протокола от этих констант был исследован в работе [173, гл. 2].Оптимальные значения констант зависят от ряда системотехнических параметров, таких как1) время связи, т. е.
промежуток времени между двумя последовательнымиоперациями процесса,2) задержка подтверждения приема, т. е. среднее время, которое требуется процессу р для передачи пакета процессу q и получения от него ответа,3) вероятность ошибки, т. е. вероятность потери пакета при передаче.Протокол чередующихся битов. Особо интересный вариант протокола раздвижного окна возникает в том случае, когда L = 1, т. е.
когда lp = 1 и lq = О(или наоборот). В качестве начальных значений переменных ар и aq в этом случае98Гл. 3. Коммуникационные протоколывыбирается не 0, а числа —1Р и —lq. Можно показать, что равенства ар + lq == sp и aq + lp = sq будут всегда сохраняться, и поэтому в протоколе достаточноиспользовать только одну из двух переменных ар или sp (и только одну из переменных aq или Sq). Если воспользоваться таймерами, которые позволят станциям отправлять сообщения поочередно, то мы получим таким образом широкоизвестный протокол чередующихся битов ; см. [135].3.2. Протокол с таймерамиТеперь мы перейдем к изучению той роли, которая отводится таймерам припроектировании и верификации коммуникационных протоколов; для этого рассмотрим упрощенный вариант А^-протокола сквозной передачи сообщений Флетчера и Ватсона.
Этот протокол был описан в работе [85], но та его слегка упрощенная версия, с которой мы будем иметь дело в этом разделе, заимствована изкниги [187, §3.2]. Этот протокол поддерживает не только механизм обмена данными (как это делает симметричный протокол раздвижного окна, рассмотренныйнами в §3.3.1), но также обеспечивает открытие и завершение соединений. Протокол обладает устойчивостью относительно потери и дублирования сообщений,а также относительно нарушения порядка следования сообщений.Информация о состоянии протокола (вернее, той его части, которая обеспечивает передачу данных) содержится в структуре данных, которая называетсядосье соединения.
(В §3.2.1 будет рассказано о том, какая именно информациясодержится в досье соединения). Досье соединения создается и стирается при открытии и закрытии соединения. Таким образом, соединение считается открытым(одной из станций), если существует досье этого соединения.Желая сосредоточить внимание читателей на наиболее существенных особенностях протокола (а именно, на механизме управления соединением и на тойроли, которая в этом механизме отведена таймерам), мы ограничимся рассмотрением упрощенного варианта протокола. В работах [85] и [187, §3.2] можно найтиобсуждение того, каким образом этот протокол должен быть расширен, для тогочтобы отвечать практическим потребностям.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
