polynomiálny počet správ
konzistentný broadcast
•  ak dobrý proces / poslal (m, i, r) v kroku r, dobrí ju akceptujú najneskôr v r + 1
•  ak dobrý proces / neposlal (m, i, r) v kroku r, nikto dobrý ju neakceptuje
•  ak je správa (m, i, r) akceptovaná dobrým j v ť, najneskôr v ť + 1 ju akc. všetci
dobrí
algoritmus                                                                                       ^			
• / pošle (init, m, i,	r) v kole r		
• ak dobrý dostane kole r + 1	(init, m, i, r) v kole r	pošle (echo, m,	, r) všetkým dobrým v
a ak pred kolom ť	> r + 2 dostane dobrý od f + 1 echo, pošle (echo, m, i, r) v ť		
• ak dostal echo od n - f, akceptuje			
dohoda                                                                                           ^			
a dvoj kro kove fázy			
• v prvom kole bcastujú	všetci s 1		
• v kole 2s - 1 pošlú tí,	čo akceptovali od f +	s - 1 a ešte nebcastovali	
• akpo2(ŕ+ 1) kolách	/ akceptoval od 2ŕ + 1	procesov, tak 1	inakO
vzájomné vylúčenie
Ricart-Agrawala
•  logické hodiny 7}
•  request rí poslať všetkým (7), /)
•  čakať na odpoveď od všetkých
•  neodpovedá, ak:
a je v CS
• žiada prístup s vyššou prioritou (nižším časom)
•  pri opustení CS pošle všetky odpovede
zmenšiť počet správ - token
•  pre každý proces mám jeho posledný request
•  pre vstup: pošle všetkým request a čaká na token
•  pri opustení: zisti, kto čaká na token (v tokene je tabulka posledných držaní)
Dijkstra: self-stabilizing token-ring
•  procesy Zn, 0 je špeciálny
•  pre 0: má token, ak x0 = x„_i, pri opustení CS x0 := (x0 + 1)modn
•  pre ostatných: má token, ak x, ^ x,_i, pri opustení CS x, := x,_i
detekcia terminácie
a pasívne vrcholy = čakajú na prijatie správy
•  terminácia = všetky vrcholy sú pasívne
•  základný vs. riadiaci algoritmus
J
Dijkstra-Scholten
•  základný algoritmus má jedného iniciátora
•  udržuje sa strom výpočtu: vnútorné vrcholy sú procesy, listy sú správy
•  poslať správu: scp := scp + 1
•  prijať správu od q: ak nie som v strome, fatherp = q, inak send sig to fatherp
a prijať sig: scp := scp - 1 ak scp = 0 a som pasívny: send sig to fatherp a vypoj sa
•  prechod do pasívneho stavu:
ak scp = 0, send sig to fatherp a vypoj sa
•  S = J2 scp- S rastie pri poslanej správe a klesá pri doručenom sig, S > 0
•  ak alg. terminuje, posielajú sa iba sig, S klesá =► terminálna konfigurácia a strom výpočtu je prázdny
□        \3
počet správ je rovnaký ako v zákl. algoritme
J
•  p a q sú aktívne (poslať jednu správu z p)
•  obidva sa stanú pasívne =► musí sa poslať riadiaca správa, nech p
•  q ostane aktívny, pošle správu a zaktívni p
•  základný terminuje =► riadiaca správa
zovšeobecniť na viac iniciátorov:
les, keď skolabuje strom, ostane prázdny, wave
u        <3        -        =        =     -00*0