Algorithm and Analysis of Multiple Messages Broadcast in the Multiport Model
多端口模式下的多消息广播算法与分析

1 引言网络通信一般可分为五类,单播(Unicast)、组播(Multi-cast)、汇播(Concast)、群播(MultiPoint to MultiPoint)和广播(Broadcast)。其中,广播通信是实现一点对所有点通信(one-to-all Broadcast)的简便有效形式,在很多并行计算问题,如神经网络、优化、线性代数等问题中的使用非常频繁。这篇文章的依据是文1]中介绍的消息机制下多端口(multiport model)系统中的一种广播算法——k树算法。k树算法主要基于n结点扫描树的构造以及树结点的命名,时间复杂度是m/k] max(log_k(n 2k)],2)。实验证明,这种算法虽然不是最优的,其时间复杂度与最短广播周期log_(k 1)