Browse Prior Art Database

Optimal All to All Broadcasting Schemes in a System with Multi-port Communication

IP.com Disclosure Number: IPCOM000107713D
Original Publication Date: 1992-Mar-01
Included in the Prior Art Database: 2005-Mar-22
Document File: 2 page(s) / 106K

Publishing Venue

IBM

Related People

Chen, MS: AUTHOR [+3]

Abstract

Broadcasting, which refers to a process of information dissemination in a distributed system whereby a message originating from a certain node is sent to all other nodes in the system, is a very important issue in distributed computing. All-to-all broadcasting means the process by which every node broadcasts its certain piece of information to all other nodes. Similar to one-to-all broadcasting, all- to-all broadcasting schemes are characterized by the number of communication steps required and the total number of messages incurred to complete the broadcasting. In this disclosure, we develop optimal all-to-all broadcasting schemes for a distributed system of an arbitrary number of nodes with k-port communication, where k is a given positive integer depending on the system.

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

Optimal All to All Broadcasting Schemes in a System with Multi-port Communication

       Broadcasting, which refers to a process of information
dissemination in a distributed system whereby a message originating
from a certain node is sent to all other nodes in the system, is a
very important issue in distributed computing.  All-to-all
broadcasting means the process by which every node broadcasts its
certain piece of information to all other nodes.  Similar to
one-to-all broadcasting, all- to-all broadcasting schemes are
characterized by the number of communication steps required and the
total number of messages incurred to complete the broadcasting.  In
this disclosure, we develop optimal all-to-all broadcasting schemes
for a distributed system of an arbitrary  number  of nodes  with
k-port communication, where k is a given positive integer depending
on the system.  K-port communication means that each node can send
out k messages simultaneously in one communication step.   The system
considered is completely connected with synchronous communication,
and every message sent in the system takes one communication step.
Also, to reduce the communication overhead, the schemes discussed are
those without duplicate information, i.e., NODUP (no duplication)
schemes where each message only conveys new information to its
receiver.

      We propose the optimal all-to-all broadcasting scheme for a
distributed system with k-port communication to complete the
broadcasting with not only the minimal number of communication steps
but also the minimal number of messages.  A partitioning tree of a
positive number p is a tree where the root node is labeled with p,
all leaf nodes are labeled with ones, and the number labeled in each
non-leaf node (or internal node) is the sum of those labeled in its
child nodes.  The number of child nodes of an internal node z is
called the degree of z.  As will be described in the next section
(implementation), the operation of the optimal NODUP all-to-all
broadcasting scheme in a system of p nodes with k-port communication
can be described by the optimal partitioning tree of p where the
degree of each node is less than or equal to k+1.  The procedure to
construct such an optimal partitioning tree is described in the next
section.  Our results show that for a system of p nodes with k-port
communication, the minimal number of messages required for all-to-all
broadcasting in n=  logk + 1p  steps is,

                            (Image Omitted)

...