Paper detail

On spreading rumor in heterogeneous systems

In this paper we consider a model of spreading information in heterogeneous systems wherein we have two kinds of objects. Some of them are active and others are passive. Active objects can, if they possess information, share it with an encountered passive object. We focus on a particular case such that active objects communicate independently with randomly chosen passive objects. Such model is motivated by two real-life scenarios. The first one is a very dynamic system of mobile devices distributing information among stationary devices. The second is an architecture wherein clients communicate with several servers and can leave some information learnt from other servers. The main question we investigate is how many rounds is needed to deliver the information to all objects under the assumption that at the beginning exactly one object has the information? In this paper we provide mathematical models of such process and show rigid and very precise mathematical analysis for some special cases important from practical point of view. Some mathematical results are quite surprising -- we find relation of investigated process to both coupon collector's problem as well as the birthday paradox. Additionally, we present simulations for showing behaviour for general parameters