Tree search on an atomic model for message passing

Pangfeng Liu, William Aiello, Sandeep Bhatt

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)67-85
Number of pages19
JournalSIAM Journal on Computing
Volume31
Issue number1
DOIs
StatePublished - 2001

Keywords

  • Parallel communication model
  • Parallel tree search
  • Randomized algorithm

Fingerprint

Dive into the research topics of 'Tree search on an atomic model for message passing'. Together they form a unique fingerprint.

Cite this