Browse Prior Art Database

Efficient Two Round Communication Structure of Decentralized Consensus Protocols

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

IBM

Related People

Nakajima, A: AUTHOR

Abstract

Disclosed is a scheme of constructing an efficient and symmetric two- round communication structure of decentralized consensus protocols.

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

Efficient Two Round Communication Structure of Decentralized Consensus Protocols

Disclosed is a scheme of constructing an efficient and
symmetric two- round communication structure of decentralized
consensus protocols.

Let points of a finite projective plane be p_1, p_2, ..., p_n.
Let lines of a finite projective plane be l_1, l_2, ..., l_n.  The
number of points, n, must be equal to m * m + m + 1
and m must be a power of a prime.  The scheme first creates a finite
projective plane with the following condition: if p_i is on l_j, then
p_j is on l_i.

Let {d_1, d_2, ..., d_m+1} be a (m * m + 1, m +
1, 1)- difference set.  Points, lines, and incidence between points
and lines defined by the following equation:
l_a = {p_b : (a - 1) + (b - 1) = d_c (mod (m
* m + 1))}               ( 0 < a, b < m * m + 2,
0 < c < m + 2), (1)
become a finite projective plane that satisfies the previous
condition.

Then, the scheme creates a two-round communication structure of
decentralized consensus protocols.  Let S_1(i) be a send set that
node i uses in the first round.  Let S_2(i) be a send set that node
i uses in the second round. The scheme constructs the communication
structure by using the finite projective plane created by equation 1
and the following equation:
S_1(i) = S_2(i) = {a : p_a is on l_i}
(0 < a, i < n + 1).  (2)

The communication...