TY - JOUR
T1 - Tree search on an atomic model for message passing
AU - Liu, Pangfeng
AU - Aiello, William
AU - Bhatt, Sandeep
PY - 2001
Y1 - 2001
N2 - This paper presents a simple atomic model of message-passing multicomputers. Within one synchronous time step each processor can receive one atomic message, perform local computation, and send one message. When several messages are destined to the same processor, then one is transmitted and the rest are blocked. Blocked messages cannot be retrieved by their sending processors; each processor must wait for its blocked message to clear before sending more messages into the network. Depending on the traffic pattern, messages can remain blocked for arbitrarily long periods. The model is conservative when compared with existing message-passing systems. Nonetheless, we prove linear message throughput when destinations are chosen at random; this rigorously justifies an instance of folklore. Based on this result we also prove linear speedup for backtrack and branch-and-bound searches using simple randomized algorithms.
AB - This paper presents a simple atomic model of message-passing multicomputers. Within one synchronous time step each processor can receive one atomic message, perform local computation, and send one message. When several messages are destined to the same processor, then one is transmitted and the rest are blocked. Blocked messages cannot be retrieved by their sending processors; each processor must wait for its blocked message to clear before sending more messages into the network. Depending on the traffic pattern, messages can remain blocked for arbitrarily long periods. The model is conservative when compared with existing message-passing systems. Nonetheless, we prove linear message throughput when destinations are chosen at random; this rigorously justifies an instance of folklore. Based on this result we also prove linear speedup for backtrack and branch-and-bound searches using simple randomized algorithms.
KW - Parallel communication model
KW - Parallel tree search
KW - Randomized algorithm
UR - http://www.scopus.com/inward/record.url?scp=0036220257&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0036220257&partnerID=8YFLogxK
U2 - 10.1137/S0097539799358070
DO - 10.1137/S0097539799358070
M3 - Article
AN - SCOPUS:0036220257
SN - 0097-5397
VL - 31
SP - 67
EP - 85
JO - SIAM Journal on Computing
JF - SIAM Journal on Computing
IS - 1
ER -