(CAN) The upper bound Lemma for the size

Lecture

(CAN) The upper bound Lemma for the size

Beitragvon tbk » Di 17. Nov 2015, 18:45

Hi,

i have some questions about the upper bound lemma for the size in CAN:

The lemma says, that for a small probability (p=1/(n^c)) a rectangle of size (c ln n )/n is not further divided.

This will be proofed with the probability that no peers falls into an area R
P_(R,n) <= e^(-nVol(R))

I get it, that if we plug in (c ln n)/n for the Vol(R) we get P_(R,n) = 1/(n^c)

But in between there is a statements:

Every peer receives at most c (ln n) m/n elements if all m elements are stored equally distributed over the area
while the average peer stores m/n elements

My explanation for that is:
1) While the average peer stores m/n elements:
because the average or expected size is 1/n and m elements equally distributed over the area => m/n?

2) Every peer receives at most c (ln n) m/n elements:
because we assume that all areas are c (ln n) larger?

So if we combine all together then we can get, that:

A) a area with size c (ln n)/n is with a very small probability not further divided
and because c (ln n)/n > average or expected size 1/n this is the upper bound

B) number of data stored on a peer is bounded by c (ln n) times the average amount
because of 1) and 2)

But what is the big picture of this ... what is so special about c (ln n)?
tbk
Nibble
 
Beiträge: 4
Registriert: Di 12. Aug 2014, 14:47

Re: (CAN) The upper bound Lemma for the size

Beitragvon professor » Do 19. Nov 2015, 11:29

The noted bounds come from an analysis from the Chernoff bounds. Maybe you discuss this question in the exercise next week? Or come to my consultation hour.
professor
7-Bit
 
Beiträge: 71
Registriert: Mo 17. Okt 2011, 13:57


Zurück zu Peer-to-Peer Networks

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 1 Gast

cron