Errores Bizantinos

The Byzantine Generals Problem
LESLIE LAMPORT, ROBERT SHOSTAK, and MARSHALL PEASE SRI International

Reliable computer systems must handle malfunctioningcomponents 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. Communicatingonly bymessenger, 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 confoundtwo 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]: CommunicationsManagement-networkcommunication; D.4.5 [Operating Systems]: Reliability--fault tolerance General Terms: Algorithms, Reliability Additional Key Words and Phrases: Interactive consistency

/

1. INTRODUCTION A r e l i a b l e c o m p u t e r s y s t e m m u s t b e a b l e to cope w i t h t h e f a i l u r e of o n e or m o r e of its c o m p o n e n t s . A failed c o m p o n e n t m a y e x h i b i t a t y p e of be h a v i o r t h a t is o f t e n o v e r l o o k e d - - n a m e l y , s e n d i n g c o n f l i c t i n g i n f o r m a t i o n to d i f f e r e n t p a r t s of t h e s y s t e m . T h e p r o b l e m of c o p i n g w i t h t h i s t y p e of f a i l u r e is e x p r e s s e d a b s t r a c t l y as t h e B y z a n t i n e G e n e r a l s P r o b l e m . W e d e v o t e t h e m a j o r p a r tof t h e p a p e r to a d i s c u s s i o n of t h i s a b s t r a c t p r o b l e m a n d c o n c l u d e b y i n d i c a t i n g h o w o u r s o l u t i o n s can be used in i m p l e m e n t i n g a reliable c o m p u t e r system. W e i m a g i n e t h a t s e v e r a l d i v i s i o n s of t h e B y z a n t i n e a r m y a r e c a m p e d o u t s i d e a n e n e m y city, e a c h d i v i s io n c o m m a n d e d b y its o w n g e n e r a l . T h e g e n e r a l s c a n communicate with one another only by messenger. After observing the enemy, t h e y m u s t d e c i d e u p o n a c o m m o n p l a n of a c t i o n . H o w e v e r , s o m e of t h e g e n e r a l s 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 commercialadvantage, 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. © 1982 ACM 0164-0925/82/0700-0382 $00.75 ACM Transactionson ProgrammingLanguagesand 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...