Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Network probability problem

  1. Jan 23, 2007 #1
    1. The problem statement, all variables and given/known data
    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?

    3. 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.

  2. jcsd
  3. Jan 23, 2007 #2


    User Avatar
    Science Advisor
    Homework Helper

    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"
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook