Reliable Broadcast Algorithms for HARTS

Abstract

The problem of broadcasting in point-to-point interconnection networks with virtual cut-through switching is considered. A simple extension of virtual cut-through is proposed, which provides good support for broadcasting in mesh-connected multicomputers. An implementation of this extension (termed a broadcast primitive) for a hexagonal mesh multicomputer called HARTS, that uses virtual cut-through switching, is also presented. Based on this primitive, a set of broadcast algorithms is developed for the hexagonal mesh topology These algorithms deliver multiple copies of a message from a source node to every other node in the hexagonal mesh through disjoint paths. They can be used for broadcasting in the presence of faulty nodes/links, even when the identity of the faulty components is not known. The performance of these algorithms has been analyzed and compared with the performance of other possible broadcast algorithms. © 1991, ACM. All rights reserved.