The-Byzantine-Generals-Problem.pdf

需积分: 0 131 浏览量更新于2023-05-22 收藏 1.18MB PDF 举报

拜占庭将军问题论文-英文版 Reliable computer systems must handle malfunctioning components that give conflicting information to different parts of the system. This situation can be expressed abstractly in terms of a group of generals of the Byzantine army camped with their troops around an enemy city. Communicating only by messenger, the generals must agree upon a common battle plan. However, one or more of them may be traitors who will try to confuse the others. The problem is to find an algorithm to ensure that the loyal generals will reach agreement. It is shown that, using only oral messages, this problem is solvable if and only if more than two-thirds of the generals are loyal; so a single traitor can confound two loyal generals. With unforgeable written messages, the problem is solvable for any number of generals and possible traitors. Applications of the solutions to reliable computer systems are then discussed.

The Byzantine Generals Problem

LESLIE LAMPORT, ROBERT SHOSTAK, and MARSHALL PEASE

SRI International

Reliable computer systems must handle malfunctioning components that give conflicting information

to different parts of the system. This situation can be expressed abstractly in terms of a group of

generals of the Byzantine army camped with their troops around an enemy city. Communicating only

by messenger, the generals must agree upon a common battle plan. However, one or more of them

may be traitors who will try to confuse the others. The problem is to find an algorithm to ensure that

the loyal generals will reach agreement. It is shown that, using only oral messages, this problem is

solvable if and only if more than two-thirds of the generals are loyal; so a single traitor can confound

two loyal generals. With unforgeable written messages, the problem is solvable for any number of

generals and possible traitors. Applications of the solutions to reliable computer systems are then

discussed.

Categories and Subject Descriptors: C.2.4. [Computer-Communication Networks]: Distributed

Systems--network operating systems; D.4.4 [Operating Systems]: Communications Management--

network communication; D.4.5 [Operating Systems]: Reliability--fault tolerance

General Terms: Algorithms, Reliability

Additional Key Words and Phrases: Interactive consistency

1. INTRODUCTION

A reliable computer system must be able to cope with the failure of one or more

of its components. A failed component may exhibit a type of behavior that is

often overlooked--namely, sending conflicting information to different parts of

the system. The problem of coping with this type of failure is expressed abstractly

as the Byzantine Generals Problem. We devote the major part of the paper to a

discussion of this abstract problem and conclude by indicating how our solutions

can be used in implementing a reliable computer system.

We imagine that several divisions of the Byzantine army are camped outside

an enemy city, each division commanded by its own general. The generals can

communicate with one another only by messenger. After observing the enemy,

they must decide upon a common plan of action. However, some of the generals

This research was supported in part by the National Aeronautics and Space Administration under

contract NAS1-15428 Mod. 3, the Ballistic Missile Defense Systems Command under contract

DASG60-78-C-0046, and the Army Research Office under contract DAAG29-79-C-0102.

Authors' address: Computer Science Laboratory, SRI International, 333 Ravenswood Avenue, Menlo

Park, CA 94025.

Permission to copy without fee all or part of this material is granted provided that the copies are not

made or distributed for direct commercial advantage, the ACM copyright notice and the title of the

publication and its date appear, and notice is given that copying is by permission of the Association

for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific

permission.

ACM Transactions on Programming Languages and Systems, Vol. 4, No. 3, July 1982, Pages 382-401.

The Byzantine Generals Problem 383

may be traitors, trying to prevent the loyal generals from reaching agreement.

The generals must have an algorithm to guarantee that

A. All loyal generals decide upon the same plan of action.

The loyal generals will all do what the algorithm says they should, but the

traitors may do anything they wish. The algorithm must guarantee condition A

regardless of what the traitors do.

The loyal generals should not only reach agreement, but should agree upon a

reasonable plan. We therefore also want to insure that

B. A small number of traitors cannot cause the loyal generals to adopt a bad

plan.

Condition B is hard to formalize, since it requires saying precisely what a bad

plan is, and we do not attempt to do so. Instead, we consider how the generals

reach a decision. Each general observes the enemy and communicates his obser-

vations to the others. Let

v(i)

be the information communicated by the ith

general. Each general uses some method for combining the values v (1) ..... v (n)

into a single plan of action, where n is the number of generals. Condition A is

achieved by having all generals use the same method for combining the infor-

mation, and Condition B is achieved by using a robust method. For example, if

the only decision to be made is whether to attack or retreat, then

v(i)

con be

General i's opinion of which option is best, and the final decision can be based

upon a majority vote among them. A small number of traitors can affect the

decision only if the loyal generals were almost equally divided between the two

possibilities, in which case neither decision could be called bad.

While this approach may not be the only way to satisfy conditions A and B, it

is the only one we know of. It assumes a method by which the generals

communicate their values v (i) to one another. The obvious method is for the ith

general to send v (i) by messenger to each other general. However, this does not

work, because satisfying condition A requires that every loyal general obtain the

same values v(1) .....

v(n),

and a traitorous general may send different values to

different generals. For condition A to be satisfied, the following must be true:

1. Every loyal general must obtain the same information v (1) .... , v (n).

Condition 1 implies that a general cannot necessarily use a value of

v(i)

obtained directly from the ith general, since a traitorous ith general may send

different values to different generals. This means that unless we are careful, in

meeting condition 1 we might introduce the possibility that the generals use a

value of v (i) different from the one sent by the ith general--even though the ith

general is loyal. We must not allow this to happen if condition B is to be met. For

example, we cannot permit a few traitors to cause the loya~ generals to base their

decision upon the values "retreat",..., "retreat" if every loyal general sent the

value "attack". We therefore have the following requirement for each i:

2. If the ith general is loyal, then the value that he sends must be used by every

loyal general as the value of v (i).

ACM Transactions on Programming Languages and Systems, Vol. 4, No. 3, July 1982.

384 L. Lamport, R. Shostak, and M. Pease

We can rewrite condition I as the condition that for every i (whether or not the

ith general is loyal),

1'. Any two loyal generals use the same value of

v(i).

Conditions 1' and 2 are both conditions on the single value sent by the ith

general. We can therefore restrict our consideration to the problem of how a

single general sends his value to the others. We phrase this in terms of a

commanding general sending an order to his lieutenants, obtaining the following

problem.

Byzantine Generals Problem.

A commanding general must send an order to

his n - 1 lieutenant generals such that

IC1. All loyal lieutenants obey the same order.

IC2. If the commanding general is loyal, then every loyal lieutenant obeys the

order he sends.

Conditions IC1 and IC2 are called the

interactive consistency

conditions. Note

that if the commander is loyal, then IC1 follows from IC2. However, the com-

mander need not be loyal.

To solve our original problem, the ith general sends his value of

v(i)

by using

a solution to the Byzantine Generals Problem to send the order "use v (i) as my

value", with the other generals acting as the lieutenants.

2. IMPOSSIBILITY RESULTS

The Byzantine Generals Problem seems deceptively simple. Its difficulty is

indicated by the surprising fact that if the generals can send only oral messages,

then no solution will work unless more than two-thirds of the generals are loyal.

In particular, with only three generals, no solution can work in the presence of a

single traitor. An oral message is one whose contents are completely under the

control of the sender, so a traitorous sender can transmit any possible message.

Such a message corresponds to the type of message that computers normally

send to one another. In Section 4 we consider signed, written messages, for which

this is not true.

We now show that with oral messages no solution for three generals can handle

a single traitor. For simplicity, we consider the case in which the only possible

decisions are "attack" or "retreat". Let us first examine the scenario pictured in

Figure 1 in which the commander is loyal and sends an "attack" order, but

Lieutenant 2 is a traitor and reports to Lieutenant 1 that he received a "retreat"

order. For IC2 to be satisfied, Lieutenant 1 must obey the order to attack.

Now consider another scenario, shown in Figure 2, in which the commander is

a traitor and sends an "attack" order to Lieutenant 1 and a "retreat" order to

Lieutenant 2. Lieutenant 1 does not know who the traitor is, and he cannot tell

what message the commander actually sent to Lieutenant 2. Hence, the scenarios

in these two pictures appear exactly the same to Lieutenant 1. If the traitor lies

consistently, then there is no way for Lieutenant 1 to distinguish between these

two situations, so he must obey the "attack" order in both of them. Hence,

whenever Lieutenant 1 receives an "attack" order from the commander, he must

obey it.

ACM Transactions on Programming Languages and Systems, Vol. 4, No. 3, July 1982.

剩余19页未读，继续阅读

zuyao0309

粉丝: 0
资源: 2

The-Byzantine-Generals-Problem.pdf

The Byzantine Generals Problem

The Byzantine Generals Problem.zip

The Byzantine Generals Problem

list every art syles

AI定位问题解决方法imv

有哪些算法是属于拜占庭算法

Byzantine算法

拜占庭容错共识算法 公式

上面这个pbft代码运行后要输入什么

区块链中什么是拜占庭将军问题？并给出实用拜占庭容错算法（PBFT）的简要流程

最新资源

拜占庭容错共识算法公式