An atomic model for message-passing

Pangfeng Liu, William Aiello, Sandeep Bhatt

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

32 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publicationProceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1993
Pages154-163
Number of pages10
ISBN (Electronic)0897915992, 9780897915991
DOIs
StatePublished - 1 Aug 1993
Event5th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1993 - Velen, Germany
Duration: 30 Jun 19932 Jul 1993

Publication series

NameProceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1993

Conference

Conference5th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1993
Country/TerritoryGermany
CityVelen
Period30/06/932/07/93

Fingerprint

Dive into the research topics of 'An atomic model for message-passing'. Together they form a unique fingerprint.

Cite this