We consider the broadcasting operation in point-to-point packet-switched parallel and distributed networks of processors. We develop a general technique for the design of optimal broadcast algorithms on a wide range of such systems. Our technique makes it easier to design such algorithms and, furthermore, provides tools that can be used to derive precise analyses of their running times. As direct applications of this method we give an exact analysis of a known algorithm for the POSTAL model, and design and analyze an optimal broadcast algorithm for the MULTI PORT MULTI-MEDIA model. We then show how our method can be applied to networks with different underlying topologies, by designing and giving an exact analysis of an optimal broadcast algorithm for the OPTICAL RING.
展开▼
机译：我们考虑处理器的点对点分组交换并行和分布式网络中的广播操作。我们开发了一种广泛的系统上用于设计最佳广播算法的通用技术。我们的技术使设计此类算法变得更加容易，此外，还提供了可用于得出其运行时间的精确分析的工具。作为此方法的直接应用，我们对POSTAL模型的已知算法进行了精确分析，并为MULTI PORT MULTI-MEDIA模型设计和分析了最佳广播算法。然后，我们将通过设计并给出用于OPTICAL RING的最佳广播算法的精确分析，来展示如何将我们的方法应用于具有不同基础拓扑的网络。
展开▼
