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áza: zajať i[k], i[2k],..., i[n — k] sekvenčne
•  vzniknú nezávislé "kruhy" R0,..., Rk_-Í, Rj = {/[/' + k], i\j + 2/c],...,/[/ + 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'],.. ., i[(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
u        <3        -        =        =     -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.
routovanie
cieľ: doručovať srávy medzi ľubovoľnou dvojicou
modely
•  destination based a  splittable
•  connections (wormhole) a  buffering
9  selfish
9 statické váhy (najkratšie cesty) 9 dynamické váhy (hot potato) • deadlock
-J
□      s>
najkratšie cesty
ako DFS                                                                                          *					
16/ \	\    8/	\    V	\   V	\  V	
u					v
exponenciálne veľa správ
□         rJ           -           =
najkratšie cesty
begin (* Initialize S to 0 and D to 0-distance *) 5:=0 ; forall u, r do
if u = t) then D(u. w] := 0 else if uv 6 E then D[«, i<] := uiuv else £>[u, ť] := oc : (* Expand S by pivoting *) while S5ÉI' do
(* Loop invariant: Vu. u : D\u, u] = ds(u. v) *) begin ]>ick w from V \ S ;
(* Execute a global uj-pivot *) forall u € V do
(* Execute a local w-pivot at u *) forall 1 e V do
D[u. v\ := min (D[u, «], D[u, 10] + D[m, b]) : S:=SU{«)} end     (* V«, v : D[u. v] = d(«, b) *) end
□        \3
najkratšie cesty
var Su Du
Nb„
set of nodes ; array of weights array of nodes :
begin Su := 0 :
forall v € V do if V = u
then begin Du[ľ\ := 0 : Nbu[v] := udef end else if v € Neighu
then begin D„jcj := u.',„. ; Nb„[v] := v end else begin Du[v] := oc ; M>„[t»] := udef end ; while 5„ ^ V do
begin pick w from V \ Su :
(* All nodes must pick the name «ode w here *) if u — w
then "broadcast the table £>,„" else "receive the table Dw" forall v € V do
if £>u[u;] + D,,.M < Du[v] then begin Du(t>j :=£>„[«>]+ £>„.[,•) :
M„[«] := Nbu[w] end : 5U := Sn U {u>} end end
□        \3
najkratšie cestv
var Su     : set of nodes ;
Du    : array of weights
Nbu   : array of nodes ;
begin Su ■— 0 ;
forall 71 £ V do if v = u
then begin Du[v] := 0 ; Ař6„[t>] := udef end else if v € Neighu
then begin D„[v] :— u)uv ; Nbu[v] := i> end else begin £>„M := oo ; ÄT6u[t;] := ude/ end ; while SIL ŕ V do
begin pick w from V \ Sw ;
{* Construct the tree Tw *) forall j; e Neigh,, do
if N&u[uj] = x then send {ys. u>) to x else send (nys.it;) to x ; num„recu : = 0 ; (* u must receive |JVeř^/i^| messages *) while num-recu < \Neigku\ do
begin receive (ys, w ) or { nys. w ) message :
num.recu := num-recu -f 1 end ; if D,,{w] < 'OO then (* participate in pivot round *) begin if u ^ w
then receive (dtab. uuD) fromthis Nbu\w) forall x € Neigh u do
if (ys. it') was received from x then send (dtab. «?, D) to x ; forall o £ V do (* local «'-pivot *) if Du[w] + D[v] < Du[v] then begin Du[v] := Du[w] + D[v] ;
Nbu[v] :=Nbu[w] end end :
Netchange
var Neigh»            : set of nodes :          (* The neighbors of u *)
Du                  : array of 0.. N ;       (* Du[v) estimates dfu, v) *)
Nbu                : array of nodes :      {* Nbu\v\ is preferred neighbor for v *
ndiau              : array of 0.. N ;       (* ndisv\w. v] estimates d(w, v) *)
Initialization:
begin forall it' £ Nciyh,,, v € V do ndisu[<t>. v] := N : forall v G V do
begin DUU>\ ■- N : Nb„{»\ := udej end : Dtl(it]:=0; Nb„[u\ := local ■ forall w fc A'c-ítrň,, do sond {mydist, u, 0) to í/j end
Procedure Recompute (v): begin if v = u
then begin Du[v] := 0 ; Nbu[v] := local end else begin (* Estimate distance to v *)
ři:- I + min{wfe((|«!. ľ] : tv € Neighu} ; if d < JV then begin Du[v]:=d;
Nbu[v] := w with 1 + ndisu[w, v] = d end else begin Du[v] := ,V ; /Vft,,^] := udef end end ; if í*«'r] has changed then forall x 6 JVei^ do send {mydist. u, Dw [■(.>]) to x end
Processing it ( mydist. r. d) message from neighbor «■: { A (mydist. ľ. d) irt at the head u f QN.ľ } begin receive (mydist. c ŕ/) from w : ndisu[w, v] := d : Recompute (v) end
Upon failure of channel aw:
begin receive ( fail, u>) : Neighu := Neigh,, \ {w} :
forall u S V do Recompute (v) end
Upon repair of channel utw:
begin receive {repair, w} : Neighu := Neigh,, U {u1} ; forall r £ V do
begin ndis„[w, v\ := N ;
send (mydist, (.£>„ [e]) tow end etui
korektnosť
lexikograficky klesá hodnota [ř0, ř-|,..., tN]
kde tj je počet správ (mydist, /)+ počet dvojíc u, v kde Du[v] = i
□        \3
packet routing
•  synchrónny režim
» vrcholy majú pakety (uložené v bufferoch)
•  v jednom kroku pojednej linke ide max. jeden paket
•  algoritmus = odchádzajúce linky + priorita bufferov
•  celkový čas
initial        j^—k configuration   H3j
packet routing na mriežke v N x v N
Každý vrchol má 1 paket, do každého smeruje 1 paket (permutation routing)
algoritmus
Najprv riadok, potom stĺpec. Prednosť má ten s najdlhšou cestou.
analýza: stačí 2a/ÄŽ - 2 krokov
o po V/V - 1 krokoch je každý v správnom stĺpci (nebrzdia sa)
• routovanie v stĺpci ide v VN - 1 krokoch
» pre každé / platí: po N — 1 krokoch sú koncové pakety na koncových miestach • dôvod: zdržujú sa iba navzájom
□        \3