BOUNDS ON THE EFFICIENCY OF MESSAGE-PASSING PROTOCOLS FOR PARALLEL COMPUTERS

This paper considers the problem of creating message-passing protocols for parallel computers. It is assumed that the processors are connect ed by a network that provides guaranteed delivery of every message, pr ovided that each message delivered by the network is removed by the re ceiving processor unconditionally and in finite time. Two models of me ssage passing are considered, namely, a selective model in which the r eceiver specifies the source of the message and a nonselective model i n which the receiver accepts messages from all sources. We consider on ly space-efficient protocols in which each processor has storage for a constant number of messages acid message headers. We present three ma in results. First, we give a protocol for the selective model that per forms a constant amount of communication per send or receive posted by the application. Second, we prove that no such efficient protocol exi sts for the nonselective model. Third, we present a protocol for the n onselective model that performs a logarithmic amount of communication per send or receive posted by the application.