Byzantine fault tolerance is a sub-field of fault tolerance research inspired by the Byzantine Generals' Problem,[1] which is a generalized version of the Two Generals' Problem.
The objective of Byzantine fault tolerance is to be able to defend against Byzantine failures, in which components of a system fail in arbitrary ways (i.e., not just by stopping or crashing but by processing requests incorrectly, corrupting their local state, and/or producing incorrect or inconsistent outputs.). Correctly functioning components of a Byzantine fault tolerant system will be able to correctly provide the system's service assuming there are not too many Byzantine faulty components.
Failure modes
editA Byzantine fault is an arbitrary fault that occurs during the execution of an algorithm by a distributed system. It encompasses both omission failures (e.g., crash failures, failing to receive a request, or failing to send a response) and commission failures (e.g., processing a request incorrectly, corrupting local state, and/or sending an incorrect or inconsistent response to a request). When a Byzantine failure has occurred, the system may respond in any unpredictable way, unless it is designed to have Byzantine fault tolerance.
For example, if the output of one function is the input of another, then small round-off errors in the first function can produce much larger errors in the second. If the second function were fed into a third, the problem could grow even larger, until the values produced are worthless. Another example is in compiling source code. One minor syntactical error early on in the code can produce large numbers of perceived errors later, as the parser of the compiler gets out-of-phase with the lexical and syntactic information in the source program. Such failures have brought down major Internet services. For example, in 2008 Amazon S3 was brought down for several hours when a single-bit hardware error propagated through the system.[2]
In a Byzantine fault tolerant (BFT) algorithm, steps are taken by processes, the logical abstractions that represent the execution path of the algorithms. A faulty process is one that at some point exhibits any of the above failures. A process that is not faulty is correct.
The Byzantine failure assumption models real-world environments in which computers and networks may behave in unexpected ways due to hardware failures, network congestion and disconnection, as well as malicious attacks. Byzantine failure-tolerant algorithms must cope with such failures and still satisfy the specifications of the problems they are designed to solve. 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.[1] In other words, the algorithm can ensure correct operation only if fewer than one third of the processes are faulty.
Origin
editByzantine refers to the Byzantine Generals' Problem, an agreement problem (first proposed by Marshall Pease, Robert Shostak, and Leslie Lamport in 1980)[3] in which generals of the Byzantine Empire's army must decide unanimously whether to attack some enemy army. (The Byzantine Army was chosen as an example for the problem as the Byzantine state experienced frequent treachery among the high levels of its administration.) The problem is complicated by the geographic separation of the generals, who must communicate by sending messengers to each other, and by the presence of traitors amongst the generals. These traitors can act arbitrarily in order to achieve the following aims: trick some generals into attacking; force a decision that is not consistent with the generals' desires, e.g. forcing an attack when no general wished to attack; or confusing some generals to the point that they are unable to make up their minds. If the traitors succeed in any of these goals, any resulting attack is doomed, as only a concerted effort can result in victory.
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 agreed upon is irrelevant.
Early solutions
editSeveral solutions were originally described by Lamport, Shostak, and Pease in 1982.[1] 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. 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 send 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 3t + 1.[4]
- A second solution requires unforgeable signatures (in modern computer systems, this may be achieved in practice using 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.
Practical Byzantine fault tolerance
editByzantine fault tolerant replication protocols were long considered too expensive to be practical.[citation needed] Then in 1999, Miguel Castro and Barbara Liskov introduced the "Practical Byzantine Fault Tolerance" (PBFT) algorithm,[5] 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,[6] HQ,[7] Zyzzyva,[8] and ABsTRACTs [9] working to lower costs and improve performance and protocols like Aardvark[10] and RBFT[11] working to improve robustness.
UpRight[12] 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 solving the Byzantine Generals' Problem of synchronising the global view and generating computational proof of the majority consensus.[13][14]
Additionally to PBFT and Upright, there is also the BFT-SMaRt library,[15] 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[16] utilizes a slim BFT layer for communication. It prototypes a secure multi-cloud storage system within Java using GPLv2. Focus lies on simplicity and readability, it aims to be the foundation for further research projects.
See also
editReferences
edit- ^ a b c Lamport, L.; Shostak, R.; Pease, M. (1982). "The Byzantine Generals Problem" (PDF). ACM Transactions on Programming Languages and Systems. 4 (3): 382–401. doi:10.1145/357172.357176.
- ^ Amazon S3 Availability Event: July 20, 2008
- ^ Pease, M.; Shostak, R.; Lamport, L. (April 1980). "Reaching Agreement in the Presence of Faults". Journal of the ACM. 27 (2): 228–234. doi:10.1145/322186.322188.
- ^ P. Feldman and S. Micali. An optimal probabilistic protocol for synchronous Byzantine agreement. SIAM J. Computing, 26(4):873{933, 1997.
- ^ M. Castro and B. Liskov, Practical Byzantine Fault Tolerance and Proactive Recovery, ACM Transactions on Computer Systems, v. 20 n. 4, pp. 398-461, 2002.
- ^ M. Abd-El-Malek, G. Ganger, G. Goodson, M. Reiter, J. Wylie, Fault-scalable Byzantine Fault-Tolerant Services, Association for Computing Machinery Symposium on Operating Systems Principles, 2005.
- ^ J. Cowling, Danial Myers, Barbara Liskov, Rodrigo Rodrigues, Liuba Shrira, HQ Replication: A Hybrid Quorum Protocol for Byzantine Fault Tolerance, Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation, 2006.
- ^ R. Kotla, L. Alvisi, M. Dahlin, A. Clement, E. Wong, Zyzzyva: Speculative Byzantine Fault Tolerance, ACM Transactions on Computer Systems, v. 27 n. 4, December 2009
- ^ R, Guerraoui, N. Knežević, M. Vukolić, V. Quéma, The Next 700 BFT Protocols, Proceedings of the 5th European conference on Computer systems (EuroSys), 2010.
- ^ A. Clement, E. Wong, L. Alvisi, M. Dahlin, M. Marchetti, Making Byzantine Fault Tolerant Systems Tolerate Byzantine Faults, USENIX Symposium on Networked Systems Design and Implementation, April 22–24, 2009.
- ^ P.-L. Aublin, S. Ben Mokhtar, V. Quéma, RBFT: Redundant Byzantine Fault Tolerance, International Conference on Distributed Computing Systems: 33rd IEEE International Conference on Distributed Computing Systems, July 8–11, 2013.
- ^ UpRight. Google Code repository for the UpRight replication library.
- ^ "What Is Bitcoin?". Retrieved July 3, 2011.
- ^ Satoshi Nakamoto's 2008-11-13 22:56:55 post
- ^ BFT-SMaRt. Google Code repository for the BFT-SMaRt replication library.
- ^ Archistar. github repository for the Archistar project.
External links
edit- 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.
Category:Public-key cryptography Category:Distributed computing problems Category:Fault tolerance Category:Failure Category:Theory of computation