Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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
add comment

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
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. –  Paul Sep 12 '12 at 21:15
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.