OPTIMAL-ALGORITHMS FOR BROADCAST AND GOSSIP IN THE EDGE-DISJOINT PATHMODES

The communication power of the one-way and two-way edge-disjoint path modes for broadcast and gossip is investigated. the complexity of comm unication algorithms is measured by the number of communication steps (rounds), the main results achieved are the following: 1. For each con nected graph G(n) of n nodes, the complexity of broad cast in G(n), B- min(G(n))(r) satisfies [log(2)n] less than or equal to B-min(G(n)) les s than or equal to [log(2)n] + 1. The complete binary trees meet the u pper bound, and all graphs containing a Hamiltonian path meet the lowe r bound. 2. For each connected graph G(n) of n nodes, the one-way (two -way) gossip complexity R(G(n)) (R(2)(G(n))) satisfies [log(2)n] less than or equal to R(2)(G(n)) less than or equal to 2 .[log(2)n] + 1, 1. 44...log(2)n less than or equal to R(G(n)) less than or equal to 2 .[l og(2)n] + 2. All these lower and upper bounds are shown to be sharp up to 1.