Реферат: Распределенные алгоритмы
"m Î M : A(m)
è в самом деле легко видеть, что подобное предложение сохраняется при дублировании и потере пакетов. В дальнейших главах мы увидим инварианты в более общей форме, например
èëè
условие Þ $m Î M : A(m).
Утверждения, имеющие этй форму могут быть фальсифицированы потерей или дублированием пакетов, è следовательно не могут использоваться в дîêàçàòåëüñòâе корректности Àëãîðèòìов, которые должны допускать подобные дефекты.
Подобные же наблюдения применимы к форме инвариантов в действии Time. Уже было отмечено, что это действие сохраняет все утверждения формы Xt ³ Yt + C,
где Xt è Yt -таймеры è C -константа.
P1¢ = cs Þ St£ S (1¢)
/\ cr Þ 0 < Rt £ R (2')
/\ "i < B + High : Ut[i] < U (3')
/\ " <.., r > Î Mp, Mq : 0 < r £m (4')
/\ <data, s, i, w, r >Î M, Þ cs /\ St ³ (1+e)(r+ m+(1+e)R) (5')
/\ crÞ cs /\ St ³ (l+e)((i+e)Rt+m) (6')
/\ < ack, i, r > Î Mp Þ cs /\ St > (1 + e)´r (7')
/\ <data, s, i, w, r > ÎMq, Þ (w = inp[B + i] /\ i < High) (8')
/\ Øcs Þ \/i < B: 0k(i) (9')
/\ cs Þ \/i < B + Low : 0k(i) (10')
/\<data,true,I,w, r)Î MqÞ"i<B+I: 0k(i) (11')
/\ cr Þ "i < B + Exp : 0k(i) (12')
/\ <ack,I, r >Î MpÞ"i <B+I: Ok(i) (13')
/\ <data, s, i, w, r) ÎMq Þ Ut[B+i] > (l+e)( r -m) (14')
/\ i1£ i2 < B + High Þ Ut[i1] < Ut[i2] (15')
/\ cr Þ Rt ³ (1 + e)((l + e) Ut[pr] + (1 + e)2 m) (16')
/\ pr < B + High /\ Ut[pr] >-(1+e)mÞ cr (17')
/\ cr Þ B + Exp = pr+1 (18')
Ðèñóíîê 3.9 инвариант протокола с отклонением таймеров.
Неаккуратные таймеры. Действие Time моделирует идеальные таймеры, которые уменьшаются точно на d в течение d единиц времени, на на практике таймеры страдают неточности, называемой отклонением. Это отклонение всегда предполагается e-ограниченным, ãäå e-известная константа, что означает, что в течение d единиц времени таймер уменьшается на величину d ', которая удовлетворяет d /(l + e) £ d' £ d ´ (1 + e). (Обычно e бывает порядка 10-5 или 10-6.) Такое поведение таймеров моделируется действием Time-e, приведенном в Àëãîðèòìе 3.8.
Было замечено, что Time сохраняет утверждения
специальной формы Xt ³
Yt + C потому, что таймеры обеих частей неравенства уменьшаются
на в точности одинаковую величину, è из
Xt ³ Yt + C следует (Xt
- d) ³ ( Yt - d)
+ C. Такое жн наблюдение может быть сделано для Time-e. Для действительных чисел Xt, Yt, d, d
', d", r, è c,
удовлетворяющих d > 0
è r > 1, из
(Xt ³
r2 Yt + c) /\ (
£ d '£ d ´
r) /\ (
£ d ''£ d ´
r)
следует
(Xt-d ')³ r2(Yt- d") + c.
Следовательно, Time-e сохраняет утверждение формы
Xt ³ (1 + e)2 Yt + c.
Теперь протокол может быть адаптирован к работе с отклоняющимися таймерами, если соответствующим образом изменить инварианты. Для того, чтобы другие действия тоже сохраняли измененные инварианты, константы R è S протокола должны удовлетворять
R ³ (1 + e)((1 + e)U + (I + e)2) è S ³ (1 + e)(2m + (1 + e)R).
Исключая измененные константы, протокол остается таким же. Его инвариант приведен на Ðèñóíêе 3.9.
Òåîðåìà 3.16 P2'- инвариант протокола, основанного на таймере с e-ограниченным отклонением таймера. Протокол удовлетворяет требованиям Нет потерь и Упорядочение.
Óïðàæíåíèå 3.1 Покажите, что сбалансированный протокол скользящего окна не удовлетворяет требованию окончательной доставки, если из предположений Fl è FS, выполняется только F2.
Óïðàæíåíèå 3.2 Докажите, что если L = 1 в сбалансированном протоколе скользящего окна è ap è aq, инициализируются значениями -lq è -lp, то всегда верно ap+lq = sp è aq+lp = sq.
Óïðàæíåíèå 3.3 В протоколе, основанном на таймере отправитель может объявить слово возможно потерянным, когда на самом деле оно было корректно доставлено приемником.
(1) Опишите выполнение протокола, при котором возникает этот феномен.
(2)Можно ли спроектировать протокол, в котором отправитель генерирует сообщение об ошибке в течение ограниченного промежутка времени, тогда и только тогда, когда слово не доставлено приемником?
Óïðàæíåíèå 3.4 Предположим, что из-за выхода из строя часового устройства, приемник не может закрыть соединение вовремя. Опишите работу протокола, основанного на таймере, когда слово теряется без сообщений отправителя.
Óïðàæíåíèå 3.5 Опишите работу протокола, основанного на таймере, в котором приемник открывает соелинение при принятии пакета с порядковым номером, большим нуля.
Óïðàæíåíèå 3.6 Действие Time-e не моделирует отклонение в оставшемся времени жизни пакетов. Почему?
Óïðàæíåíèå 3.7 Докажите Теорему 3.16.
Óïðàæíåíèå 3.8 Инженер сети хочет использовать протокол, основанный на таймере, но хочет, чтобы отчет о возможно потерянных словах приходил раньше, в соответствии со следующей модификацией Ep.
Ep: (* Генерация сообщения об ошибке для возможно потерянных слов *)
{ Ut[B + Low] < 0 }
begin error[B + Low] := true ; Low := Low + 1 end
Продолжает ли тàêèì îáðàçîì измененный протокол удовлетворять требованиям Нет потерь и Упорядочение или должны быть сделаны какие-то изменения? Укажите преимущества и недостатки этих изменений.
Процесс (узел в компьютерной сети), вообще, не соединен непосредственно с каждым другим процессом каналом. Узел может посылать пакеты информации непосредственно только к подмножеству узлов называемых соседями узла. Маршрутизация - термин, используемый для того, чтобы описать решающую процедуру, с помощью которой узел выбирает один (или, иногда, больше) соседей для посылки пакета, продвигающегося к конечному адресату. Цель в проектировании алгоритма маршрутизации - сгенерировать (для каждого узла) процедуру принятия решения для выполнения этой функцию и предоставление гарантии для каждого пакета.
Страницы: 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
