Computer Science Department
TECHNICAL REPORT
Byzantine Agreement by Distributed Randomization in O(log n) Rounds.
John H. Reif* and Paul G. Spirakis**
October 1984 Technical Report #143
REVISED
NEW YORK UNIVERSITY
Department of Computer Science Courant Institute of Mathematical Sciences 251 MERCER STREET, NEW YORK, N.Y. 10012
v
Byzantine Agreement by Distributed Randomization in O(log n) Rounds.
John H. Reif* and Paul G. Spirakis*'
October 1984 Technical Report #143
REVISED
*
Lab.
for Computer Science, MIT;
and
Aiken
Comp.
Lab.,
Harvard
University. **
Courant Institute Math.
Sci., New York Univ.
c
;/?s.sv8
Byzantine Agreement by Local Randomization in O(log n) Rounds.
John H. Reif
and Paul G. Spirakis
October 1984
Abstract We consider here
the
synchronous processors.
provide t.
a
t
= o(n).
random
global
c
Lab.
t
<
Byzantine
) ) )
>
1
O(log n)
messages and signatures.
bit
instead
and
it
only
Computer
Science,
Courant Institute Math.
among
MIT;
and
n
We
uses
Note that this bound is
makes
external
use of local random
probability
at
most
n~ c
arbitrarily large.
and Aiken Corap.
University. itis
rounds
Our algorithm does not require the use of an
is a constant which can be set
for
Agreement
n/10 processors may be faulty.
Our algorithm makes an error with
choices.
where
At most
of
randomized algorithm which takes
n l+0(.log(n/(nt
nt if
problem
Sci., New York Univ.
Lab., Harvard
2
Introduction
1.
The Byzantine Agreement (BA) problem is essentially the problem of finding a protocol for reaching agreement among n distributed processes of which at most
Lamport
[PSL,
t
80]
and
synchronization among showed
essential for maintaining coordination and
is
processes
distributed
in
systems.
[FLP,
the processes are asynchronous.
[DS,
81]
showed that
rounds
t+1
necessary for synchronous processes and deterministic potocols. [BO,
83]
gave a randomized solution
However,
algorithm
his
rounds for
t
needs
aji
to.
asynchronous
the
Rabin round
[R,
introduced the assumption of
83],
(which
all
processes
can
BenOr problem.
constant
rounds and a polynomial number of messages in the case
of
BA
are
exponential number of messages and
j
n'*'^'*6 for any e ^.Q^ but requires a
=
82]
BA problem has no deterministic solution in the case
the
that
BA was defined by Pease, Shostak and
may be faulty.
read)
a
single
t
number
= o(n
1/9 w ).
bit
per
random
to solve the asynchronous BA
problem, with no error, in an expected constant number of rounds and by
using
0(n
)
messages.
further
He
could be reduced to 0(nt) messages. his
algorithm to take only
l2 R and by using
"predealt"
the
a
same
observed that this message bound Rabin also showed
how
to
modify
fixed number R of rounds with reliability
number
of
messages.
Apparently,
the
nature of the random sequence of bits required for Rabin's
algorithm is crucial. Rabin posed as an open problem finding a protocol to distributedly decide on a global random bit.
Broder and Dolev in [BD, 84] have shown
that a protocol for finding a global random bit in the synchronous case
requires a
t+1 rounds in the worst case (which can be achieved anyway by
deterministic
solution).
[B,84]
has
shown
how
to
construct
a
3
random bit by distributed randomization, in O(log n) expected
"global"
However, his construction is nonuniform in the sense
number of rounds.
that each processor must follow a protocol possibly distinct from other
processors' protocols, which has to be precomputed
and
apparently
is
not easily computable on line.
contribution
Our
the discovery of a randomized algorithm for
is
synchronous Byzantine Agreement. only
and
random
local
tn 1+0 l
**
choice,
Note
does not assume a global or
it
,
where
c
>"
1
r
can
sfnd
that this message and signature' bound is nt if
P.
processors
be
(the
some reliable means of communication.
sends a message M.
message, and its value, v is
Protocol proper .
We assume that
"generals").
with
supplied ).
e
the
As long as a P.
Once
a
processor
{
0, 1}
same
to each P.
(the
P
,
through
sender
M^ is called the initial
.
Each
Let v be the complement of v.
.
program,
deviates
considered to remain faulty even if,
later
or
fl
AP
computes according P.
P.
In the beginning of the system's
execution, another process Pq distinct from Pj
?!
extended
easily
can directly exchange messages with every other
"commander")
= o(n).
Definitions and assumptions
2.
P,,...,P
t
by known techniqiie^'."
to the multivalued case,
every
arbitrarily
set
be
We assume a twovalued initial message, Dutfl£3ftT can be
Let
by
and signainrres and by making an error
messages
nF
with probability at most n c large.
but
authentication
of
Our algorithm achieves" BA in O(log n) rounds,
external random bit. using
It only makes use
(called AP,
to
the Agreement it
is
called
from AP it is faulty and is on,
it
reverts
back
to
4
following AP.
We assume that the set
processors
of
eventually
that
become faulty is independent of the random choices of our algorithm.
Byzantine Agreement is achieved when (1)
All proper processors agree on the same value, and
(2)
if
sender
the
Pq
sends
the
same value to everybody (operates
correctly) then all proper processors agree on its value. Our analysis of the problem is based on the worst case
faulty
that
processors
are not predictable and may be malicious.
algorithm should sustain any strange even
a
collusion
to
assumption
prevent
the
behavior
faulty
of
processors
proper
An
processors, from reaching
agreement. . ri
zi
c
In our algorithm we employ authentication of messages
signatures.
A
faulty
processor
can
invent
information and furthermore faulty
processors
production
However,
false
of
messages.
signature scheme that enables each one to
any
sign
unauthenticated
cooperate
can all
digital
by
processors its
the
in
share
message
so
a
that
every receiver will recognize who sent the message and no one can alter the content of the message or
the
scheme
78]).
was suggested by [RSA,
signature
undetectably.
(Such
We assume that every message that
contains only signatures of faulty processors can be produced by processors. (signed) by
We P.
.
shall
denote
by
Finally, we assume
a
a.(M) that
these
the message M authenticated
each
processor
Pj
has
a
random number generator, and can choose random numbers independently of other processors. or
affect
the
We assume that the faulty processors cannot result
of
these
predict
choices of random numbers by proper
processors. Note that our assumptions about authenticated messages mean (as in
5[D,82]) that no processor can alter an authenticated at
a
next
received
message
previous round and forward it as an authenticated message at the nor
round,
authenticated
message
t
receive
not
and
received
have
to
forward
In the rest of the paper, we assume
an
that as an
that
t
<_
is the maximum number of faulty processors.
Let
Definition.
did
it
authenticated message. n/10, where
pretend
processor
any
can
a
path
length m be a sequence of m distinct
of
II
,
processor names. i
Definition .
Let n =
P.
p.
sends
a message M t£_ P.
message to
.
,
,r
by using
!l,

wemean that: P^ sends
relays the message (after signing it) to P.i
,
etc.
If
2
P,
i
,
of the form
(where
n
= p
P J
Definition .
p. 1
x l
2
(a
m
±
m— 1
(... a ± (OiCM.H 1
.
J
J
Let P. send a message M to P^ by using
origin (M) = Def inition
P,) ...)
...p.i p.).
m
A signed message
a.
(a,
S
P^^
,
destination (M)
of the form
(...o:
II
(a^M^
P,)...)
.
Then = P
a
signed
Then,
name.
the processors in the path are proper, then P. will receive
i
?^
m
consisting of M appended to the path
P.
"Processor
By saying
be a path.
..p.
2
1
P^
and each of a
message
\ 6
where
II
= P.
...p.
called
and
partial
a
arriving
k < m,
—<
m
1
processor
to
P^
,
is
k+1
signed
message arriving at
M is called the
P,
i
k+1
value of S. A processor P. detects a
Definition . signed
arrive
messages
contradiction
two
if
,
partial
(let them be S, S'), with the following
at P.
properties: (1)
origin(S) = P k
,
origin(S') =
P
k

k'
(k,
necessarily
not
are
distinct) (2)
destination(S) =
(3)
value(S) = Oq(0), value(S') = o Q (l)
Note that,
P
,
t
can be one of
i
destination(S'
)
= P

,
t
t~ f t.
or t~ or one of k,k'.
t
lorter'?"
contaminated
A
Definition .
faulty processor.
g
Fix a constant a
arbitrarily
to
>
2.
1.
c
decrease
2.
R.
.
(Interrogation
as follows:
P.
a path
II
,
P
Fix m =
> 4.
log n.
a
—
For each
phase).
.
.
.
the error probability of our algorithm.)
i
j
in
to j,
{
1 ,
2,
.
. .
,n)

{
i}
,
P
i
randomly
each of length m = a log n.
Pj "interrogates" each P^
sends an interrogation (empty)
if P.
containing at least one

of g paths from
each of the paths in R. Then,
c
log n«n a lo S (
(Random choice phase).
chooses a set
a path
(Note that a can be set arbitrarily large so
Furthermore, fix a constant Fix g =
_
is
The Algorithm AP for processor P i
3.
as
path,
,
(j
message
/ i)
to
V.
about M
,
through
(This takes m rounds).
has received an interrogation message from P k through
sends back its H i
,
by using the path
IT
in
reverse .
?
i
)
7
message
does this answering for each distinct interrogation
path
distinct
arrival.
of
answering
(This
process
each
and
also m
takes
rounds.
Note that it may happen that some answers will not
processor,
interrogating
due
an
at
processors not relaying the
faulty
to
arrive
answer in the return path. 3.
(Validation phase).
{S,S',
origin(S)
If
P^
=
destination(S')
= P
P^
partial
sends
the
(selected in Phase

1)
,
origin(S')
,
=
P
[II
3 S:
k

,
destination(S) = P t
and value(S) = Og(0), value(S') =
message
to P
form
has detected a contradiction of the
P.
along
S'
then
Oq(1)}
each of the g paths in R^ t
and furthermore
,
,
in
this
case
also
P^
fc
sends
the
message
partial
P^ does this only once for
That is, if
contradiction.
involving P
only one is
,
S
along each' of. the paths in
R^,.
to P t
~
.
each processor P t being the destination of
a
P.
has detected more than one contradiction
validation
The
used.
phase
takes
m
=
a log n rounds.
4.
(Decision
phase).
value arriving at
it
P.
in
decides Phases
v if and only if v is the only
on and
2
3.
Else,
a
default
value
corresponding to "sender faulty" is produced. De f inition .
Let R be the union of R.
.
for all P. and all proper P.
8
Analysis of the Algorithm
4.
Lemma
Let E^ be the event that for all
1 .
one proper processor.
For each path
Proof:
Then Prob{E,}
II
>
II
 n~^
1
in R,
contains at least
II
for y
>
constant.
a
2
,
prob(n contains no proper processor}
(£^a log n < n a log(t/n) _ n
<•
—
"a < n
log 10
since
_t —< n
— 1
log(t/n)
implies
10
—<
 log 10
Then Prob{not Ej}
< n
< n
2
g n
2
c
_a lo
10
J5
logn n" a lo §
9
(because 2 <±2).
I.e.
Prob{not E,} < n"Y
,
where Y is defined to be equal to
—
—— —
l°g c  log log n . . o v o n  *> n 2 2 2 2 a ilog9 > a log9  3 > 2 — n n log log
Definition
.
A path
II
is
called
proper
if
all
its
.
processors
are
proper.
Lemma
2
.
Let
E2
the
be
least one element of R.
.
event "For each proper Pj and each P
is proper".
then
,
at
)
9
Prob{E 2 }
>
 n" (c_2)
1
.
Proof: The probability that a particular random path in R.
.
is
proper
is
[l  ll a lo g n = n a logOt/n)^ n
Let q be the probability that all paths of R^. are not proper.
q
= (l
 (1  I) a lo § n )g n
=
r [
 n
<_
e"§ n
<
nc
,
1
"a lo § ( zzr ) xxg nt
5'goi
i
)
a log(
—
)
•
^
D(
(since (1  l/x) x
<
e"
So q
Then
,
by definition of
log(
a
g = c log n
n
•
— nt
) t
Hence 2
Prob{not E 2 )
<
Prob{E 2 }
 n (c 2)
n q
<_
n~ (c_2)
So >
1
.
c
> 4
1
for all x > 0),
10Lemma
3
and E2. Phase
Let
.
us condition the algorithm's execution on the events E,
Then the algorithm achieves Byzantine Agreement at the end
of
3.
Proof
:
Case
1 .
The
commander P
(since M is the same).
hence
commander, phases
2
and
Q
Then Vi
is proper.
There is only one
M i = a Q (M) is the same
,
value
signed
sent
only one such value arrives at each proper
the
by P.
during
(The faulty processors cannot alter Oq(M), or devise
3.
a
false value for it, due to authentication.) Case
2
Pq
.
is faulty.
proper processor
P.
Assume (for the sake of contradiction) that a
commits to value v (by
another proper P. commits to different value v' Then, there is a path to
P..
By
II
Ej there is a proper processor P g on
will detect
a
the
message
(answering)
destination P.
.
each
g paths.
of
its
So,
P
2
sent
will notify By Ey
,
II
which returns
,
,
and (by E2) P s is
in Pj^
phase
2
and
between the
2
destination
with
origin
n
and
P,
correctly.
Hence, it is impossible
to commit to v. Note that the above argument works even if
P.^
P^
through
0q(v)
about the value
i
=
•
k.
Lemma
value.
for the sender's
with origin P
v
at least one of these paths will relay
the contradiction information to P. for
P.
"system faulty"}.
{v,
contradiction at the end of phase
(answering) message sent in phase and
e
and
phase 3)
of
from P. to some processor P^
indeed among the processors interrogated by Hence, P
end
the
4
.
Our algorithm achieves BA, within 0(a log n) rounds, by using
2K)(log(— )) nt
x
messages, and with probability of error
<_
n
,
6
>
1.
11
Our algorithm makes an error if E,
Proof:
Prob(error)
n^
n"6 +
<.
or E2 do not hold.
n^5
_<
Thus
,
where = min(3 ,y
6
algorithms
Our
rounds. of
So,
has
three

)
phases
1
.
phase takes m = a log n
each
and
The
the total number of rounds is 3m = 3a log n.
signatures
per
message
0(a
is
total number of
the
so
liagisrDr,
number
signatures sent is
.,
n 2 g» (# rounds)
_<
(V
c

(# signatures /message)
n 2 g O(a 2 log 2 n) j
C
•
.
• .
a log(
cn^log n n
— — nU
)
9
•
9
O(a^log^n)
2+0(log(Jl_)) nt
= n
.
•
This is the same as the total number of messages.
l+0(log(— )) Lemma
5
.
messages
We can modify and
our
signatures,
algorithm O(log n)
to
rounds
use
only
with
nt
tn
the
same
success
probability. Proof
:
We modify our algorithm as follows: We
processors to be "relay" processors. to.
arbitrarily
So,
t+1
We require any nonrelay processor
send messages only to relay processors (the commander
relay). Pi
choose
cannot
be
if processor Pi wants to send a message to processor P.
sends the (signed) message to the t+1 relay processors.
a
,
They, then,
12send it to P..
Clearly, at least one relay processor is proper and the
faulty ones cannot alter messages, due to authentication.
(This is the
same technique, as used in [DS, 82a]).
Acknowledgment
We wish to thank R. Cole for useful
:
comments
on
this
paper.
References
[BO, 83]
M. BenOr,
"Another
Advantage
Asynchronous Agreement Protocols", in Proc. [B,84] Bracha, to appear,
1984.
[BD,84] A. Broder and D. Dolev,
Choice: Completely
Free
of
PODC 1983.
>
;
"Flipping
Coins
in
Many
Pockets",
F0CS.84, Proc. [DLM.82]
N.A. Lynch,
DeMillo,
R.A.
Protocols," Proc.
and
M. Merritt,
14th ACM SIGACT Symp.
"Cryptographic
on Theory of computing,
May 1982. [Da, 82]
"The
Dolev,
D.
Generals
Byzantine
Strike
Again",
Jour.
Algorithms 3(1). [Db,81]
D.
Dolev,
Environment",
"Unanimity 22nd
an
in
Annual Symp.
Unknown
and
Unreliable
on Foundations of Comp.
Sci.,
159168.
[DFFLS.82] D. Dolev, M. Fischer, R. Fowler, N. Lynch,
"Efficient
Byzantine
Agreement
Information and Control 52(3), [DS,82a] D. Dolev and H.R.
process
R.
Strong,
Authentication",
1982.
Strong, "Polynomial algorithms for multiple
agreement", Proc.
Computing, May 1982.
without
and
14
ACM SIGACT Symp.
on the Theory of
13[DS,82b]
D.
Dolev
H.R.
and
"Distributed
Symp.
2nd
Proc.
Waiting",
for
Report RJ3416.
Byzantine Agreement", IBM Res. [DS,82c] D. Dolev and H.R. Strong,
Algorithms
"Authenticated
Strong,
on
Reliability
Bounded
with
Commit in
Distributed
Software and Database Sys., Pittsburgh, July 1982.
Proc.
System",
Distributed
Agreement
Strong, "Requirements for
[DS,82d] D. Dolev and H.R.
Databases, Berlin, Sept.
2nd
Symp.
Intl.
in
on Distributed
1982.
[Feller, 59] W. Feller, "An Introduction to Probability Theory and
Applications", Wiley, R. Fischer,
[FLP.82]
N.
Lynch
Proceedings
of
Its
rIooojo
1959.
and
M.
Paterson,
Distributed Consensus with One Faulty also
a
2 nd
ACM
;
"Impossibility
Process",
SIGACTSIGMOD
of
MIT/LCS/TR282, Conference
on
Principles of Database Systems. [FFL.82] M. Fischer, R. Fowler, and N. Lynch,
Byzantine
Generals
Algorithm", Proc.
in Distributed Software and
Database
"A Simple and
2nd Symp.
Systems,
Efficient
on Reliability
Pittburgh,
July
1982.
[FL,82] M. Fischer, and L. Lamport, Tech. [La, 83]
L.
30(3),
Lamport,
"The
Weak.
Byzantine
Report, April 1982.
Generals
Problem", JACM,
1983.
[LSP.82] L. Lamport, R. Shostak, and M. Pease, "The Byzantine Generals
Problem", ACM Trans.
on Programming Lang.
and Sys., 4 (1982).
[LF,82] M. Fischer and N. Lynch, "A Lower Bound for the Time to Assure
Interactive Consistency", Information Processing Letters, 1982.
14(4),
14[PSL.80]
M.
Pease, R. Shostak, and L. Lamport, "Reaching Agreement in
the Presence of Faults", JACM 27(2) 228234. [R,83] M. Rabin,
[RSA.78]
"Randomized Byzantine Generals", Proc.
R.L. Rivest,
Obtaining
Digital
Comm. ACM 21,
Shamir,
A.
Signatures
and and
L.
Adleman,
PublicKey
120126.
This book
may
A
be
be kept
FOURTEEN DAYS fine will
FOCS 1983.
"A
Method
for
Cryptosystems",
NYU COMPSCI TR143^7 Reif, John H
/
Byzantine agreement by distributed
NYU COMPSCI TR143^ Reif, John H
/
Byzantine agreement by distributed BORROWLKs
DATE DUE
NftMc
LIBRARY N.Y.U. Courant Institute of
Mathematical Sciences 251 Mercer
New
York, N. Y.
St.
10012