Voľba šéfa v jednosmernom kruhu
(algoritmus Chang, Roberts)
Majme n procesorov zapojených do jednosmerného kruhu. Každý procesor má svoj identifikátor
(jednoznačné prirodzené čislo) a dve komunikačné linky, linku lin po ktorej mu prichádzajú správy
a linku lout po ktorej posiela správy. Na začiatku je zobudených niekoľko (aspoň jeden) procesov.
Keď proces dostane správu, zobudí sa. Cieľom je za šéfa zvoliť proces s minimálnym ID spomedzi
procesov zobudených na začiatku.
Algoritmus používa jednoduchú ideu: na začiatku každý zobudený procesor pošle po kruhu
svoje ID. Proces, ktoý dostane správu i , porovná i so svojím ID. Ak je jeho číslo väčšie, pošle
správu ďalej. Keďže procesy majú jednoznačné ID, jediná správa, ktorej sa podarí obísť celý kruh,
je správa nesúca minimálne ID.
const: ID : integer
lin, lout : link
var: leader : integer
Init:
leader := NULL
Code:
send ID
wait until leader <> NULL
On receipt i :
if i < ID then send i
if i = ID then
leader := ID
send leader, ID
On receipt leader, x :
leader := x
send leader, ID
Z nasledujúceho obrázku ľahko vidno, že v najhoršom prípade sa môže vykomunikovať až (n2
)
správ, ak sú procesory učíslované v smere kruhu a správy od procesorov s menšími číslami idú
pomaly (t.j. najprv dorazí správa od procesora n, potom dve správy od procesora n-1, tri správy
od n - 2 atď).
1
2
3
4
5
6 7
8
9
Teraz ideme ukázať, že v priemernom prípade sa vykomunikuje O(n log n) správ. Pretože jediná
operácia s ID je porovnanie, môžeme bez ujmy na všeobecnosti predpokladať, že procesory sú
očíslované permutáciou čísel 1, . . . , n. Nech náhodná premenná Xi udáva koľkokrát bola poslaná
správa i . Zjavne 1 bola poslaná n-krát, takže uvažujme i > 1. Pozrime sa na rozdelenie pravde-
1
podobnosti Xi. Aká je pravdepodobnosť, že i bola poslaná práve k-krát? Zjavne vrcholy kruhu
museli byť očíslované tak, že za vrcholom i nasleduje k - 1 vrcholov s väčším ID a za nimi vrchol
s menším ID. Je práve n-i
k-1 (i-1) možností takýchto očíslovaní. Všetkých možností, ako vybrať
k - 1 císel vrcholov a potom jedno iné číslo je n-1
k-1  (n - k). Preto keď túto pravdepodobnosť
označíme P(i, k), dostávame
P(i, k) =
n-i
k-1  (i - 1)
n-1
k-1  (n - k)
Aký je teda očakávaný počet poslaní správy i ? Správa i mohla byť poslaná najviac n - i + 1
krát a teda stredná hodnota Xi je
E[Xi] =
n-i+1
k=1
k  P(i, k)
Majme teraz náhodnú premennú X, ktorá udáva počet všetkých správ. Zjavne
X =
n
i=2
Xi
a teda
n + E[X] = n +
n
i=2
E[Xi] = n +
n
i=2
n-i+1
k=1
k  P(i, k)
je očakávaný počet všetkých správ. Ostáva nám teda iba upraviť sumu
n +
n
i=2
n-i+1
k=1
k 
n-i
k-1  (i - 1)
n-1
k-1  (n - k)
Budeme používať nasledujúcu identitu:
Lema 1
n-1
j=k
j!
(j - k)!
= k!
n
k + 1
Dôkaz:
n-1
j=k
j!
(j - k)!
=
n-1
j=k
k!j!
k!(j - k)!
= k!
n-1
j=k
j
k
= k!
n
k + 1
Teraz už môžeme dokázať nasledujúcu vetu:
Veta 1 Očakávaný počet správ algoritmu Chang-Roberts je n  Hn.
Dôkaz: Substitúcia j := n + 1 - i:
n +
n
i=2
n-i+1
k=1
k 
n-i
k-1  (i - 1)
n-1
k-1  (n - k)
= n +
n-1
j=1
j
k=1
k 
j-1
k-1  (n - j)
n-1
k-1  (n - k)
=
Rozpíšeme:
= n +
n-1
j=1
j
k=1
k(j - 1)!(n - j)(k - 1)!(n - k)!
(k - 1)!(j - k)!(n - 1)!(n - k)
=
Zmeníme poradie sumácie:
= n +
n-1
k=1

k(n - k - 1)!
(n - 1)!
n-1
j=k
(j - 1)!(n - j)
(j - k)!

 =
2
= n +
n-1
k=1

k(n - k - 1)!
(n - 1)!


n-1
j=k
n(j - 1)!
(j - k)!
-
n-1
j=k
j!
(j - k)!



 =
Podľa lemy teraz
n-1
j=k
(j-1)!
(j-k)! = (k - 1)! n-1
k a
n-1
j=k
j!
(j-k)! = k! n
k+1 , preto pokračujeme:
= n +
n-1
k=1
k(n - k - 1)!
(n - 1)!
n  (k - 1)!
n - 1
k
- k!
n
k + 1
=
a po rozpísaní a vykrátení dostaneme
= n +
n-1
k=1
n
k + 1
čo je hľadaný výsledok.
3