Fault-tolerant Gossip Graphs Based on Wheel Graphs - Hovnanyan, Vilyam H.; Poghosyan, Suren S.; Poghosyan, Vahagn S. (Mathematical Problems of Computer Science, 2021)
The gossip problem (telephone problem) is an information dissemination problem where each of n nodes of a communication network has a unique piece of information that must be transmitted to all the other nodes using two-way communications (telephone calls) between the pairs of nodes. Upon a call between the given two nodes, they exchange the whole information known to them at that moment. In this paper, we investigate the k-fault-tolerant gossip problem, which is a generalization of the gossip problem, where at most k arbitrary faults of calls are allowed. The problem is to find the minimal number of calls ¿(n; k) needed to guarantee the spread of whole information. We constructed a k-fault-tolerant gossip scheme (sequences of calls) to find the upper bounds of ¿(n; k), which improves the previously known results for some particular small values of n and k.