Lezione 8
Chernoff Bound
Siano X1,…Xn n variabili casuali indipendenti tali che
Pr[Xi =1]=pi
0<pi<1
Pr[Xi =0]=1-pi
E[Xi]= pi
n
Consideriamo
la variabile casuale X 
X i e poniamo
n
i 1
 = E[X]=  pi
i 1

Allora abbiamo   > 0


 e
Pr[ X  (1   )  ]  
1
(
1


)

Pr[ X  (1   )  ]  e

 2
2



Chernoff Bound
 e
Pr[ X  (1   )  ]  
1
(
1


)

Pr[ X  (1   )  ]  e





 2
2
Esempio
Supponiamo di lanciare 100 volte una moneta
Sia Xi la variabile casuale
1, l' iesimo lancio
testa;
Xi  
0, l' iesimo lancio croce;
Abbiamo quindi
Pr[Xi=1]=1/2 e E[Xi]=1/2 per tutte le i.
n
Allora X 
X i conta il numero delle teste in 100 lanci.
=E[X]=50 i 1
Calcoliamo un upper bound sulla probabilità che X>60
Pr[X>60]=Pr[X>(1+0.2) ]<(e0.2/1.21.2)500.393

Chernoff Bound
 e
Pr[ X  (1   )  ]  
1
(
1


)

Pr[ X  (1   )  ]  e

 2
2
Nella lezione precedente ci siamo posti una domanda
Quanti nodi ci sono in 2b/n identificatori?
T
2b/n
Nel nostro sistema ci sono n nodi.
1, l' iesimo nodo appartiene a T;
Xi  
0, l' iesimo nodo non appartiene a T;
Pr[Xi=1]=(2b/n)/2b=1/n
Pr[Xi=0]=1- Pr[Xi=1]=(n-1)/n
E[X ]=1/n




 e
Pr[ X  (1   )  ]  
1
(
1


)

Chernoff Bound
T
Pr[ X  (1   )  ]  e
2b/n





 2
2
1, l' iesimo nodo appartiene a T;
Xi  
0, l' iesimo nodo non appartiene a T;
n
X   Xi
i 1
4 ln n / ln ln n =
X conta quanti nodi cadono in T
O(log n / log log n)
=E[X]=1/n*n=1
=1
Chernoff bound
e/4<1
Proviamo
che non ci sono più di O(logn / log log
n) nodi.


4 ln n
1
ln ln n


e
 4 ln n  
Pr  X  
   
4 ln n
ln
ln
n

    4 ln n  ln ln n



  ln ln n 
e
4 ln n  ln ln n 
ln 

ln ln n  ln n 
e
4 ln n
ln ln ln n  ln ln n 
ln ln n

e



4 ln n

 e
ln ln n

e

 
4 ln n
 4 ln n

 4 ln n  ln ln n 



 ln ln n
 ln ln n 

4 ln n
ln ln ln n
ln ln n
e
4 ln n

e

 e

ln ln ln n
ln ln n





4 ln n
 ln ln n
4 ln n
4 ln n

e ln ln n  ln ln n  ln ln n  ln ln n







 4 ln n 
 ln n 


n>e2e
4 ln n
 lnlnlnlnlnnn 1 

  e



4 ln n
 e 1/ 2 
4 ln n
 e  2 ln n 
1
n2
H-Chord
Chord
b
 Sia n=2 , per ogni 0 ≤ i < b, il nodo x è connesso ai
nodi (x+2i) mod 2b;
Il grado è b;
Il diametro è b;
APL è b/2;
R-Chord n=2b [MNW04]
b
 Sia n=2 , per ogni 0 ≤ i < b, sia rx(i) un intero scelto in
maniera casuale dall’intervallo [0,2i), il nodo x è
connesso ai nodi (x+2i+rx(i)) mod 2b;
H-Chord
 Sia H() una funzione di hash (es SHA) che mappa un
identificatore in nell’intervallo [0,1), il nodo x è
connesso con i nodi x+2i+H(x)2i mod 2b;
H-Chord
R-Chord vs H-Chord
R-Chord 2i
H-Chord
2i
2i+1
2i+1
2i+2
2i+2
H-Chord
I
Claim
2p
s
d
Per ogni nodo si  S, la probabilità che un
vicino di si  I è almeno d’/2p.
P’=Pr[Jk(si)I per qualche 0 ≤ k < b] ≥ d’/2p
Prova
Consideriamo il generico vicino di s, si.
Denotiamo con di la distanza fra si e t.
Sia pi tale che 2pi ≤ di < 2pi+1
di
Due casi:
2p
1. d-d’≥si+2pi
s
2p+1
2p ≤ d < 2p+1
p > (log n) / log (log n)
I = (d-d’, d]
d’=  d log log n 

log n
|S|=p
di≤d
pi≤p
i
i
s
d

2pi+1
d-d’ I
t
H-Chord
I
Claim
2p
s
d
Per ogni nodo si  S, la probabilità che un
vicino di si  I è almeno d’/2p.
P’=Pr[Jk(si)I per qualche 0 ≤ k < b] ≥ d’/2p
di
Prova
1. d-d’≥si+2pi
2p+1
2p ≤ d < 2p+1
p > (log n) / log (log n)
I = (d-d’, d]
d’=  d log log n 

log n
|S|=p
di≤d, pi≤p
2pi
si
s

2pi+1
d-d’ I
d
t
L’unico jump di si che può cadere in I è il jump (pi+1)esimo, infatti il jump (pi+1)-esimo [si+2pi, si+2pi+1).
In particolare il jump (pi+1)-esimo appartiene a I con
probabilità |I|/2pi = d’/2pi ≥ d’/2p
pi≤p
H-Chord
I
2p
Claim
2p+1
s
2p ≤ d < 2p+1
p > (log n) / log (log n)
I = (d-d’, d]
d’=  d log log n 
d
Per ogni nodo si  S, la probabilità che un
vicino di si  I è almeno d’/2p.
P’=Pr[Jk(si)I per qualche 0 ≤ k < b] ≥ d’/2p
Prova
d
2. d-d’<si+2pi
di
si
s
2pi
d-d’

log n

|S|=p
di≤d, pi≤p
2pi+1
I
t
H-Chord
2p ≤ d < 2p+1
p > (log n) / log (log n)
I = (d-d’, d]
d’=  d log log n 
Claim
Per ogni nodo si  S, la probabilità che un
vicino di si  I è almeno d’/2p.
P’=Pr[Jk(si)I per qualche 0 ≤ k < b] ≥ d’/2p
d
Prova
di
2. d-d’<si+2pi
si
2pi
d-d’

log n

|S|=p
di≤d, pi≤p
2pi+1
I
s
t
A B
In questo caso sia il jump p-esimo che il jump (p+1)-esimo
possono cadere in I.
Sia I = A  B dove A=(d-d’, si+2pi) e B=[si+2pi,d]
Ovviamente |A|+|B|=d’.
H-Chord
2p ≤ d < 2p+1
p > (log n) / log (log n)
I = (d-d’, d]
d’=  d log log n 
Claim
Per ogni nodo si  S, la probabilità che un
vicino di si  I è almeno d’/2p.
P’=Pr[Jk(si)I per qualche 0 ≤ k < b] ≥ d’/2p
d
Prova
2. d-d’<2pi
di
si
2pi
d-d’


log n


|S|=p
di≤d, pi≤p
A=(d-d’, si+2pi)
B=[si+2pi,d]
2pi+1
I
s
t
A B
C
Sia C l’insieme (si+2pi+1 – 2|A|,si+2pi+1)
In H-Chord se il (pi+1)-esimo jump di si cade in C allora
il pi-esimo jump di si cade in A.
Siamo interessati a calcolare la probabilità che il (pi+1)-esimo
jump di s cade in C o in B.
H-Chord
Claim
Per ogni nodo si  S, la probabilità che un
vicino di si  I è almeno d’/2p.
P’=Pr[Jk(si)I per qualche 0 ≤ k < b] ≥ d’/2p
d
Prova
di
2. d-d’<2pi
2pi
d-d’
si
2p ≤ d < 2p+1
p > (log n) / log (log n)
I = (d-d’, d]
d’=  d log log n 

log n

|S|=p
di≤d, pi≤p
A=(d-d’, si+2pi)
2pi+1
I
s
t
A B
C
Sia Q l’evento “il (pi+1)- esimo jump di si cade in C”
questa volta
Sia R l’evento “il (pi+1)-esimo jump di si Ma
cade
in B”
QR è vuoto.
Siamo interessati a calcolare la Pr[QR]=Pr[Q]+Pr[R]-Pr[QR]
Q
QR
R
H-Chord
2p ≤ d < 2p+1
p > (log n) / log (log n)
I = (d-d’, d]
d’=  d log log n 
Claim
Per ogni nodo si  S, la probabilità che un
vicino di si  I è almeno d’/2p.
P’=Pr[Jk(si)I per qualche 0 ≤ k < b] ≥ d’/2p
d
Prova
di
2. d-d’<2pi
si
2pi
d-d’

2pi+1
I
t
A B
Pr[QR]= Pr[Q]+Pr[R]-Pr[QR] =Pr[Q]+Pr[R]
2 pi

2A B
2 pi

|S|=p
di≤d, pi≤p
A=(d-d’, si+2pi)
s
CB
log n

d' d'
 p
pi
2
2
C
H-Chord
Perchè H-Chord e non R-Chord?
Svantaggi R-Chord


Come mantenere la lista dei vicini dei vicini?
No fast bootstrap
In H-Chord non c’è nessun fattore random, in
particolare ogni nodo conoscendo il suo vicino
conosce i vicini del suo vicino.
O almeno può stimare le posizioni dei
vicini del nostro vicino
H-Chord
Dato un nodo x, x conosce il suo vicino y,
dato y, x può calcolare H(y) e quindi può
calcolare per ogni 0≤i<b y+2i+H(y)2i.
La funzione di hash è
uguale per tutti i nodi
Tuttavia, quando il ring non è pieno, x non
conosce l’esatta posizione dei vicini dei vicini
ma ne ha una buona stima.
H-Chord 2i
2i+1 2i+1
2i+2
Chord
10
9
8
7
6
5
4
3
2
1
0
R-Chord
Greedy
R-Chord NoN
R-Chord SP
H-Chord
Greedy
H-Chord NoN
log N
18
16
14
12
10
8
6
H-Chord SP
4
2
hops
H-Chord
H-Chord
9
Chord
8
6
R-Chord
Greedy
R-Chord NoN
5
R-Chord SP
hops
7
4
2
H-Chord
Greedy
H-Chord NoN
1
H-Chord SP
3
0
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
log N
H-Chord
Perchè H-Chord e non Chord?
Svantaggi R-Chord


Come mantenere la lista dei vicini dei vicini?
No fast bootstrap
Non è possibile fare fast bootstrap perché le tabelle di
routing sono diverse, tuttavia se due nodi x, y generano
due valori hash abbastanza vicini (H(x)H(y)) allora le
loro tabelle sono simili.
I problemi sono:
Cosa vuol dire “abbastanza vicini”
Come trovare un vicino con hash “abbastanza vicino”
Sistemi P2P uniformi
Vantaggi:





Facili da implementare e da analizzare;
Algoritmo di routing semplice (greedy);
Routing locale, la procedura di lookup interessa solo i nodi
che si trovano fra sorgente e destinazione;
Non c’è congestione sui nodi, vale a dire il traffico generato
dai messaggi di lookup è più o meno uguale per tutti i nodi.
Fast bootstrap:
Poiché tutti i nodi utilizzano gli stessi jump, è possibile utilizzare
la tabella di routing del proprio predecessore per velocizzare
notevolmente l’operazione di join;
Svantaggi:

Sfortunatamente non sono gli algoritmi più efficienti.
10
Koorde base k
01
11
00
Scegliendo k = O(log n):


02
Grado = O(log n)
APL = O(log n / log (log n))
Svantaggi



Bisogna stimare n a priori;
Non è possibile cambiare il grado in un
sistema attivo;
E’ molto complicato stabilizzare la rete;
12
b=2
k=3
20
21
22
R-Chord
Vantaggi:





Algoritmo di routing locale
Algoritmo di routing semplice
Efficiente
Non è necessaria la stima di log n
L’algoritmo di stabilizzazione è identico a
quello di Chord
Svantaggi


Come mantenere la lista dei vicini dei vicini?
No fast bootstrap
H-Chord
Vantaggi





Algoritmo di routing locale
Algoritmo di routing semplice
Efficiente
Non è necessaria la stima di log n
L’algoritmo di stabilizzazione è identico a
quello di Chord
Svantaggi

No fast bootstrap ????
Hc-Chord