Browse Prior Art Database

Efficient Randomized Distributed Agreement Mechanism

IP.com Disclosure Number: IPCOM000104131D
Original Publication Date: 1993-Mar-01
Included in the Prior Art Database: 2005-Mar-18
Document File: 2 page(s) / 56K

Publishing Venue

IBM

Related People

Garay, JA: AUTHOR

Abstract

V := "initial value"; for k := 1 R do \*Exchange 1: polling and early decision*\ send(V); collect n-t values; C := the multiplicity of the most popular value (say v); if C ge n-2t then V := v else V := perpend; \*Universal Exchange 2: readiness*\ send(`ready'); collect n-t 'ready' messages; \*Exchange 3: lottery and late decision*\ send(s sub ); collect n-t pieces of this round's secret; RSS; if V = perpend then V := s sub k od; "final value" := V;

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

Efficient Randomized Distributed Agreement Mechanism

      V := "initial value";
for k := 1 R do
\*Exchange 1: polling and early decision*\
send(V);
collect n-t values;
C := the multiplicity of the most popular value (say v);
if C ge n-2t then V := v
else V := perpend;
\*Universal Exchange 2: readiness*\
send(`ready');
collect n-t 'ready' messages;
\*Exchange 3: lottery and late decision*\
send(s sub <k,i>);
collect n-t pieces of this round's secret;
RSS;
if V = perpend then  V := s sub k
od;
"final value" := V;

     Randomized distributed agreement protocol;
     code for processor 0 le i lt n.

      This disclosure focuses on realistic and efficient solutions to
the  distributed agreement problem.  The first requirement forces one
to give up the synchronicity assumption.   The second,  to  look  for
solutions  with  low  computation and communication complexity costs,
while requiring (expected) constant time to termination.   Otherwise,
the performance of any protocol with even low polynomial message size
(e.g.,  O(n  sup  3  )) will be seriously retarded as the size of the
system grows moderately.  Presented is a randomized protocol  for  an
asynchronous  network  that terminates in an expected constant number
of rounds and uses messages of size Theta ( 'log' n ),  provided  the
total  number  of  processors  n  gt  5t.   This method represents an
improvement in terms of the total number of required  processors  (to
tolerate  the same number of faults t) to existing protocols that use
the notion of a "trusted dealer" and pre-distributed pieces of a coin
toss.  The main v...