TY - GEN
T1 - An atomic model for message-passing
AU - Liu, Pangfeng
AU - Aiello, William
AU - Bhatt, Sandeep
N1 - Publisher Copyright:
© 1993 ACM.
PY - 1993/8/1
Y1 - 1993/8/1
N2 - This paper presents a simple atomic model of message-passing network systems. 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 exisiting message-passing systems. Nonetheless, we 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 network systems. 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 exisiting message-passing systems. Nonetheless, we prove linear speedup for backtrack and branch-and-bound searches using simple randomized algorithms.
UR - http://www.scopus.com/inward/record.url?scp=85014503350&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85014503350&partnerID=8YFLogxK
U2 - 10.1145/165231.165251
DO - 10.1145/165231.165251
M3 - Conference contribution
AN - SCOPUS:85014503350
T3 - Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1993
SP - 154
EP - 163
BT - Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1993
T2 - 5th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1993
Y2 - 30 June 1993 through 2 July 1993
ER -