The Byzantine Generals Problem

Lamport, Leslie and Shostak, Robert and Pease, Marshall (1982) The Byzantine Generals Problem. ACM Transactions on Programming Languages and Systems (TOPLAS), 4 (3). pp. 382-401.

Text lamport-shostak-pease-byzantine.pdf Restricted to Registered users only Download (1MB)

Abstract

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

Item Type:	Article
Uncontrolled Keywords:	Algorithms Reliability Interactive consistency
Subjects:	Projects > BloSSom 2019 Main Topics > Distributed Systems Main Topics > Theory
Divisions:	Computer Science
Depositing User:	Unnamed user with email richard.dabels@uni-rostock.de
Date Deposited:	03 Sep 2019 16:32
Last Modified:	03 Sep 2019 16:32
URI:	http://blossom.informatik.uni-rostock.de/id/eprint/4

Actions (login required)

View Item