FACTOID # 5: Minnesota and Connecticut are both in the top 5 in saving money and total tax burden per capita.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Byzantine Fault Tolerance

Byzantine Fault Tolerance is the name given to a sub-field of error tolerance research, inspired by The Byzantine Generals' problem, which is a generalized version of theTwo Generals' Problem. In general, a Byzantine fault is one in which a component of some system not only behaves erroneously, but also fails to behave consistently when interacting with multiple other components. Correctly functioning components of a Byzantine fault tolerant system will be able to reach the same group decisions regardless of Byzantine faulty components. There are upper bounds on the percentage of traitorous or unreliable components, however. An error-tolerant design is one that does not unduly penalize user errors. ... In computing, the Two Generals Problem is a thought experiment meant to illustrate the pitfalls and design challenges of communicating over an unreliable link. ... In fault-tolerant distributed computing, a Byzantine failure is an arbitrary fault that occurs during the execution of an algorithm by a distributed system. ...


The object of Byzantine Fault Tolerance is to be able to defend against a Byzantine failure. Several solutions were originally described by Lamport, Shostak, and Pease in the ACM Transaction on Programming Languages and Systems in 1982. [1] In fault-tolerant distributed computing, a Byzantine failure is an arbitrary fault that occurs during the execution of an algorithm by a distributed system. ... The Association for Computing Machinery, or ACM, was founded in 1947 as the worlds first scientific and educational computing society. ...


The dilemma

The Byzantine Generals problem describes a group of generals, each commanding a division of the Byzantine army, encircling a city. These generals wish to formulate a plan for attacking the city. In its simplest form, the generals must only decide whether to attack or retreat. Some generals may prefer to attack, while others prefer to retreat. The important thing is that every general agrees on a common decision, for a halfhearted attack by a few generals would become a rout and be worse than a coordinated attack or a coordinated retreat. The Byzantine Army was the primary military body of the Byzantine armed forces, serving alongside the Byzantine Navy. ... General is a high military rank, used by nearly every country in the world. ... A rout is a disorderly withdrawal made by a military force following defeat , a collapse of discipline, or poor morale. ...


The problem is complicated by the presence of traitorous generals who may not only cast a vote for a suboptimal strategy, they may do so selectively. For instance, if nine generals are voting, four of whom support attacking while four others are in favor of retreat, the ninth general may send a vote of retreat to a few generals, and a vote of attack to the rest. Those who received a retreat vote from the ninth general will retreat, while the rest will attack (which may not go well for the attackers).


Byzantine fault tolerance can be achieved if the loyal generals have a strategy to compare notes with each other such that conflicting information is disregarded.


Solutions

Lamport, Shostak, and Pease proposed several solutions. They began by noting that the Generals Problem can be reduced to solving a "Commander and Lieutenants" problem where Loyal Lieutenants must all act in unison and that their action must correspond to what the Commander ordered in the case that the Commander is Loyal. Roughly speaking, the Generals vote by treating each others' orders as votes.

  • One solution considers scenarios in which messages may be forged, but which will be Byzantine Fault Tolerant as long as the number of traitorous generals does not equal or exceed one third. The impossibility of dealing with one-third or more traitors ultimately reduces to proving that the 1 Commander + 2 Lieutenants problem cannot be solved if the Commander is traitorous. The reason is, if we have three commanders, A, B, and C, and A is the traitor: when A tells B to attack and C to retreat, and B and C sends messages to each other, forwarding A's message, neither B nor C can figure out who is the traitor, since it isn't necessarily A - the other commander could have forged the message purportedly from A. It can be shown that if n is the number of generals in total, and t is the number of traitors in that n, then there are solutions to the problem only when n is greater than or equal to 3 times t + 1.
  • A second solution requires unforgeable signatures (in modern computer systems, this may be achieved through public key cryptography), but maintains Byzantine Fault Tolerance in the presence of an arbitrary number of traitorous generals.
  • Also presented is a variation on the first two solutions allowing Byzantine Fault Tolerant behavior in some situations where not all generals can communicate directly with each other.
  • ^  "Byzantine Fault Tolerance" paper (PDF)by Lamport, Shostak, and Pease: ACM Transaction on ProgrammingLanguages and Systems, 1982.

Public key cryptography is a form of cryptography which generally allows users to communicate securely without having prior access to a shared secret key. ... To meet Wikipedias quality standards, this article or section may require cleanup. ... The Association for Computing Machinery, or ACM, was founded in 1947 as the worlds first scientific and educational computing society. ...

See also


  Results from FactBites:
 
Reference.com/Encyclopedia/Byzantine fault tolerance (882 words)
Byzantine fault tolerance is the name given to a sub-field of error tolerance research, inspired by The Byzantine Generals' Problem, which is a generalized version of the Two Generals' Problem.
A Byzantine failure (or Byzantine fault) is an arbitrary fault that occurs during the execution of an algorithm by a distributed system.
Byzantine fault tolerance can be achieved if the loyal (non-faulty) generals have a unanimous agreement on their strategy.
CSAIL Research Abstract (1193 words)
Second, to handle Byzantine failures, HRDB uses voting---any response obtained by a client to a SQL statement in a committed transaction is guaranteed to have received a majority vote from among 2f + 1 replicas.
Fail-stop faults are easy to detect and the replica manager replays transactions to bring the replica up to date.
Byzantine faults that result in scheduling errors, particularly on the primary, can be very hard to detect.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m