The relationship between the gossip complexity in vertex-disjoint paths mode and the vertex bisection width

AbstractThe one-way and two-way communication modes used for sending messages to processors of interconnection networks via vertex-disjoint paths in one communication step are investigated. The complexity of communication algorithms is measured by the number of communication steps (rounds). This paper reveals a direct relationship between the gossip complexity and the vertex bisection width. More precisely, the main results are the following: 1.1. We prove that for any 2-way gossip algorithm running on a graph Gn, k of n nodes and vertex bisection width k, the lower bound on the number of rounds is 2 log2 n-log2 k-log2 log2 k-6.2.2. We prove that there is a graph Gn,k of n nodes and vertex bisection width k such that there exists a 2-way gossip algorithm for it running in 2 log2 n-log2 k-log2 log2 k + 7 rounds.3.3. We prove that for any 1-way “well-structured” gossip algorithm running on a graph Gn,k of n nodes and vertex bisection width k, the lower bound on the number of rounds is 2 log2 n-0.56 … (log2 k + log2 log2 k)-O(1) (to the best of the authors' knowledge, to date all gossip algorithms designed in vertex-disjoint paths mode have been “well-structured”).4.4. We prove that there is a graph Gn,k of n nodes and vertex bisection width k such that there exists a 1-way gossip algorithm for it running in 2 log2 n-0.56 … (log2 k + log2 log2 k) + O(1) rounds.These results improve the previous results and prove their optimality with respect to the class of graphs Gn,k of n nodes and vertex bisection width k.Tight lower bounds on one-way “well-structured” gossip algorithms in d-dimensional grids, d ⩾ 3, several results for gossiping in graphs of constant degree and planar graphs, as well as similar results for the related edge-disjoint paths mode follow