Distributed Algorithms for Multimessage Multicasting

We consider the multimessage multicasting over the $n$ processor complete (orfully connected) static network when the forwarding of messages is allowed, andinitially each processor only knows the messages it needs to send and theirdestinations. We present an efficient distributed algorithm to route themessages for every degree $d$ problem instance with total expectedcommunication time $O(d + \\log n)$, where $d$ is the maximum number of messagesthat each processor may send (or receive).Our routing algorithm consists of three phases. In the first phase theprocessors exchange messages to learn some basic global information. In thesecond phase each processor forwards its messages to transform the problem to amultimessage unicasting problem of degree $d$. The third phase uses a wellknown distributed algorithm to transmit all the unicasting messages.