- #1

- 1

- 0

## Homework Statement

I have a question that's stumped me for a bit. Suppose we have a peer-to-peer network that's used to store replicas of files (such as p2p networks do) that are replicated randomly. And suppose we have the following:

peer 1 has files 1, 3, 5

peer 2 has files 2, 4, 5

peer 3 has files 3 , 1, 2

peer 4 has files 4 , 2, 1

peer 5 has files 5, 3, 4

In the example above, we have 3 replicas, but for a system of N peers we could have up to N replicas of each peer with each peer containing the same number of replicas as any other peer.

The question is, with N peer, K replicas and M peer failures (suppose they drop out simultaneously but independently), what is the probability that the remaining peers contain at LEAST one replica of all of the original peers?

## The Attempt at a Solution

Intuitively, I think that for the simple case with N peers, where the number of replicas (K) == number of failures (M), we can express the probability of having at least one replica of each peer remaining as:

1 - (N/Choose(N,M))

For the general case, however, I'm stumped. I suspect that it's a chain of probabilities, but I'm not positive on that one. Any suggestions would be appreciated.

Thanks!