Browse Prior Art Database

Optimal Decentralized Consensus Protocols Without an Initiator

IP.com Disclosure Number: IPCOM000121506D
Original Publication Date: 1991-Sep-01
Included in the Prior Art Database: 2005-Apr-03
Document File: 2 page(s) / 77K

Publishing Venue

IBM

Related People

Chen, MS: AUTHOR [+3]

Abstract

Reaching a consensus among separate processing nodes efficiently is an important issue in reliable distributed computations. Decentralized consensus protocols are characterized by the number of steps required to reach a consensus by all nodes, and the total number of messages sent during the execution of the protocol. Note that unlike the centralized consensus protocols, where a centralized coordinator collects all the information from all participants and then sends the consensus to every participant, there is no centralized coordinator in the decentralized consensus protocols.

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

Optimal Decentralized Consensus Protocols Without an Initiator

      Reaching a consensus among separate processing nodes
efficiently is an important issue in reliable distributed
computations.  Decentralized consensus protocols are characterized by
the number of steps required to reach a consensus by all nodes, and
the total number of messages sent during the execution of the
protocol.  Note that unlike the centralized consensus protocols,
where a centralized coordinator collects all the information from all
participants and then sends the consensus to every participant, there
is no centralized coordinator in the decentralized consensus
protocols.  We develop in this disclosure the optimal decentralized
consensus protocols with the focus on how to reach a consensus with
not only the minimal number of steps but also the minimal number of
messages for a distributed system with one port communication.  This
scheme can be generalized for a system with k port communication [*].
To facilitate the presentation of our protocol, we shall propose an
addressing scheme for nodes in the distributed system.  It can be
seen that in light of the addressing scheme, the optimal consensus
protocol can be systematically executed and shown to incur the
minimal number of messages in the minimal number of steps.

      To describe the addressing scheme, it is necessary to introduce
the concept of a partitioning tree of a positive number p, which can
be constructed as follows. First, label the root node with p.  Then,
for each external node with a label k / 2, generate the left and
right
children of this node and label them with      and     ,
respectively.
This step repeats unti...