Optimal Algorithms for Broadcast and Gossip in the Edge-Disjoint Path Modes

AbstractThe communication power of the one-way and two-way edge-disjoint path modes for broadcast and gossip is investigated. The complexity of communication algorithms is measured by the number of communication steps (rounds). The main results achieved are the following: 1. For each connected graphGnofnnodes, the complexity of broadcast inGn,Bmin(Gn), satisfies ⌈log2n⌉⩽Bmin(Gn)⩽⌈log2n⌉+1. The complete binary trees meet the upper bound, and all graphs containing a Hamiltonian path meet the lower bound. 2. For each connected graphGnofnnodes, the one-way (two-way) gossip complexityR(Gn) (R2(Gn)) satisfies⌈log2n⌉⩽R2(Gn)⩽2·⌈log2n⌉+1,1.44...log2n⩽R(Gn)⩽2·⌈log2n⌉+2.All these lower and upper bounds are shown to be sharp up to 1. 3. All planar graphs ofnnodes and degreehhave a two-way gossip complexity of at least 1.5log2n−log2log2n−0.5log2h−8, and the two-dimensional grid ofnnodes has the gossip complexity 1.5log2n−log2log2n±O(1); i.e., two-dimensional grids are optimal gossip structures among planar graphs of bounded degree. Some upper bounds are also obtained for the one-way mode. 4. Thed-dimensional grid,d⩾3, ofnnodes has the two-way gossip complexity (1+1/d)·log2n−log2nlog2n±O(d)