Optimal bounds on the gain of permitting dynamic allocation of communication channels in distributed computing

Consider a distributed system consisting of n computers connected by a numb er of identical broadcast channels. All computers may receive messages from all channels. We distinguish between two kinds of systems: systems in whic h the computers may send on any channel (dynamic allocation) and system whe re the send port of each computer is statically allocated to a particular c hannel. A distributed task (application) is executed on the distributed sys tem. A task performs execution as well as communication between its subtask s. We compare the completion time of the communication for such a task usin g dynamic allocation and k(d) channels with the completion time using stati c allocation and k(s) channels. Some distributed tasks will benefit very mu ch from allowing dynamic allocation, whereas others will work fine with sta tic allocation. In this paper we define optimal upper and lower bounds on t he gain (or loss) of using dynamic allocation and k(d) channels compared to static allocation and k(s) channels. Our results show that, for some tasks , the gain of permitting dynamic allocation is substantial, e.g. when k(s) = k(d) = 3, there are tasks which will complete 1.89 times faster using dyn amic allocation compared to using the best possible static allocation, but there are no tasks with a higher such ratio.