Tighter Upper Bounds for the Minimum Number of Calls and Rigorous Minimal Time in Fault-Tolerant Gossip Schemes

Abstract

The gossip problem (telephone problem) is an information dissemination problem in which 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. During 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 $\tau (n,k)$ needed to guarantee the $k$-fault-tolerance. We construct two classes of $k$-fault-tolerant gossip schemes (sequences of calls) and found two upper bounds of $\tau (n,k)$, which improve the previously known results. The first upper bound for general even $n$ is $\tau (n,k)\le 1/2n\lceil {\log }_{2}n\rceil +1/2nk$. This result is used to obtain the upper bound for general odd $n$. From the expressions for the second upper bound it follows that $\tau (n,k)\le 2/3nk+O(n)$ for large $n$. Assuming that the calls can take place simultaneously, it is also of interest to find $k$-fault-tolerant gossip schemes, which can spread the full information in minimal time. For even $n$ we showed that the minimal time is $T(n,k)=\lceil {\log }_{2}n\rceil +k$.

19 pages, 5 figures