Browse Prior Art Database

Designing Broadcasting Algorithms in the Postal Model for Message Passing Systems

IP.com Disclosure Number: IPCOM000109172D
Original Publication Date: 1992-Aug-01
Included in the Prior Art Database: 2005-Mar-23
Document File: 5 page(s) / 243K

Publishing Venue

IBM

Related People

Bar-Noy, A: AUTHOR [+2]

Abstract

Disclosed are algorithms for broadcasting in message-passing systems with communication latencies. Optimal-time Algorithm BCAST for broadcasting one message is disclosed first. Three generalizations of BCAST for broadcasting multiple messages: Algorithms REPEAT, PACK, and PIPELINE, are disclosed second. A class of algorithms for broadcasting multiple messages, collectively called Algorithm DTREE, is disclosed third.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 29% of the total text.

Designing Broadcasting Algorithms in the Postal Model for Message Passing Systems

       Disclosed are algorithms for broadcasting in
message-passing systems with communication latencies.  Optimal-time
Algorithm BCAST for broadcasting one message is disclosed first.
Three generalizations of BCAST for broadcasting multiple messages:
Algorithms REPEAT, PACK, and PIPELINE, are disclosed second.  A class
of algorithms for broadcasting multiple messages, collectively called
Algorithm DTREE, is disclosed third.

      In message-passing systems processors submit messages to and
receive messages from an underlying communication network, which
delivers messages from their sources to their destinations.  Several
distributed-memory parallel computers, including MIT J-machine (1),
and several high-speed communication networks, such as PARIS (2) and
plaNET (3), ignore the exact structure of the communication network
and assume that the network creates a complete point to point
communication graph.  In these systems, sending a message is a send
and forget event, and the propagation of a message between any pair
of processors takes roughly the same time.

      This article proposes the postal model for message-passing
systems with communication latencies.  The postal model employs a
latency factor g > 1 that measures the inverse of the ratio between
the time it takes an originator of a message to send it and the time
that passes until the recipient of the message receives it.  More
specifically, the model assumes that an originator of a message
spends 1 unit of time sending the message to its destination and then
it is free to perform other functions including sending other
messages.  When the message arrives at its destination, the recipient
spends 1 unit of time receiving it.  The communication latency, g is
the total time that passes from the time an originator starts
preparing a message until the time the recipient finishes handling
it.  The notation MPS(n,g) is used  for message-passing systems with
n processors and communication latency g.

      This article explores the effects of communication latencies in
message-passing systems on the design of broadcasting algorithms.
The broadcasting problem of m > 1 messages in  MPS(n,g) is defined as
follows.  At time t=0, processor p0 has m messages M1, M2, ..., Mm to
broadcast to the other n-1 processors.  The goal is to design
algorithms that minimize the arrival time of last message to last
processor.  Other variants of broadcasting were investigated for both
parallel computers and for distributed-processing environments (see
(4,5)).
Broadcasting one Message: Algorithm BCAST

      Described is optimal-time Algorithm BCAST for broadcasting one
message in MPS(n,g).  A similar approach for the sensitive census
problem is presented in [6].  First defined is the generalized
Fibonacci function Fg(t) and its index function fg(n).
The function Fg(t) is defined from the non...