Designing broadcasting algorithms in the postal model for message-passing systems

Abstract

In many message-passing systems, such as distributed-memory parallel computers and high-speed communication networks, the exact structure of the underlying communication network may be ignored. In such systems it is assumed that the network creates a complete communication graph between the processors, in which passing messages is associated with communication latencies. We propose the postal model for communication in such systems. This model incorporates a latency parameter λ ≥ 1 that measures the inverse of the ratio between the time it takes an originator of a message to send it and the time that passes until the recipient of the message receives it. We demonstrate how to use the framework of the postal model to design broadcasting algorithms. We present an optimal-time algorithm for broadcasting one message in systems with n processors and communication latency λ, whose running time is Θ(λ log n/log(λ+1)). For broadcasting m ≥ 1 messages, we first examine several natural generalizations of the algorithm for broadcasting one message. We then analyze a family of broadcasting algorithms that are based on degree-d trees. All the algorithms described in this paper are practical, asynchronous, event-driven algorithms that preserve the order of messages.