Browse Prior Art Database

Optimal Initiator-Based Decentralized Consensus Protocols with Multi-Port Communication

IP.com Disclosure Number: IPCOM000111121D
Original Publication Date: 1994-Feb-01
Included in the Prior Art Database: 2005-Mar-26
Document File: 4 page(s) / 134K

Publishing Venue

IBM

Related People

Chen, MS: AUTHOR [+2]

Abstract

Because of the availability of inexpensive, high-performance microprocessors, it has become very attractive to link together many powerful and autonomous computers to build a distributed computing system for better availability and cost performance. In a distributed computing computing system, instead of using a shared memory and a global clock, all synchronization and communication between the processing nodes can be done via message passing. As a result, the design of of consensus protocols becomes a very important issue in distributed computing. The consensus protocol refers to a process for all nodes in a distributed system to collect the information/status from every other node and reach a consensus among them.

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

Optimal Initiator-Based Decentralized Consensus Protocols with Multi-Port
Communication

      Because of the availability of inexpensive, high-performance
microprocessors, it has become very attractive to link together many
powerful and autonomous computers to build a distributed computing
system for better availability and cost performance.  In a
distributed computing computing system, instead of using a shared
memory and a global clock, all synchronization and communication
between the processing nodes can be done via message passing.  As a
result, the design of of consensus protocols becomes a very important
issue in distributed computing.  The consensus protocol refers to a
process for all nodes in a distributed system to collect the
information/status from every other node and reach a consensus among
them.  There are typically two types of decentralized consensus
protocols: the one without an initiator, and the one with an
initiator.  In the former (without an initiator), synchronization is
assumed to be achieved a priori, and all processing nodes
concurrently participate in the consensus protocol when the protocol
is started.  In the latter (with an initiator), it is assumed that
each node, except the initiator, will not participate in the
consensus protocol until it is informed to do so by receiving a
message from some other node.  Performance of the consensus protocols
is usually assessed by the number of message steps required to reach
a consensus by all nodes in a distributed system, and also the total
number of messages incurred during the execution of the protocol.

      This method discloses an initiator-based decentralized
consensus protocols with multi-port communication.  The system
considered is completely connected with synchronous communication.
There can be an arbitrary number of nodes in the system, and all
nodes are assumed to have the same number of communication ports.
Every message sent takes one communication step.  There is no
restriction on the number of messages each node can receive in one
step.  This protocol contains three phases:  (1) broadcasting phase,
(2) shuffling phase, and (3) confirming phase.  The purpose of the
broadcasting phase, which is started by the initiator, is mainly to
let every node receive some messages, so that every node is informed
to participate in the protocol.  Then, the shuffling phase, which
follows the broadcasting phase, is to reach consensus in a subset of
nodes.  After consensus is reached by those nodes, the entire
information is broadcast to all other nodes in the system in the
confirming phase.  It is worth mentioning that due to the multicast
capability of each node, how to decide the number of communication
ports to be employed in each phase is an important issue and critical
to performance.  To facilitate our presentation, we define a
generalized n-dimensional m-ary hypercube, denoted by H sub n sup m,
as follows.  Definition: An n-dimension m-ar...