Быстрый поиск

Реферат: Распределенные алгоритмы

Мы завершаем этот подраздел кратким обсуждением предположений Fl и F2. F2-ìèíèìàëüíîå требование, которому должен удовлетворять канал, соединяющий p и q, для того, чтобы он мог передавать данные. Очевидно, если некоторое слово inp[i] никогда не проходит через канал, то невозможно достичь окончательной доставки слова. Предположение Fl обычно реализуется в протоколе с помощью условия превышения времени: если ap не увеличилось в течение определенного промежутка времени, inp[ap] передается опять. Как уже было отмечено во введении в эту главу, для этого протокола безопасная доставка может быть доказана без принятия во внимания проблем времени (тайминга).

3.1.3 Обсуждение протокола

Ограничение памяти в процессах. Àëãîðèòì 3.1 не годится для реализации в компьютерной сети, т.к. в каждом процессе хранится бесконечное количество информации (массивы in и out) и т.к. он использует неограниченные порядковые номера. Сейчас будет показано, что достаточно хранить только ограниченное число слов в каждый момент времени. Пусть L = lp + lq.

Ëåììà 3.6 Из P следует, что отправление < pack, w,i> процессом p применимо только для i < ap+L.

Äîêàçàòåëüñòâî. Сторож Sp требует i < sp+lp, значит согласно Ëåììе 3.3 i < ap+L. ð

Ëåììà 3.7 Из P следует, что если outp[i]¹ udef, то i < sp + L.

Äîêàçàòåëüñòâî. Из (2p), ap > i— lq, значит i < ap + lq, и i < sp + L (из Ëåììы 3.3). ð

Ðèñóíîê 3.2 Скользящие окна протокола.

Последствия этих двух лемм отображены на Ðèñóíêе 3.2. Процессу p необходимо хранить только слова inp[ap..sp + lp — 1] потому, что это слова, которые p может послать. Назовем их как посылаемое окно p (представлено как S на Ðèñóíêе 3.2). Каждый раз, когда ap увеличивается, p отбрасывает слова, которые больше не попадают в посылаемое окно (они представлены как A на Ðèñóíêе 3.2). Каждый раз, когда sp увеличивается, p считывает следующее слово из посылаемого окна от источника, который производит слова. Согласно Ëåììе 3.6, посылаемое окно процесса p содержит не более L слов.

Подобным же образом можно ограничить память для хранения процессом p массива outp. Т.к. outp[i] не меняется для i < sp, можно предположить, что p выводит эти слова окончательно и более не хранит их (они представлены как W на Ðèñóíêе 3.2). Т.к. outp[i] = udef для всех i ³ sp + L, эти значения outp[i] также не нужно хранить. Подмассив outp[sp..sp +L—1] назовем принимаемое окно p. Принимаемое окно представлено на Ðèñóíêе 3.2 как u для неозначенных слов и R для слов, которые были приняты. Только слова, которые попадают в это окно, хранятся процессом. Леммы 3.6 и 3.7 показывают, что не более 2L слов хранятся процессом в любой момент времени.

Ограничение чисел последовательности. В заключение будет показано, что числа последовательности могут быть ограничены, если используются fifo-каналы. При использовании fifo предположения можно показать, что номер порядковый номер пакета, который получен процессом p всегда внутри 2L-окрестности sp. Обратите внимание, что fifo предположение используется первый раз.

Ëåììà 3.8 Утверждение P', определяемое как

P' º P

/\ <pack, w, i> is behind <pack, w', i'> in Qp Þ i > i' - L (4p)

/\ <pack, w, i> is behind <pack, w', i'> in Qq Þ i > i' - L (4q)

/\ <pack,w,i> ÎQp Þ i³ ap - lp (5p)

/\ <pack,w,i> ÎQq Þ i³ aq - lq (5q)

является инвариантом Àëãîðèòìа 3.1.

Äîêàçàòåëüñòâî. Т.к. уже было показано, что P - инвариант, мы можем ограничиться доказательством того, что (4p), (4q), (5p) и (5q) выполняются изначально и сохраняются при любом перемещении. Заметим, что в начальном состоянии очереди пусты, следовательно (4p), (4q), (5p) и (5q) очевидно выполняются. Сейчас покажем, что перемещения сохраняют истинность этих утверждений.

Sp: Чтобы показать, что Sp сохраняет (4p) и (5p), заметим, что Sp не добавляет пакетов в Qp и не меняет ap.

Чтобы показать, что Sp сохраняет (5q), заметим, что если Sp добавляет пакет <pack, w, i> в Qq, то i ³ ap, откуда следует, что i³ aq - lq (из Ëåììы 3.3).

Чтобы показать, что Sp сохраняет (4q), заметим, что если < pack, w', i'> в Qq, тогда из (lq)
i' < sp + lp, следовательно, если Sp добавляет пакет < pack, w, i> с i ³ ap, то из Леммы 3.3 следует i' < ap+L £ i+L.

Rp: Чтобы показать, что Rp сохраняет (4p) and (4q), заметим, что Rp не добавляет пакеты в Qp или Qq.

Чтобы показать, что Rp сохраняет (5p), заметим, что когда ap увеличивается (при принятии <pack, w', i'>) до i' - lq +1, тогда для любого из оставшихся пакетов <pack, w, i> в Qp мы имеем i > i' - L (из 4р). Значит неравенство i ³ ap - lp сохраняется после увеличения ap.

Чтобы показать, что Rp сохраняет (5q), заметим, что Rp не меняет Qq и aq.

Lp: Действие Lp не добавляет пакетов в Qp или Qq, и не меняет значения ap или aq; значит оно сохраняет (4p), (4q), (5p) и (5q).

Из симметрии протокола следует, что Sq, Rq и Lq тоже сохраняет P'. ð

Ëåììà 3.9 Из P' следует, что

<pack, w,i>Î Qp Þ sp -L£ i< sp +L

<pack, w,i>Î Qq Þ sq -L£ i< sq +L.

Äîêàçàòåëüñòâî. Пусть <pack, w,i> Î Qp. Из (lp), i < sq + lq, и из Ëåììы 3.3 i < sp + L. Из (5p), i ³ ap— lp, и из Ëåììы 3.3 i ³ sp— L. Утверждение относительно пакетов в Qq доказывается так же. ð

Согласно Ëåììе достаточно посылать пакеты с порядковыми номерами modulo k, где
k ³ 2L. В самом деле, имея sp и i mod k, p может вычислить i.

Выбор параметров. Значения констант lp и lq сильно влияют на эффективность протокола. Их влияние на пропускную способность протокола анализируется в [Sch91, Chapter 2]. Оптимальные значения зависят от числа системно зависимых параметров, таких как

время связи, т.е., время между двумя последовательными операциями процесса,

время задержки на обмен, т.е., среднее время на передачу пакета от p к q и получение ответа от q к p,

вероятность ошибки, вероятность того, что конкретный пакет потерян.

Протокол, чередующий бит. Интересный случай протокола скользящего окна получается, когда L = 1, ò.å., lp = 1 и lq= 0 (или наоборот). Переменные ap и aq, инициализируется значениями -lp и -lq, а не 0. Можно показать, что ap + lq = sp и aq + lp = sq всегда выполняется, значит только одно ap и sp (и aq и sq) нужно хранить в протоколе. Хорошо известный протокол, чередующий бит [Lyn68] получается, если использование таймеров дополнительно ограничивается, чтобы гарантировать, что станции посылают сообщения в ответ.