- #1

- 3

- 0

## Homework Statement

Consider an unstructured overlay network in which every node randomly chooses c neighbors. To search for a file, a node floods a request to its neighbors and requests those to flood the request once more. How many nodes will be reached?

## Homework Equations

## The Attempt at a Solution

I have the solution already (from the textbook) but it doesn't explain it very well. Can you please explain this solution to me? I'm not understanding the probability part (I understand the c*c-1).

TEXTBOOK SOLUTION:

An easy upper bound can be computed as c*(c -1), but in that case we ignore the fact that neighbors of node P can be each other's neighbor as well. The probability q that a neighbor of P will send a message only to nonneighbors of P is 1 minus the probability of sending it to at least one neighbor of P:

[tex] q = 1 - \sum\limits_{k=1}^{c-1} \binom{c-1}{k} \left( \frac{c}{N-1}\right)^k \left( 1-\frac{c}{N-1} \right)^{c-1-k} [/tex]

In that case, this flooding strategy will reach [itex]c \times q(c -1) [/itex] nodes. For example, with c = 20 and N = 10, 000, a query will be flooded to 365.817 nodes.

So, that's the textbook's answer.... but I'm

**really**confused! I don't understand the probability part. I mean, I understand what it's trying to do, but I'm totally lost on where the numbers or summation is coming from. I would REALLY appreciate an explanation of this! I think it's trying to enumerate all combinations and give them a probability in some way, but I'm lost at how they arrived at this. Our teacher said this was an "almost trivial" problem.... and when I submitted my homework, I submitted [itex] c \times (c-1) [/itex] and then I saw this and almost fell over.

Thanks in advance!