Browse Prior Art Database

Broadcasting Multiple Messages Optimally in Simultaneous Send/ Receive Systems

IP.com Disclosure Number: IPCOM000110531D
Original Publication Date: 1992-Dec-01
Included in the Prior Art Database: 2005-Mar-25
Document File: 4 page(s) / 185K

Publishing Venue

IBM

Related People

Bar-Noy, A: AUTHOR [+2]

Abstract

Disclosed is an algorithm for the problem of broadcasting m messages to n processors in a fully-connected, simultaneous send/receive system. Initially, one processor has m messages to broadcast to the other n-1 processors in the system. Communication between processors occurs in rounds. In each communication round, a processor can send a message to one processor and receive a message from another processor. A message sent in a given communication round is received in the same round. The goal is to broadcast the m messages among the n processors in the minimal number of communication rounds. A lower bound on the number of communication rounds required is (m-1) + log n.

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

Broadcasting Multiple Messages Optimally in Simultaneous Send/ Receive Systems

       Disclosed is an algorithm for the problem of broadcasting
m messages to n processors in a fully-connected, simultaneous
send/receive system.  Initially, one processor has m messages to
broadcast to the other n-1 processors in the system.  Communication
between processors occurs in rounds.  In each communication round, a
processor can send a message to one processor and receive a message
from another processor.  A message sent in a given communication
round is received in the same round.  The goal is to broadcast the m
messages among the n processors in the minimal number of
communication  rounds.  A lower bound on the number of communication
rounds required is (m-1) + log n.

      The problem of broadcasting m messages to n processors in
simultaneous send/receive systems was studied by several researchers.
A simple folklore algorithm provides an optimal solution for this
problem in the case of m=1 and for any value of n.  The running time
of this algorithm is log n rounds.  An optimal algorithm for the case
of n = 2k and for any value of m is presented in [1].  The
running time of the algorithm of [1] is (m-1) + log n rounds.  A
special case of one of the algorithms [2] provides a solution for
this problem for any values of m and n.  The running time of this
solution is m + 2 log n + O(1) rounds.  Finally, a recently developed
solution for this problem is contained in [3].  This algorithm works
for any values of m and n and its running time is m + log
n + O(log log n).

      This article provides an optimal algorithm (up to an additive
term of 2) for the problem of broadcasting m message to n processors
in a simultaneous send/receive system.  This algorithm works for any
values of m and n and requires at most m + log n + 1
rounds.

      The description of the optimal algorithm for broadcasting m
messages among n processors is in four steps.  First, Algorithm A for
broadcasting m=1 messages to n=2k processors is described.  Second,
Algorithm B for broadcasting m>1 messages to n=2k processors is
described.  Third, Algorithm C for broadcasting m>1 messages from one
external source to 2k internal processors is described.  Fourth,
Algorithm D for broadcasting m > 1 message to n processors, for any
values of m and n, is described.
Algorithm A

      This algorithm broadcasts m=1 messages to n=2k processors in k
= log n rounds.  The algorithm consists of doubling the number of
processors that know the message in every round.  Denote the n=2k
processors using the 2k binary addresses (ek,...,e1), where ej {0,1}
for 1<j<k.  Let the broadcast originator be processor s = (sk,...s1)
and let M be the broadcast message. In round 1, processor s sends M
to processor (sk,...,s2,1-s1).  In general, in round i, for 1<i<k,
each processor p that knows the message M sends it to the processor
whose address is obtained by complementing...