Optimal broadcast in α-port wormhole-routed mesh networks

We consider the problem of broadcasting in 2- and 3-dimensional mesh networks with the wormhole-routing capability. Our model assumes that each node is capable of communicating with α nodes simultaneously where α is a given integer with 1⩽α⩽4 for 2-dimensional meshes and 1⩽α⩽6 for 3-dimensional meshes. We give broadcasting algorithms that use optimal number of phases (if each side of the mesh is (α+1)⁺) or at most optimal number plus two phases (otherwise). Our algorithms require the predetermined location of the source node and this assumption can be relaxed by allowing one additional initial phase