Multiple message broadcasting with generalized Fibonacci trees

Abstract

We present efficient algorithms for broadcasting multiple messages. We assume n processors, one of which contains m packets that it must broadcast to each of the remaining n - 1 processors. The processors communicate m rounds. In one round each processor is able to send one packet to any other processor and receive one packet from any other processor. We give a broadcasting algorithm which requires m + log n + 3 log log n + 15 rounds. In addition, we show a simple lower bound of m+ ⌈log n⌉ - 1 rounds for broadcasting m this model.