Multiple message broadcasting in the postal model

Abstract

Broadcasting is a widely used operation in many message-passing systems. Most existing broadcasting algorithms, however, do not address several emerging trends in distributed-memory parallel computers and high-speed communication networks. These trends include (i) treating the system as a fully connected collection of processors, (ii) packetizing large data into sequences of messages, and (iii) tolerating communication latencies. This paper explores the broadcasting problem in the postal model that addresses these issues. The authors provide two algorithms for broadcasting m messages in a message-passing system with n processors and communication latency lambda. A lower bound on the time for this problem is (m-1)+f/sub lambda /(n), where f/sub lambda /(n) is the optimal time for broadcasting one message. They present algorithm PARTITION that takes at most 2m+f/sub lambda /(n)+O( lambda ) time, and algorithm D-D-TREES that takes at most m+2f/sub lambda /(n)+O( lambda ) time.