Circuit-switched broadcasting in d-dimensional tori and meshes
Ju-Young L. Park, Sang‐Kyu Lee, Hyeong‐Ah Choi · 2002
Considers the problem of broadcasting on torus and mesh networks using circuit-switched, half-duplex, and link-bound communication. The authors first discuss the optimum broadcasting time and then present a broadcasting algorithm for a (2d+1)/sup pspl times/(2d+1)/sup pspl times/.../spl times/(2d+1)/sup p/ d-dimensional torus. This algorithm requires pd time steps to complete the broadcasting, which is the optimum. Using this algorithm, the authors also show that the broadcasting on a (2d+1)/sup pspl times/(2d+1)/sup pspl times/.../spl times/(2d+1)/sup p/ d-dimensional mesh can be done in 2pd time steps, which is within a factor of 2 of the optimum.>