User:Path-logical/sandbox

"Byzantine generals" redirects here. For actual military generals of the Byzantine empire, see Category:Byzantine generals.

In fault-tolerant computer systems, Byzantine fault tolerance is the characteristic of a system that tolerates the class of failures known as the Byzantine Generals' Problem, which is a generalized version of the [[Two Generals' Problem]]. The phrases interactive consistency or source congruency have been used to refer to Byzantine fault tolerance, particularly among the members of the early implementer teams.

The objective of Byzantine fault tolerance is to be able to defend against Byzantine failures, in which components of a system fail with symptoms that prevent some components of the system from reaching agreement among themselves, where such agreement is needed for the correct operation of the system. Correctly functioning components of a Byzantine fault tolerant system will be able to provide the system's service assuming there are not too many faulty components.

The following practical, concise definitions are helpful in understanding Byzantine fault tolerance:

Byzantine fault

Any fault presenting different symptoms to different observers

Byzantine failure

The loss of a system service due to a Byzantine fault in systems that require

consensus where fault and failure use the standard definitions from the IFIP WG10.4 on Dependable Systems . Note that the type of system services which Byzantine faults affect are agreement (a.k.a consensus) services.

Origin

Byzantine refers to the Byzantine Generals' Problem, an agreement problem (described by Marshall Pease, Robert Shostak, and Leslie Lamport in their 1980 paper, [http://research.microsoft.com/en-us/um/people/lamport/pubs/reaching.pdf "Reaching Agreement in the Presence of Faults"]) in which a group of generals, each commanding a division of the <a href="/wiki/Byzantine_army" title="Byzantine army">Byzantine army</a>, encircling a city. These <a href="/wiki/General" title="General" class="mw-redirect">generals</a> 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 <a href="/wiki/Rout" title="Rout">rout</a> and be worse than a coordinated attack or a coordinated retreat.

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 (non-faulty) generals have a unanimous agreement on their strategy. Note that if the source general is correct, all loyal generals must agree upon that value; otherwise, the choice of strategy used is irrelevant.

http://research.microsoft.com/en-us/um/people/lamport/pubs/pubs.html#byz

Early solutions

Several solutions were described by Lamport, Shostak, and Pease in 1982. 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 other's 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. To see this, suppose we have a traitorous Commander A, and two Lieutenants, B and C: when A tells B to attack and C to retreat, and B and C send messages to each other, forwarding A's message, neither B nor C can figure out who is the traitor, since it is not 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 > 3t.

• A second solution requires unforgeable message signatures. For

security-critical systems, digital signatures (in modern computer systems, this may be achieved in practice using public-key cryptography) can provide Byzantine fault tolerance in the presence of an arbitrary number of traitorous generals. However, for safety-critical systems, simple error detecting codes, such as CRCs, provide the same or better coverage at a much lower cost. Thus, cryptographic digital signature methods are not a good choice for safety-critical systems, unless there is also a specific security threat as well.

• 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.

Practical Byzantine fault tolerance

In 1999, Miguel Castro and Barbara Liskov introduced the "Practical Byzantine Fault Tolerance" (PBFT) algorithm, which provides high-performance Byzantine state machine replication, processing thousands of requests per second with sub-millisecond increases in latency.

PBFT triggered a renaissance in BFT replication research, with protocols like Q/U, HQ, Zyzzyva, and ABsTRACTs working to lower costs and improve performance and protocols like Aardvark and RBFT working to improve robustness.

UpRight is an open source library for constructing services that tolerate both crashes ("up") and Byzantine behaviors ("right") that incorporates many of these protocols' innovations.

One example of BFT in use is Bitcoin, a peer-to-peer digital currency system. The Bitcoin network works in parallel to generate a chain of Hashcash style proof-of-work. The proof-of-work chain is the key to overcome Byzantine failures and to reach a coherent global view of the system state. Hyperledger utilizes PBFT to achieve similar results to Bitcoin but with known entities operating the consensus nodes.

Additionally to PBFT and Upright, there is also the BFT-SMaRt library, a high-performance Byzantine fault-tolerant state machine replication library developed in Java. This library implements a protocol very similar to PBFT's, plus complementary protocols which offer state transfer and on-the-fly reconfiguration of hosts. BFT-SMaRt is the most recent effort to implement state machine replication, still being actively maintained.

Archistar utilizes a slim BFT layer for communication. It prototypes a secure multi-cloud storage system using Java licensed under LGPLv2. Focus lies on simplicity and readability, it aims to be the foundation for further research projects.

Tolerance Degree and Resources

Such algorithms are commonly characterized by their resilience t, the number of faulty processes with which an algorithm can cope.

Many classic agreement problems, such as the Byzantine Generals' Problem, have no solution unless n = 3t + 1, where n is the number of processes in the system and t is the number of traitors (faults). In other words, the algorithm can ensure correct operation only if fewer than one third of the processes are faulty.

See also

• Atomic commit
• Brooks–Iyengar algorithm
• Byzantine Paxos
• Consensus (computer science)
• Quantum Byzantine agreement

External links

• Ocean Store replicates data with a Byzantine fault tolerant commit protocol.
• Practical Byzantine Fault Tolerance
• Byzantine Fault Tolerance in the RKBExplorer
• UpRight is an open source library for Crash-tolerant and Byzantine-tolerant state machine replication.