Tree search on an atomic model for message passing

作     者：Liu, PF Aiello, W Bhatt, S 

作者机构：Natl Taiwan Univ Dept Comp Sci & Informat Engn Taipei 106 Taiwan AT&T Labs Res AT&T Shannon Ctr Florham Pk NJ 07932 USA Akamai Technol Inc Cambridge MA 02139 USA 

出 版 物：《SIAM JOURNAL ON COMPUTING》 (工业与应用数学会计算杂志)

年 卷 期：2001年第31卷第1期

页      面：67-85页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：parallel tree search parallel communication model randomized algorithm 

摘      要：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.