Name
Abstract | ||
|---|---|---|
In this paper we compare two methods for generating finite families of random subsets according to some sequence of independent random variables 茂戮驴1, ..., 茂戮驴ndistributed uniformly over the interval [0,1]. The first method called uniform splituses 茂戮驴ivalues straightforwardly to determine points of division of [0,1] into subintervals. The second method called binary splituses 茂戮驴ionly to perform subsequent divisions of already existing subintervals into exact halves. We show that the variance of lengthes of obtained intervals in the first method is approximately $\frac{1}{n^2}$ and that the variance of lengthes of obtained intervals in the second method is approximately $\frac{1}{n^2}(\frac{1}{\ln 2}-1)$.The uniform split is used in the Chord peer-to-peer protocol while the binary split is used in the CAN protocol. Therefore our analysis applies to this protocols and shows that CAN has a better probabilistic properties than Chord. We propose also a simple modification of the Chord protocol which improves its statistical properties. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/978-3-540-74208-1_30 | APPROX-RANDOM |
Keywords | Field | DocType |
uniform split,binary split,uniform splituses,binary splituses,exact half,finite family,chord protocol,random subsets,chord peer-to-peer protocol,independent random variable,p2p protocols,p2p | Discrete mathematics,Combinatorics,Random variable,Probabilistic logic,Chord (music),Mathematics,Chord (peer-to-peer),Binary number | Conference |
Volume | ISSN | Citations |
4627 | 0302-9743 | 4 |
PageRank | References | Authors |
0.48 | 8 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jacek Cichoń | 1 | 63 | 8.06 |
| Marek Klonowski | 2 | 200 | 32.36 |
| Lukasz Krzywiecki | 3 | 59 | 15.12 |
| Bartłomiej Różański | 4 | 4 | 0.82 |
| Paweł Zieliński | 5 | 274 | 19.73 |