Browse Prior Art Database

Optimal Decentralized Consensus Protocols with an Initiator

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

Publishing Venue

IBM

Related People

Chen, MS: AUTHOR [+3]

Abstract

We develop in this disclosure the optimal decentralized consensus protocol with an initiator. Under the proposed protocol, the consensus can be reached by all nodes in the minimal number of steps while incurring the minimal number of messages. Note that, unlike the protocol without an initiator [1], in the case of having an initiator, each node, except the initiator, will not start sending any message until it receives a message from some other node. The proposed decentralized consensus protocol consists of three phases: broadcasting phase, shuffling phase, and confirming phase. The purpose of the broadcasting phase, started by the initiator, is mainly to inform each node to participate in the consensus protocol by letting every node receive some messages.

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

Optimal Decentralized Consensus Protocols with an Initiator

      We develop in this disclosure the optimal decentralized
consensus protocol with an initiator.  Under the proposed protocol,
the consensus can be reached by all nodes in the minimal number of
steps while incurring the minimal number of messages.  Note that,
unlike the protocol without an initiator [1], in the case of having
an initiator, each node, except the initiator, will not start sending
any message until it receives a message from some other node. The
proposed decentralized consensus protocol consists of three phases:
broadcasting phase, shuffling phase, and confirming phase.  The
purpose of the broadcasting phase, started by the initiator, is
mainly to inform each node to participate in the consensus protocol
by letting every node receive some messages.  Through sending
messages, the information will be cumulatively collected during the
broadcasting phase, and a minimal covering set that has the entire
information is formed at the end of this phase.  The minimal covering
set formed at the end of the broadcasting phase is termed the
shuffling set.  The purpose of the shuffling phase is in fact to
reach consensus for the nodes in the shuffling set.  After the
consensus is reached by the nodes in the shuffling set, the entire
information is sent to all other nodes in the system in the
confirming phase.

      To facilitate the presentation, let Bn(m) denote the binary
representation of an integer m with n bits, and #(bnbn-1...b1) be the
       n
integer Sbk2k-1 .  We then address the p nodes in the system by
Bn(k),
      k=1
for 0&k&p - 1, where n =  log2p  .  Note that in a system of
p nodes, a node cncn-1 ... c1 can obtain its relative address to some
node dndn-1 ...d1 by Bn((#(cncn-1 ...c1)-#(dndn-1 ...d1))mod p).
Using the concept of the relative address, a receiver of a message
can determine its relative address to the initiator and perform
accordingly to complete the consensus protocol.  Thus, without loss
of generality, we assume the address of the initiator is Bn(0)=00...0
in the following for simplicity.  Note that in the algorithm below,
it takes n =  log2p steps to complete the broadcasting phase for a
system of p nodes, and the shuffling set, according to the above
addressing method, is the set of nodes with the address bnbn-1 ...b1
where #(bnbn-1 ...b1)/2n-1 .
Thus, conceptually, the p nodes in the system can be divided into two
parts: those forming a Qn-1 and those in the shuffling set.  In
essence, the broadcasting and the confirming phases are completed by
the nodes in the Qn-1, whereas the shuffling phase is carried out by
the nodes in the shuffling set.  To facilitate the presentation, the
primitive send(k, M, bnbn-1 ...b1, tag) is used to mean the sender
sends the messageM to the node nnbn-1 ...b1 in step k, and the value
of the tag is used to denote the phase of the message in the
consensus protocol so that tag = "B", "S...