Tree search on an atomic model for message passing

This paper presents a simple atomic model of message-passing multicomputers . Within one synchronous time step each processor can receive one atomic me ssage, perform local computation, and send one message. When several messag es are destined to the same processor, then one is transmitted and the rest are blocked. Blocked messages cannot be retrieved by their sending process ors; each processor must wait for its blocked message to clear before sendi ng more messages into the network. Depending on the traffic pattern, messag es can remain blocked for arbitrarily long periods. The model is conservative when compared with existing message-passing syste ms. Nonetheless, we prove linear message throughput when destinations are c hosen at random; this rigorously justifies an instance of folklore. Based o n this result we also prove linear speedup for backtrack and branch- and-bo und searches using simple randomized algorithms.