2
$\begingroup$

I am trying to find the expected number of rounds for a system to finish a process. Lets say N = 100. One process starts off the program by sending a message to another random process. The choice is made at random so a process can potentially send a message multiple times to another process.

When a process receives a message, it will also send a message to other processes. Since collision can occur (i.e. multiple processes sending a message to a same process), and this is where I am kind of confused.

If at round R - X processes have the message and Y processes don't. I am trying to find how many processes might get the message at round R + 1, and expand it to the total amount of rounds needed. Each process has a 1/100 chance of receiving a message so there is a finite possibility but I am confused on how to calculate this. Any hints?

  • 1
    I don't get what is random in your problem. Is it the program to whom the message is sent, or is it wether a program sends a message, or is it the amount of messages a program sends, or is it a combination of any of all three above? I think once you have figured that out and what probability you assign to each event, you'll be less confused.2012-09-12
  • 0
    What is random is the number of rounds required to complete a process. What is missing is the definition of completing a process. Apparently Hagen knows because he gave Paul (the OP) a satisfactory answer.2012-09-12
  • 0
    There has been recent interest in _gossip_ and how a single piece of information spreads across a network. See, for example, the paper A.D. Sarwate, A.G. Dimakis, The Impact of Mobility on Gossip Algorithms, IEEE Transactions on Information Theory 58(3): pp. 1731--1742, March 2012 (the lead author is my son).2012-09-12

1 Answers 1

2

A naive estimate would say that on average a share of $\frac Xn$ of the $Y$ processes will learn the message, thus one expects the number $X$ to grow to $X+\frac{XY}n$. Thus as long as $X\ll n$, the number will grow exponentially like $2^R$; if $X\approx \frac n2$, it will grow slower, but $Y$ will decrease by about half each step; and as $Y$ gets smaller, it will decrease even faster. Therefore a rough upper bound is that you probably need at most $2\log_2 \frac n2$ rounds.

  • 0
    Ah that makes sense. I was thinking of it as not decreasing by half each step and was getting very confused. Thanks for the explanation.2012-09-12