1 Introduction
Gossiping, or rumor-spreading, is a simple stochastic process for dissemination of information across a network. In a round of gossip, each node chooses a single, usually random, neighbor as its communication partner according to a gossip algorithm (e.g., selecting a random neighbor). Once a partner is chosen the node calls its partner and a limited amount of data is transferred between the partners, as defined by the gossip protocol. Three basic actions are considered in the literature: either the caller pushes information to its partner (push), pulls information from the partner (pull), or does both (push&pull). In the most basic information dissemination task, a token or a rumor in placed arbitrary in the network and we are interested in the number of rounds and message transmissions until all nodes in the network receive the rumor. The selection of the protocol can lead to significant differences in the performance. Take for example the star graph, let nodes call a neighbor selected uniformly at random and assume the rumor is placed at one of the leafs. It is easy to see that both push and pull will require ω(n) rounds to complete the spreading of a single rumor while push&pull will take only two rounds.
Somewhat surprisingly, but by now well understood, randomized rumor-spreading turned out to be very efficient in terms of time and message complexity while keeping robustness to failures [13,23]. In addition, this type of algorithms are very simple and distributed in nature so it is clear why gossip protocols have gained popularity in recent years and have found many applications both in communication networks and social networks. To name a few examples: updating a database replicated at many sites [9,23], resource discovery [22], computation of aggregate information [24], multicast via network coding [8], membership services [19], or the spread of influence and gossip in social networks [6,25].
