voľba šéfa: jednosmerné kruhy
Chang Roberts                                                                                   "*			
			
const: var: Init:	ID lin> 'out '■ leader:	integer link integer	On receipt (/): if / < ID then send (/> if / = ID then leader := ID send (leader, ID)
leader -.= NULL			
Code:			On receipt (leader, x):
send (ID) wait until leader <>		NULL	leader := x send (leader, ID)
			
0(n\ogn) správ v priemernom prípade, Q(n2) v najhoršom
□         rS
dvojsmerné kruhy
Hirschberg-Sinclair
•  level /: dobýjať územie 2'
•  log n levelov
•  n/21 vrcholov na leveli
•  každý vrchol pošle 2' správ
Franklin
•  level /: poraziť susedov (na rovnakom leveli; "synchronizácia'" a log n levelov
•  n správ na level
Dolev - simulácia na 1-smernom kruhu
• idea: presunúť identitu
□         r3
dolný odhad
zapojiť do čiary L, vymení sa C(Ľ) správ
a indukcia
•  dve vrecia: vyberám trojice, chcem dve spojiť item pri spojení: dĺžka 2r+1, počet správ > /•2r_1
•  ešte treba 2r~1 správ; sporom
dolný odhad
□        S         -         =        -e    -o<\(y
GHS
•  ľubovoľná topologia
•  buduje sa kostra
•  "segmenty"
o spájanie po najlacnejšej odchádzajúcej hrane:
A menší sa pripojí k väčšiemu B rovnakí sa spoja C väčší čaká
•  veľkosť => level
var statep                                 ■.  (sleep, find, found} ;
stachp[q]                            :  (basic, branch, ir.ject)    for each q Ě Neigh   :
namePi bestwtp                 :  real ;
le.ve.lp                                    :  integer ;
testchjj. bestchp, father^  :   Neigh^ ;
veCp                                    :  integer :
(1)  As the first action of each process, the algorithm must be initialized: begin let pq be the channel of p with smallest weight ;
stachv[q\ := branch : levelp :— 0 ; statep := found ; rtcf, :— 0 : send {connect.!.}) to q end
(2)  Upon receipt of (connect. L) from q:
begin if I < levelp then (* Combine with Rule A *) begin stac.hp\q\ := branch ;
send {initiate. levdp, namep, state.v ) to q end else if stach)t\q\ = basic-then (* Rule C *) process the message later else (* Rule B *) send (initiate, levelp 4 l,ut(pq))find) to end
(3)  Upon receipt of {initiate, Ĺ, F. S) from q:
begin levelp := Ĺ : namep •— F : statep :— S : fatherp :— <? ;
bestchp :— urfe/ ; bestwtp := oo ;
forall r € Nei<jhp : stachp[r] = branch A r ^ q do send (initiate, L,FtS) to r ;
if Mate,, —find then begin recp := 0 : test end end
□               r3>
GHS
(4)  procedure test
begin if 3g e Neigh- : stachp[q] = basic then
begin testchp := q with sŕať.7ip[<?] — böÄic and ^{pq) minimal
send (test, levelp, namep) to testchp end else begin teatchy := «ríe/ ; report end end
(5)  Upon receipl of (test.L,F) from g:
begin if L > levelp then       (* Answer must wait' *) process the message later else if F — namep then (* internal edge *)
begin if siac/ip[g] = basic then stachv\q\ := reject ; if q ^ testchp
then send (reject) to y else tesi end else send (accept) to q end
(6)  Upon receipt of (accept) from q: begin testchp :— tide/ ;
if t*j(pq) < bestwtp
then begin bestwtp := u>(pg) ; bestchp :    g end ; report end
(7)  Upon receipt of (reject) from q:
begin if stachp[q] = basic then stachp q] := rejeci ;
tent end
□               r3>
GHS
(8)  proceduře repojí:
begin if reč? - f {q : stachp[q] = branch Ay/ father^} and testckp — udef then begin statCp :-foand ; semi (report, bestwtp) to fatherp end end
(9)  Upon receipt of (report,u) from r/: begin if q ^ fathe.rp
then (* reply for initiate message *) begin if u; < bestwtp then
begin bestwtp := u ; bestchp := 7 end ; ŕ-(-r,, := ľľCj, + 1 . report end else (* pq is the re-re edge *| if statCp = find
then process this message later else if u > bestwtp
then ckangeroot
else if j; — bestwtp — oc then stop end
(10)  procedure ckangeroot:
begin if stachplbestchp] — branch
then send ( changeroot) Lu besteh,, else begin send (connect,levelp) to bestchp : stachp[bestchp] := branch end end
(11)  Upon receipt of (changeroot): begin changeroot end
□         \3           -           =          -E      -O°x0
analýza
správnosť
ukázať, že sa zvolí práve jeden šéf: nenastane deadlock
počet správ
•  testovacie správy: jeden test po každej hrane
•  kostrové správy: fragment s n, vrcholmi pri postupe o level 0(ni) správ
•  postupy na level /: dizjunktné vrcholy
□        \3
KKM
•  ř(x)-traverzovanie
•  tokeny traverzujú/označujú územia
•  levely: keď sa stretnú dva, vznikne nový
•  naháňanie
KKM
var lev p	: integer	init —1 ;
catp, waitp	: V	init udef
lastp	: Neighp	init udef
begin if p is initiator then
begin levp := levp + 1 ; lastp := trav[p, levv) ;
catp := p ; send (annex, p, levp ) to lastv end ; while ... (* Termination condition, see text *) do begin receive token (q, /) ;
if token is annexing then t := A else ŕ ;= C ; if I > lev p then (* Case I *) begin levp := I ; catp := g ;
waitp := udef ; lastp := trav(q, I) ; send {annex,9,/) to lastP end else if / = levp and waitp ^ udef then {* Case II +) begin waitp := udef ; levp := kvp + 1 ; lastp := trav(p, levP) ; mrp :=p ; send (annex,/), levp) to /asrp end else if / = levp and lastp = udef then (* Case III *)
waitp := q else if I = lev p and í = A and q = catp then {* Case IV "■ begin lastp := irav(q, I) ; if lastp = decide
then p announces itself leader else send {annex,q,l) to lastp end else if I = lev p and ((t = A and
q > catp) or ť = C) then (* Case V *) begin send {chase,q,l) to lastp ; /asip := udef end else if í = levp then (* Case VI *) waitp := g end end
KKM
počet správ
•  naháňacie: 1 na vrchol a level, spolu n za level
•  objavovacie: J2i f(nd
•  ak f je konvexná, t.j. f (a) + f(b) < f (a + b), tak je 0(log n(n + f(n))) správ
□        \3
Kn: vplyv orientácie
zmysel pre orientáciu
Porty sú číslované podľa vzdialenosti vo fixnej Hamiltonovej kružnici.
a algoritmus: zajať fixný pattern {/[1 ..k], i[2k], i[3k],..., i[n - k]}
•  prvá fáza i[\..k]
» level, ID
» level je počet zajatých
» pripája sa celé územie (planarita!)
•  druhá fáza i[2k], i[3k], ...,i[n- k]
» nastav owner vrcholom /[1..fc], ack
a pošli elect do i[2k], i[3k],.. ., i[n - k]
» elect: ak je v prvej fáze, alebo je slabší => accept
počet správ
•  prvá fáza: O(n): z planarity
•  druhá fáza: max 0(n/k) kandidátov, každý pošle n/k správ :
0(n2/k2) správ
•  po zobudení (najsilnejšieho) O(k), v najhoršom O(n)
•  pridať wakeup fázu (poslať od /[1], i[k]) =► 0(k + n/k)
•  k = Jn
vylepšiť čas
•  prvá fáaza: zajať i[k], i[2k],... ,i[n — k] sekvenčne
•  vzniknú nezávislé "kruhy" Rq,..., Rk_^, Rj = {/[/' + k], i\j + 2k\,...,/[/ + n — k]}
•  druhá fáza: zajať /[1 ..k - 1] v log k krokoch
a level, ID
a v prvom kroku zajať i[k/2]
a v /-tom kroku zajať i[k/2'], i[3k/2'],.. ., /[(2; - 1 )k/2'\ ako v úplnom grafe (za zajatých
bojuje šéf) a v /-tom kroku je k/21 kandidátov; je log n krokov => 0(k log n) správ
0 k := n/ log n
n        S1         ~         =         =      -00*0
vplyv synchrónnosti
algoritmy založené na porovnaniach
a ekvivalentné okolia
•  c-symetrický reťazec: pre každé \fň < I < n a pre každý segment S je [^J ekvivalentných
•  bit-reversal je 1 /2-symetrický
•  c-symetrický reťazec, alg. nemôže skončiť po k kolách pre   gSr   — ^
•  počet správ: k =   ^p=  , je aspoň k + 1 kôl
•  aspoň   273T   aktívnych v /•-tom kole pošle správu
algoritmy využívajúce integer ID
cvičenie
V toruse rozmerov n x n (t.j. zacyklenej mriežke) sú na začiatku zobudené dva vrcholy. Napíšte algoritmus, pomocou ktorého sa každý z nich dozvie identifikátor druhého s použitím O(n) správ.
Nájdite asymptoticky optimálny (čo do počtu správ) algoritmus na voľbu šéfa v úplnom bipartitnom grafe Kn,n- Dokážte jeho zložitosť a optimalitu.