# Calculating expected number of rounds

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?

-
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. –  Raskolnikov Sep 12 '12 at 21:04
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. –  Michael Chernick Sep 12 '12 at 21:24
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). –  Dilip Sarwate Sep 12 '12 at 22:45

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.