Tree search on an atomic model for message passing

Citation
Pf. Liu et al., Tree search on an atomic model for message passing, SIAM J COMP, 31(1), 2001, pp. 67-85
Citations number
24
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Computer Science & Engineering
Journal title
SIAM JOURNAL ON COMPUTING
ISSN journal
0097-5397 → ACNP
Volume
31
Issue
1
Year of publication
2001
Pages
67 - 85
Database
ISI
SICI code
0097-5397(20010729)31:1<67:TSOAAM>2.0.ZU;2-C
Abstract
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.