Byzantine agreement by distributed randomization in 0(log n) rounds

...

0 downloads 129 Views 465KB Size

Recommend Documents


No documents
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. it-is

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/(n-t

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

Ben-Or 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

l-2 -R and by using

"pre-dealt"

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 two-valued initial message, Dutfl£3ftT can be

Let

by

and signainrres and by making an error

messages

n-F

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-,

-

we-mean 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

-lor-ter'?"

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 logO-t/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

<

n-c

,

1

"a lo § ( zzr ) xxg n-t

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



— n-t

-) 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

2-K)(log(— )) n-t

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

— — n-U

)

9



9

O(a^log^n)

2+0(log(Jl_)) n-t

= 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

n-t

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. Ben-Or,

"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.,

159-168.

[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",

SIGACT-SIGMOD

of

MIT/LCS/TR-282, 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) 228-234. [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,

Public-Key

120-126.

This book

may

A

be

be kept

FOURTEEN DAYS fine will

FOCS 1983.

"A

Method

for

Cryptosystems",

NYU COMPSCI TR-143^7 Reif, John H

/

Byzantine agreement by distributed

NYU COMPSCI TR-143^ 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

Sign up to our newsletter for the latest news

© Copyright 2013 - 2020 ALLDOKUMENT.COM All rights reserved.