Network probability problem

[chrisg]

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!

 

[AlephZero]

It might be easier to think about just one file being replicated.

In that case, you have K servers that have the file and N-K that do not.

It's the same type of problem as "choosing M balls at random from a bag containg K black balls and N-K white balls"