Broadcast in fast networks

摘要

The current trend in network technology is to implement as much of the switching function as possible directly in specialized high-speed hardware. A broadcast algorithm for such a network that is tolerant of failures in the form of message loss is presented. The model used is based on the one introduced by Cidon et al. (see Proc. of Seventh Annual ACM Symp. on Principles of Distributed Comput., Toronto, Canada. P.75-89, 1988); the hardware functions assumed are simple enough to be implemented in high-speed logic. The basic idea is to forward broadcast messages directly in hardware, thereby avoiding software-introduced delays. Software intervention (possible only after the broadcasted message has already been forwarded) is required only to ensure termination in case of failures. With high probability, the broadcast will terminate in time O(n tau /sub max/), where n is the number of nodes and tau /sub max/ is an upper bound on (variable) message delivery time across a link.