The gossip protocol works as follows:
- Start by having 1 infected node and n-1 uninfected nodes (a total of n nodes)
- In each round t every infected node gossips to b random nodes. Nodes that were uninfected and receive the gossip become infected.
I'm trying to come up with a formula for the remaining numbers of uninfected nodes after each round t.
What I have so far is this:
x(t) = number of uninfected nodes after round t
$U_v(t)$ = probability that node v remains uninfected after round t
Given that any gossip message has a probability of $1-\frac{1}{n}$ of reaching node v and given that each round $b*(n-x(t))$ independent gossips are being sent it follows that:
$$U_v(t+1) = (1-\frac{1}{n})^{b*(n-x(t))}$$
Given that at the beginning of round t+1 there are x(t) uninfected nodes and that the probability of any uninfected node of remaining uninfected is $U_v(t+1)$ we can apply the linearity of expectation and conclude that:
$$x(t+1) = x(t) * (1-\frac{1}{n})^{b*(n-x(t))}$$
Now for my question: can the above recurrence be reduced any further (hopefully getting rid of the recurrence)?
I think you are looking for logistic functions, which are frequently used to model spread of things and population growth. I'm not sure if your recurrence can be reduced any further, but you could probably find some way to make your problem into a logistic function.