Tighter Time Bounds on Broadcasting in Torus Networks in Presence of Dynamic Faults
Gianluca De Marco · Parallel Processing Letters · 2000
We consider the problem of broadcasting in a network G under the hypothesis that each vertex can inform in one unit of time all of its neighbours and that any number of message transmissions, less than the edge-connectivity of G, may fail during each time unit. In particular, we study broadcasting in the n-dimensional k-ary torus, a popular topology for link connections in communication networks. We prove that under the above strong fault-assumption, if k is even and polynomially limited in n, and n is sufficient large, broadcasting in the n-dimensional k-ary torus can be accomplished in time , where is the diameter of the n-dimensional k-ary torus.