Network probability problem

  • Thread starter chrisg
  • Start date
  • #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!
 

Answers and Replies

  • #2
AlephZero
Science Advisor
Homework Helper
7,002
293
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"
 

Related Threads on Network probability problem

Replies
4
Views
2K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
7
Views
2K
  • Last Post
Replies
0
Views
2K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
13
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
2
Views
2K
Replies
8
Views
4K
Top