Лекция 3. Коммуник. протоколы. Протокол раздвижного окна. Принципы обоснования корректности, страница 6
Описание файла
PDF-файл из архива "Лекция 3. Коммуник. протоколы. Протокол раздвижного окна. Принципы обоснования корректности", который расположен в категории "". Всё это находится в предмете "распределенные алгоритмы" из 10 семестр (2 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 6 страницы из PDF
Ðåøèòü ñàìîñòîÿòåëüíî.(4p)(4q)(5p)(5q)Ðåàëèçàöèè ïðîòîêîëà ðàçäâèæíîãî îêíàÎòñþäà ñëåäóåòÒåîðåìà 3.8.Èç óòâåðæäåíèÿ P 0 âûòåêàþò ñëåäóþùèå ñîîòíîøåíèÿhpack, w , ii ∈ Qp =⇒ sp − L ≤ i < sp + Lèhpack, w , ii ∈ Qq =⇒ sq − L ≤ i < sq + L.Ðåàëèçàöèè ïðîòîêîëà ðàçäâèæíîãî îêíàÎòñþäà ñëåäóåòÒåîðåìà 3.8.Èç óòâåðæäåíèÿ P 0 âûòåêàþò ñëåäóþùèå ñîîòíîøåíèÿhpack, w , ii ∈ Qp =⇒ sp − L ≤ i < sp + Lèhpack, w , ii ∈ Qq =⇒ sq − L ≤ i < sq + L.Äîêàçàòåëüñòâî:Ðàññìîòðèì ïàêåò h, w , ii ∈ Qppack.Ðåàëèçàöèè ïðîòîêîëà ðàçäâèæíîãî îêíàÎòñþäà ñëåäóåòÒåîðåìà 3.8.Èç óòâåðæäåíèÿ P 0 âûòåêàþò ñëåäóþùèå ñîîòíîøåíèÿhpack, w , ii ∈ Qp =⇒ sp − L ≤ i < sp + Lèhpack, w , ii ∈ Qq =⇒ sq − L ≤ i < sq + L.Äîêàçàòåëüñòâî:Ðàññìîòðèì ïàêåò h , w , ii ∈ Qp .Ñîãëàñíî ñâîéñòâó (1p) èìååì íåðàâåíñòâî i < sq + `q , èçêîòîðîãî ïî Ëåììå 3.1 ñëåäóåò íåðàâåíñòâî i < sp + L .packÐåàëèçàöèè ïðîòîêîëà ðàçäâèæíîãî îêíàÎòñþäà ñëåäóåòÒåîðåìà 3.8.Èç óòâåðæäåíèÿ P 0 âûòåêàþò ñëåäóþùèå ñîîòíîøåíèÿhpack, w , ii ∈ Qp =⇒ sp − L ≤ i < sp + Lèhpack, w , ii ∈ Qq =⇒ sq − L ≤ i < sq + L.Äîêàçàòåëüñòâî:Ðàññìîòðèì ïàêåò h , w , ii ∈ Qp .Ñîãëàñíî ñâîéñòâó (1p) èìååì íåðàâåíñòâî i < sq + `q , èçêîòîðîãî ïî Ëåììå 3.1 ñëåäóåò íåðàâåíñòâî i < sp + L .Ñîãëàñíî ñâîéñòâó (5p) èìååì íåðàâåíñòâî i ≥ ap − `p , èçêîòîðîãî ïî Ëåììå 3.1 ñëåäóåò íåðàâåíñòâî i ≥ sp − L .packÐåàëèçàöèè ïðîòîêîëà ðàçäâèæíîãî îêíàÎòñþäà ñëåäóåòÒåîðåìà 3.8.Èç óòâåðæäåíèÿ P 0 âûòåêàþò ñëåäóþùèå ñîîòíîøåíèÿhpack, w , ii ∈ Qp =⇒ sp − L ≤ i < sp + Lèhpack, w , ii ∈ Qq =⇒ sq − L ≤ i < sq + L.Äîêàçàòåëüñòâî:Ðàññìîòðèì ïàêåò h , w , ii ∈ Qp .Ñîãëàñíî ñâîéñòâó (1p) èìååì íåðàâåíñòâî i < sq + `q , èçêîòîðîãî ïî Ëåììå 3.1 ñëåäóåò íåðàâåíñòâî i < sp + L .Ñîãëàñíî ñâîéñòâó (5p) èìååì íåðàâåíñòâî i ≥ ap − `p , èçêîòîðîãî ïî Ëåììå 3.1 ñëåäóåò íåðàâåíñòâî i ≥ sp − L .Àíàëîãè÷íûì îáðàçîì äîêàçûâåòñÿ ñîîòíîøåíèå î ïàêåòàõ èçî÷åðåäè Qq .packÐåàëèçàöèè ïðîòîêîëà ðàçäâèæíîãî îêíàÊàê âèäíî èç Òåîðåìû 3.8,Ðåàëèçàöèè ïðîòîêîëà ðàçäâèæíîãî îêíàÊàê âèäíî èç Òåîðåìû 3.8, äîñòàòî÷íî, ÷òîáû íóìåðàöèÿïàêåòîâ ïðîâîäèëàñü ïî ìîäóëþ k , ãäå k ≥ 2L .sp − L ≤ i < sp + LÄåéñòâèòåëüíî, ðàñïîëàãàÿ çíà÷åíèåì ïåðåìåííîé sp , à òàêæåçíà÷åíèåì ïåðåìåííîé i ïî ìîäóëþ k , ïðîöåññ p ìîæåòâû÷èñëèòü íîìåð i .Ðåàëèçàöèè ïðîòîêîëà ðàçäâèæíîãî îêíàÎñîáî èíòåðåñíûé âàðèàíò ïðîòîêîëà ðàçäâèæíîãî îêíàâîçíèêàåò â òîì ñëó÷àå, êîãäà L = 1 , ò.å.
êîãäà `p = 1 è `q = 0(èëè íàîáîðîò).  êà÷åñòâå íà÷àëüíûõ çíà÷åíèåì ïåðåìåííûõap è aq â ýòîì ñëó÷àå âûáèðàåòñÿ íå 0, à ÷èñëà −`p è −`q .Òàêîé âàðèàíò àëãîðèòìà ðàçäâèæíîãî îêíà íàçûâàåòñÿïðîòîêîëîì ÷åðåäóþùèõñÿ (àëüòåðíèðóþùèõ) áèòîâ ; îíïðåíäíàçíà÷åí äëÿ îäíîñòîðîííåé ïåðåäà÷è äàííûõ.Ðåàëèçàöèè ïðîòîêîëà ðàçäâèæíîãî îêíàÎñîáî èíòåðåñíûé âàðèàíò ïðîòîêîëà ðàçäâèæíîãî îêíàâîçíèêàåò â òîì ñëó÷àå, êîãäà L = 1 , ò.å. êîãäà `p = 1 è `q = 0(èëè íàîáîðîò).  êà÷åñòâå íà÷àëüíûõ çíà÷åíèåì ïåðåìåííûõap è aq â ýòîì ñëó÷àå âûáèðàåòñÿ íå 0, à ÷èñëà −`p è −`q .Òàêîé âàðèàíò àëãîðèòìà ðàçäâèæíîãî îêíà íàçûâàåòñÿïðîòîêîëîì ÷åðåäóþùèõñÿ (àëüòåðíèðóþùèõ) áèòîâ ; îíïðåíäíàçíà÷åí äëÿ îäíîñòîðîííåé ïåðåäà÷è äàííûõ.Çàäà÷à.Ïîêàæèòå, ÷òî â ýòîì ñëó÷àå â ïðîòîêîëå äîñòàòî÷íîèñïîëüçîâàòü òîëüêî îäíó èç äâóõ ïåðåìåííûõ ap èëè sp (èòîëüêî îäíó èç ïåðåìåííûõ aq èëè sq ).Ðåàëèçàöèè ïðîòîêîëà ðàçäâèæíîãî îêíàÇàäà÷à.Íàñêîëüêî ñóùåñòâåííûì äëÿ ñâîéñòâ êîððåêòíîñòè èíåèçáåæíîñòè äîñòàâêè ñîîáùåíèé â àëãîðèòìå ðàçäâèæíîãîîêíà ÿâëÿþòñÿ ñëåäóþùèå òðåáîâàíèÿ:1.
Äîïóùåíèå ñïðàâåäëèâîñòè F1,2. Äîïóùåíèå ñïðàâåäëèâîñòè F2,3. Î÷åðåäíîñòü ñëåäîâàíèÿ ïàêåòîâ â êàíàëå ñâÿçè,4. Íåâîçìîæíîñòü äóáëèðîâàíÿè ïàêåòîâ â êàíàëå ñâÿçè,5. Íàäåæíîñòü ðàáîòû ïðîöåññîâ àëãîðèòìà?ÊÎÍÅÖ ËÅÊÖÈÈ 3..
