Add Determinism in Gossip-Based Dissemination Algorithms

Semester project

Gossip-based dissemination algorithms have an inherently random aspect in their dissemination. Imagine a system with N nodes and a node p that wants to gossip a message to every other node in the system. The node p first contacts k random neighbors. After this first round, not only will the source node p continue to contaminate other k random neighbors, but the k initial neighbors of p, in turn, will also contaminate k random neighbors.

We want to experiment introducing bias in random choices of neighbors and events to improve fairness, that is, we do not want to contact neighbors in a completely random manner.

For each node, we introduce a notion of interest function, which returns true if an event is considered interesting to a node and false otherwise. When nodes want to contact each other to share events, the interest function is first exchanged so that “mostly” interesting events are given to “interested” nodes. Of course, the system must still make sure that every node in the system has a chance of receiving all interesting events. Thus, some of the exchanged events must be “non-interesting” to still have a chance of contaminating other nodes that could be interested.

Language: Java

Responsible: Maxime Monod

Project intended for 1 student

Le superviseur parle aussi français…