9-ma’ruza. Saytlarni aylanish va tanlash algoritmlari. Reja

out(token, 1) through n – 1 kanal
(token, k) marker qabul qilingandagi har bir jarayon uchun:
begin if k=2ⁿ then return(OK)
else begin faraz qilaylik l - 2^l|k bo’lgan eng katta nomer ;
out(token, k+1) through kanal l
end
end

Algoritmdan ko`rinib turibdiki, 2<sup>n</sup> marker jo`natmasidan so`ng qaror qabul qilinadi. p<sub>0</sub>- initsiator, p<sub>k</sub>- (token, k) markerini qabul qiladigan jarayon bo`lsin. Har bir k < 2ⁿ uchun p_k va p_k+1 qiymatlari 1 bitga farq qiladi, bunda quyidagi shartlarni qoniqtiradigan l(k) indeksini belgilaymiz:

Har bir i <n uchun mos bo`lgan k  {0, ..., 2<sup>n</sup>} сl(k) = i, тоp<sub>0</sub> = p<sub>2</sub>n sonlar mavjud va qaror initsiatorda qabul qilinadi. Bunda p<sub>a</sub> = p<sub>b</sub> dan 2<sup>n</sup>|(b – a) bo`ladi, bunda barcha p₀, ..., p₂n_-1 turli xil bo`ladi.

4. 
   Tarri algoritmi
   

Mustaqil aloqadagi graflar uchun aylanish algoritmi sifatida quyidagi ikki qoidaga asoslangan Tarri algoritmi berilgan.

1. 
   Jarayon hech qachon bitta kanal orqali ikki marta marker yubormaydi.
   
2. 
   Noinitsiator qoidaga asoslangan holda boshqa kanallar orqali markerni yuborolmasa, o`zidan oldingisiga (u dasylab marker qabul qilgan qo`shnisiga ) markerni yuboradi.
   

Quyidagi matnda saytning local o`zgaruvchilaridan foydalaniladi.
pre – jarayon bajarilayotgan saytdan oldingi sayt, ya`ni marker kelgan sayt.
used[q] - u saytgamarker yuborilganligining belgisi.