Broadcasting in butterfly and deBruijn networks

AbstractBroadcasting is the process of message dissemination in a communication network in which a message originated by one processor is transmitted to all processors of the network. In this paper, we present a new lower bound of 1.7417m for broadcasting in the butterfly network of dimension m. This improves the best known lower bound of 1.5621m. We also describe an algorithm which improves the upper bound from 2m to 2m − 1. This is shown to be optimal for small dimensions m.In addition, the presented lower bound technique is used to derive non-trivial lower bounds for broadcasting in the deBruijn network of dimension m. An upper bound of 1.5m + 1.5 is well known for this network. Here, we are able to improve the lower bound from 1.1374m to 1.3171m