2.8 Messages Dissemination

To share messages from a source vertex to other connected vertices of a graph, communication between vertices can be achieved using different protocols. This thesis considers message flooding and probabilistic gossip protocols.

Flooding Protocol

In a flooding protocol, each received message is sent through all outgoing edges, except the one on which it arrived [TW⁺96]. Therefore, each vertex acts both as a transmitter and a receiver of the message, forwarding every received message to its neighbors, except the one that sent it the message.

There are two types of flooding: uncontrolled and controlled [CBL18].

• Uncontrolled flooding: vertices forward messages to all of their neighbors, except the one from which it received the message.
• Controlled flooding: vertices remember received messages and, therefore, drop already received messages.

While flooding protocols are easy to implement, they can be expensive in terms of wasted bandwidth.

To reduce the number of messages sent, flooding protocols can use a hop count measure contained in the header of messages, that is decremented at each hop, i.e. each time the message is sent from a vertex to all its neighbors. When the hop counter reaches 0, the message stops being sent and is discarded.

Gossip Protocol

Gossip protocols can be used to reduce the cost of flooding protocol, based on the way epidemics spread [Dem⁺87]. Also called epidemic protocols, gossip protocols spread information in a manner similar to a viral infection in a biological population, where a virus plays the role of a piece of information, i.e. a message, and an infection plays the role of learning about the information, i.e. receiving a message [SGK11].

There are two main types of gossip protocols:

• Random probabilistic dissemination, suitable for Peer-to-Peer (P2P) systems, where a node randomly chooses which of its neighbors to send the information. Kermarrec et al. [KMG03] consider that each node has a randomized partial knowledge of the system, i.e. a list of process identifiers stored locally. Then, a process that must forward a received information, randomly picks k processes from its local list and sends them the information. This mechanism is called peer-sampling service and provides a primitive that returns a random process drawn from the list [Jel⁺07].
• Haas et al. [HHL02] proposed several gossip protocols for ad hoc networks that use probabilities. Combined with the number of hops or the number of times the same message is received, the protocols choose if a node broadcast a message to all its neighbors or not, reducing thus the number of messages propagated in the system. The authors show that gossiping with a probability between 0.6 and 0.8 ensures that almost every node of the system gets the message, with up to 35% fewer messages in some networks compared to flooding.

The difference between Kermarrec et al. algorithms and Haas et al. algorithms, is that Haas et al. algorithms gossip a message to all its neighbors using a probability, whereas Kermarrec et al. algorithms gossip a message to a subset of neighbors randomly chosen.

In this thesis, a probabilistic broadcast from Haas et al. is used to reduce the number of messages exchanged. This type of gossip is more suitable to wireless networks, since a message is received by all nodes within the wireless transmission range of the sending node.

Table of Contents