95:
111:
of retreat to those generals in favor of retreat, 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). The problem is complicated further by the generals being physically separated and having to send their votes via messengers who may fail to deliver votes or may forge false votes.
1645:
268:
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 Lieutenant could have forged the message purportedly from A. It can be shown that if
50:, the "Byzantine generals problem", developed to describe a situation in which, to avoid catastrophic failure of a system, the system's actors must agree on a strategy, but some of these actors are unreliable in such a way as to cause other (good) actors to disagree on the strategy and they may be unaware of the disagreement.
424:, ensuring that a network can continue to function even when some nodes (participants) fail or act maliciously. This tolerance is necessary because blockchains are decentralized systems with no central authority, making it essential to achieve consensus among nodes, even if some try to disrupt the process.
289:
in which benign (non-Byzantine) faults as well as
Byzantine faults may exist simultaneously. For each additional benign fault that must be tolerated, the above numbers need to be incremented by one. If the BFT rounds of communication don't exist, Byzantine failures can occur even with no faulty hardware.
250:
value themselves. This kind of fault tolerance does not encompass the correctness of the value itself; for example, an adversarial component that deliberately sends an incorrect value, but sends that same value consistently to all components, will not be caught in the
Byzantine fault tolerance scheme.
343:
After PBFT, several BFT protocols were introduced to improve its robustness and performance. For instance, Q/U, HQ, Zyzzyva, and ABsTRACTs, addressed the performance and cost issues; whereas other protocols, like
Aardvark and RBFT, addressed its robustness issues. Furthermore, Adapt tried to make use
288:
and the communication is synchronous (bounded delay). The full set of BFT requirements are: For F number of
Byzantine failures, there needs to be at least 3F+1 players (fault containment zones), 2F+1 independent communication paths, and F+1 rounds of communication. There can be hybrid fault models
130:
alone, because failures such as incorrect voltages can propagate through the encryption process. Thus, a faulty message could be sent such that some recipients detect the message as faulty (bad signature), others see it is having a good signature, and a third group also sees a good signature but with
110:
The problem is complicated by the presence of treacherous 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
364:
Byzantine fault tolerance mechanisms use components that repeat an incoming message (or just its signature, which can be reduced to just a single bit of information if self-checking pairs are used for nodes). to other recipients of that incoming message. All these mechanisms make the assumption that
495:
659 SAFEbus network), the Boeing 777 flight control system, and the Boeing 787 flight control systems, use
Byzantine fault tolerance; because these are real-time systems, their Byzantine fault tolerance solutions must have very low latency. For example, SAFEbus can achieve Byzantine fault tolerance
344:
of existing BFT protocols, through switching between them in an adaptive way, to improve system robustness and performance as the underlying conditions change. Furthermore, BFT protocols were introduced that leverage trusted components to reduce the number of replicas, e.g., A2M-PBFT-EA and MinBFT.
328:
There are many systems that claim BFT without meeting the above minimum requirements (e.g., blockchain). Given that there is mathematical proof that this is impossible, these claims need to include a caveat that their definition of BFT strays from the original. That is, systems such as blockchain
249:
Byzantine fault tolerance is only concerned with broadcast consistency, that is, the property that when a component broadcasts a value to all the other components, they all receive exactly this same value, or in the case that the broadcaster is not consistent, the other components agree on a common
267:
as long as the number of disloyal generals is less than one third of the generals. The impossibility of dealing with one-third or more traitors ultimately reduces to proving that the one
Commander and two Lieutenants problem cannot be solved, if the Commander is traitorous. To see this, suppose we
316:
nor error detecting codes such as CRCs provide a known level of protection against
Byzantine errors from natural causes. And more generally, security measures can weaken safety and vice versa. Thus, cryptographic digital signature methods are not a good choice for safety-critical systems, unless
258:
Several early 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
226:
crash, detected by other nodes, Byzantine failures imply no restrictions on what errors can be created, which means that a failed node can generate arbitrary data, including data that makes it appear like a functioning node to a subset of other nodes. Thus, Byzantine failures can confuse failure
122:
The typical mapping of this allegory onto computer systems is that the computers are the generals and their digital communication system links are the messengers. Although the problem is formulated in the allegory as a decision-making and security problem, in electronics, it cannot be solved by
102:
The
Byzantine allegory considers a number of generals who are attacking a fortress. The generals must decide as a group whether to attack or retreat; some may prefer to attack, while others prefer to retreat. The important thing is that all generals agree on a common decision, for a halfhearted
210:
The objective of Byzantine fault tolerance is to be able to defend against failures of system components with or without symptoms that prevent other components of the system from reaching an agreement among themselves, where such an agreement is needed for the correct operation of the system.
312:, provide stronger coverage at a much lower cost. (Note that CRCs can provide guaranteed coverage for errors that cryptography cannot. If an encryption scheme could provide some guarantee of coverage for message errors, it would have a structure that would make it insecure.) But neither
151:. SIFT (for Software Implemented Fault Tolerance) was the brainchild of John Wensley, and was based on the idea of using multiple general-purpose computers that would communicate through pairwise messaging in order to reach a consensus, even if some of the computers were faulty.
1035:
Koopman, Philip; Driscoll, Kevin; Hall, Brendan (March 2015). "Cyclic Redundancy Code and Checksum Algorithms to Ensure Critical Data Integrity" (PDF). Federal Aviation Administration. DOT/FAA/TC-14/49. Archived (PDF) from the original on 18 May 2015. Retrieved 9 May
214:
The remaining operationally correct components of a Byzantine fault tolerant system will be able to continue providing the system's service as originally intended, assuming there are a sufficient number of accurately-operating components to maintain the service.
114:
Byzantine fault tolerance can be achieved if the number of loyal (non-faulty) generals is greater than three times the number of disloyal (faulty) generals. There can be a default vote value given to missing messages. For example, missing messages can be given a
193:
To make the interactive consistency problem easier to understand, Lamport devised a colorful allegory in which a group of army generals formulate a plan for attacking a city. In its original version, the story cast the generals as commanders of the
610:
317:
there is also a specific security threat as well. While error detecting codes, such as CRCs, are better than cryptographic techniques, neither provide adequate coverage for active electronics in safety-critical systems. This is illustrated by the
202:", at the suggestion of Jack Goldberg to future-proof any potential offense-giving. This formulation of the problem, together with some additional results, were presented by the same authors in their 1982 paper, "The Byzantine Generals Problem".
1012:
461:
While traditional blockchains like Bitcoin use Proof of Work (PoW), which is susceptible to a 51% attack, BFT-based systems are designed to tolerate up to one-third of faulty or malicious nodes without compromising the network's integrity.
478:
BFT is especially important in private or permissioned blockchains, where a limited number of known participants need to reach a consensus quickly and securely. These networks often use BFT protocols to enhance performance and security.
339:
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.
365:
the act of repeating a message blocks the propagation of Byzantine symptoms. For systems that have a high degree of safety or security criticality, these assumptions must be proven to be true to an acceptable level of
569:
1590:
Martins, Rolando; Gandhi, Rajeev; Narasimhan, Priya; Pertet, Soila; Casimiro, António; Kreutz, Diego; Veríssimo, Paulo (2013). "Experiences with Fault-Injection in a Byzantine Fault-Tolerant Protocol".
45:
system, where a fault occurs such that different symptoms are presented to different observers, including imperfect information on whether a system component has failed. The term takes its name from an
989:
2017:
308:(where "security" addresses intelligent threats while "safety" addresses the inherent dangers of an activity or mission, i.e., faults due to natural phenomena), error detecting codes, such as
87:
A Byzantine fault is any fault presenting different symptoms to different observers. A Byzantine failure is the loss of a system service due to a Byzantine fault in systems that require
324:
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.
436:
439:
to handle Byzantine faults. These protocols ensure that the majority of honest nodes can agree on the next block in the chain, securing the network against attacks and preventing
234:
The terms fault and failure are used here according to the standard definitions originally created by a joint committee on "Fundamental Concepts and Terminology" formed by the
369:. When providing proof through testing, one difficulty is creating a sufficiently wide range of signals with Byzantine symptoms. Such testing will likely require specialized
98:
If all generals attack in coordination, the battle is won (left). If two generals falsely declare that they intend to attack, but instead retreat, the battle is lost (right).
1643:, Kevin R. Driscoll, "Method for testing the sensitive input range of Byzantine filters", issued 2009-01-06, assigned to Honeywell International Inc.
1364:
1046:
Paulitsch, M.; Morris, J.; Hall, B.; Driscoll, K.; Latronico, E.; Koopman, P. (2005). "Coverage and the Use of Cyclic Redundancy Codes in Ultra-Dependable Systems".
521:
222:. The so-called fail-stop failure mode occupies the simplest end of the spectrum. Whereas the fail-stop failure mode simply means that the only way to fail is a
472:
networks. Instead of relying on a central authority, the network's security depends on the ability of honest nodes to outnumber and outmaneuver malicious ones.
332:
Several system architectures were designed c. 1980 that implemented Byzantine fault tolerance. These include: Draper's FTMP, Honeywell's MMFCS, and SRI's SIFT.
1089:
Hopkins, Albert L.; Lala, Jaynarayan H.; Smith, T. Basil (1987). "The Evolution of Fault Tolerant Computing at the Charles Stark Draper Laboratory, 1955–85".
321:
scenario where a CRC-protected message with a single Byzantine faulty bit presents different data to different observers and each observer sees a valid CRC.
452:
448:
218:
When considering failure propagation only via errors, Byzantine failures are considered the most general and most difficult class of failures among the
1333:
352:
Several examples of Byzantine failures that have occurred are given in two equivalent journal papers. These and other examples are described on the
1260:
Kotla, Ramakrishna; Alvisi, Lorenzo; Dahlin, Mike; Clement, Allen; Wong, Edmund (December 2009). "Zyzzyva: Speculative Byzantine Fault Tolerance".
738:
158:
faulty computers could not "thwart" the efforts of the correctly-operating ones to reach consensus. Shostak showed that a minimum of 3
119:. Further, if the agreement is that the null votes are in the majority, a pre-assigned default strategy can be used (e.g., retreat).
17:
2042:
1659:
Walter, C.; Ellis, P.; LaValley, B. (2005). "The Reliable Platform Service: A Property-Based Fault Tolerant Service Architecture".
435:
Different blockchains use various BFT-based consensus mechanisms like Practical Byzantine Fault Tolerance (PBFT), Tendermint, and
2037:
1852:
488:
1468:
Veronese, G. S.; Correia, M.; Bessani, A. N.; Lung, L. C.; Verissimo, P. (2013-01-01). "Efficient Byzantine Fault-Tolerance".
1358:
680:
Driscoll, Kevin; Hall, Brendan; Sivencrona, Håkan; Zumsteg, Phil (2003). "Byzantine Fault Tolerance, from Theory to Reality".
1997:
1893:
1846:
1816:
1756:
1676:
1608:
1403:
1194:
Abd-El-Malek, M.; Ganger, G.; Goodson, G.; Reiter, M.; Wylie, J. (2005). "Fault-scalable Byzantine Fault-Tolerant Services".
1106:
1065:
697:
651:
154:
At the beginning of the project, it was not clear how many computers in total were needed to guarantee that a conspiracy of
1534:
1269:
1203:
1154:
227:
detection systems, which makes fault tolerance difficult. Despite the allegory, a Byzantine failure is not necessarily a
544:
381:
Byzantine errors were observed infrequently and at irregular points during endurance testing for the newly constructed
1298:
1444:
1244:
147:
problem. This work was done in 1978 in the context of the NASA-sponsored SIFT project in the Computer Science Lab at
1134:(Technical Report), Wright-Patterson Air Force Base, OH: AFWAL/FIGL U.S. Air Force Systems Command, AFWAL-TR-84-3076
304:) can provide Byzantine fault tolerance in the presence of an arbitrary number of traitorous generals. However, for
2032:
880:
1835:
Embedded Software: First International Workshop, EMSOFT 2001, Tahoe City, CA, USA, October 8-10, 2001. Proceedings
1427:
Chun, Byung-Gon; Maniatis, Petros; Shenker, Scott; Kubiatowicz, John (2007-01-01). "Attested append-only memory".
834:
Pease, Marshall; Shostak, Robert; Lamport, Leslie (April 1980). "Reaching Agreement in the Presence of Faults".
408:
allowing the system to overcome Byzantine failures and reach a coherent global view of the system's state. Some
2047:
76:
1921:
1320:
967:
515:
88:
634:
Driscoll, K.; Hall, B.; Paulitsch, M.; Zumsteg, P.; Sivencrona, H. (2004). "The Real Byzantine Generals".
1733:, Springer Optimization and Its Applications, Cham: Springer International Publishing, pp. 389–412,
532:
1725:
Tholoniat, Pierre; Gramoli, Vincent (2022), Tran, Duc A.; Thai, My T.; Krishnamachari, Bhaskar (eds.),
31:
1640:
779:
1482:
1163:
231:
problem involving hostile human interference: it can arise purely from physical or software faults.
848:
758:
589:
538:
526:
382:
293:
187:
1130:
Driscoll, Kevin; Papadopoulos, Gregory; Nelson, Scott; Hartmann, Gary; Ramohalli, Gautham (1984),
309:
301:
223:
1990:
Blockchain Consensus - An Introduction to Classical, Blockchain, and Quantum Consensus Protocols
1477:
1158:
843:
753:
584:
305:
116:
1145:
Castro, M.; Liskov, B. (2002). "Practical Byzantine Fault Tolerance and Proactive Recovery".
1047:
42:
170:=1. His colleague Marshall Pease generalized the algorithm for any n > 0, proving that 3
1701:
8:
1876:
Yeh, Y.C. (2001). "Safety critical avionics for the 777 primary flight controls system".
910:; Landwehr, C. (2004). "Basic concepts and taxonomy of dependable and secure computing".
1770:
1230:
1977:
1969:
1946:
Deirmentzoglou, Evangelos; Papakyriakopoulos, Georgios; Patsakis, Constantinos (2019).
1899:
1734:
1682:
1622:
1503:
1450:
1409:
1383:
1176:
1071:
945:
861:
771:
711:
657:
602:
427:
238:
Computer Society's Technical Committee on Dependable Computing and Fault-Tolerance and
1833:
1993:
1889:
1842:
1812:
1752:
1672:
1614:
1604:
1572:
1495:
1440:
1399:
1240:
1112:
1102:
1061:
949:
937:
816:
812:
703:
693:
647:
313:
297:
148:
127:
1981:
1903:
1686:
1626:
1413:
1180:
1075:
775:
715:
661:
606:
263:
One solution considers scenarios in which messages may be forged, but which will be
2001:
1959:
1881:
1744:
1664:
1596:
1564:
1507:
1487:
1454:
1432:
1391:
1368:
1273:
1207:
1168:
1094:
1053:
1004:
927:
919:
865:
853:
808:
763:
685:
639:
594:
469:
199:
174:+1 is both necessary and sufficient. These results, together with a later proof by
1661:
Ninth IEEE International Symposium on High-Assurance Systems Engineering (HASE'05)
1319:
Clement, A.; Wong, E.; Alvisi, L.; Dahlin, M.; Marchetti, M. (April 22–24, 2009).
1093:. Dependable Computing and Fault-Tolerant Systems. Vol. 1. pp. 121–140.
27:
Fault in a computer system that presents different symptoms to different observers
1804:
1748:
689:
440:
397:
370:
1964:
1947:
1600:
1429:
Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles
1098:
107:, and would be worse than either a coordinated attack or a coordinated retreat.
1726:
1226:
799:"SIFT: design and analysis of a fault-tolerant computer for aircraft control".
734:
565:
409:
366:
336:
175:
140:
2005:
1522:
1008:
643:
512: – Operation that applies a set of distinct changes as a single operation
2026:
1973:
1885:
1618:
1576:
1557:
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
1499:
1116:
941:
907:
820:
707:
509:
497:
405:
243:
219:
139:
The problem of obtaining Byzantine consensus was conceived and formalized by
124:
1436:
1277:
1239:
Symposium on Operating Systems Design and Implementation. pp. 177–190.
1211:
1297:. Proceedings of the 5th European conference on Computer systems. EuroSys.
1292:
1291:
Guerraoui, Rachid; Kneževic, Nikola; Vukolic, Marko; Quéma, Vivien (2010).
1789:
1395:
1172:
857:
767:
598:
1668:
1049:
2005 International Conference on Dependable Systems and Networks (DSN'05)
444:
300:(in modern computer systems, this may be achieved, in practice, by using
242:
Working Group 10.4 on Dependable Computing and Fault Tolerance. See also
1491:
1057:
923:
1945:
1878:
20th DASC. 20th Digital Avionics Systems Conference (Cat. No.01CH37219)
1776:
1363:. 33rd IEEE International Conference on Distributed Computing Systems.
990:"An optimal probabilistic protocol for synchronous Byzantine agreement"
684:. Lecture Notes in Computer Science. Vol. 2788. pp. 235–248.
421:
401:
1831:
1555:
Nanya, T.; Goosen, H.A. (1989). "The Byzantine hardware fault model".
1232:
HQ Replication: A Hybrid Quorum Protocol for Byzantine Fault Tolerance
1595:. Lecture Notes in Computer Science. Vol. 8275. pp. 41–61.
1568:
1388:
2015 IEEE International Parallel and Distributed Processing Symposium
932:
636:
The 23rd Digital Avionics Systems Conference (IEEE Cat. No.04CH37576)
94:
428:
Applications and Examples of Byzantine Fault Tolerance in Blockchain
1917:
1739:
228:
47:
1129:
388:, at least through 2005 (when the issues were publicly reported).
329:
don't guarantee agreement, they only make disagreement expensive.
1322:
Making Byzantine Fault Tolerant Systems Tolerate Byzantine Faults
443:
and other types of fraud. Practical examples of networks include
195:
1329:
1236:
1193:
963:
292:
A second solution requires unforgeable message signatures. For
182:
using digital signatures, were published in the seminal paper,
1832:
Thomas A. Henzinger; Christoph M. Kirsch (26 September 2001).
1426:
905:
1948:"A Survey on Long-Range Attacks for Proof of Stake Protocols"
1727:"Formal Verification of Blockchain Byzantine Fault Tolerance"
1589:
1357:
Aublin, P.-L.; Ben Mokhtar, S.; Quéma, V. (July 8–11, 2013).
1290:
679:
492:
1809:
Industrial Communication Technology Handbook, Second Edition
1328:. Symposium on Networked Systems Design and Implementation.
633:
1530:
1224:
1045:
535: – Quantum version of the Byzantine agreement protocol
353:
239:
235:
104:
1467:
1365:
International Conference on Distributed Computing Systems
1841:. Springer Science & Business Media. pp. 307–.
1382:
Bahsoun, J. P.; Guerraoui, R.; Shoker, A. (2015-05-01).
1259:
522:
List of terms relating to algorithms and data structures
496:
within the order of a microsecond of added latency. The
420:
Byzantine Fault Tolerance (BFT) is a crucial concept in
1702:"How Byzantine Generals Problem Relates to You in 2024"
1318:
468:
Byzantine Fault Tolerance underpins the trust model in
1431:. SOSP '07. New York, NY, USA: ACM. pp. 189–204.
1381:
1356:
1777:
Deirmentzoglou, Papakyriakopoulos & Patsakis 2019
885:
ACM Transactions on Programming Languages and Systems
746:
ACM Transactions on Programming Languages and Systems
577:
ACM Transactions on Programming Languages and Systems
912:
IEEE Transactions on Dependable and Secure Computing
280:, then there are solutions to the problem only when
198:
army. The name was changed, eventually settling on "
1825:
1658:
1039:
833:
733:
564:
500:considers Byzantine fault tolerance in its design.
899:
836:Journal of the Association for Computing Machinery
675:
673:
671:
629:
627:
625:
623:
131:different message contents than the second group.
1639:
1583:
529: – Family of protocols for solving consensus
518: – Distributed algorithm for sensor networks
259:ordered in the case that the Commander is loyal:
2024:
1724:
1088:
1918:"ELC: SpaceX lessons learned [LWN.net]"
1652:
1548:
1082:
668:
620:
1803:M., Paulitsch; Driscoll, K. (9 January 2015).
487:Some aircraft systems, such as the Boeing 777
391:
987:
184:Reaching Agreement in the Presence of Faults.
2018:Byzantine Fault Tolerance in the RKBExplorer
1796:
1229:; Rodrigues, Rodrigo; Shrira, Liuba (2006).
1144:
359:
1554:
729:
727:
725:
482:
41:is a condition of a system, particularly a
1802:
1132:Multi-Microprocessor Flight Control System
964:"Dependable Computing and Fault Tolerance"
682:Computer Safety, Reliability, and Security
1963:
1738:
1481:
1360:RBFT: Redundant Byzantine Fault Tolerance
1162:
1091:The Evolution of Fault-Tolerant Computing
931:
847:
757:
588:
1520:
722:
415:
376:
272:is the number of generals in total, and
103:attack by a few generals would become a
93:
1988:Bashir, Imran. "Blockchain Consensus."
1869:
878:
166:messaging protocol that would work for
162:1 are needed, and devised a two-round 3
14:
2025:
1880:. Vol. 1. pp. 1C2/1–1C2/11.
1384:"Making BFT Protocols Really Adaptive"
489:Aircraft Information Management System
79:or similar system to such conditions.
1699:
1123:
476:Private and Permissioned Blockchains:
412:blockchains also use BFT algorithms.
53:A Byzantine fault is also known as a
1262:ACM Transactions on Computer Systems
1147:ACM Transactions on Computer Systems
794:
792:
1875:
1270:Association for Computing Machinery
1204:Association for Computing Machinery
1196:ACM SIGOPS Operating Systems Review
1155:Association for Computing Machinery
24:
1811:. CRC Press. pp. 48–1–48–26.
616:from the original on 13 June 2018.
545:Conflict-free replicated data type
276:is the number of traitors in that
186:The authors were awarded the 2005
25:
2059:
2011:
789:
737:; Shostak, R.; Pease, M. (1982).
568:; Shostak, R.; Pease, M. (1982).
988:Feldman, P.; Micali, S. (1997).
881:"The Byzantine Generals Problem"
739:"The Byzantine Generals Problem"
570:"The Byzantine Generals Problem"
400:works in parallel to generate a
2043:Fault-tolerant computer systems
1924:from the original on 2016-08-05
1910:
1858:from the original on 2015-09-22
1782:
1718:
1700:Rubby, Matt (20 January 2024).
1693:
1633:
1537:from the original on 2015-04-02
1514:
1461:
1420:
1375:
1350:
1339:from the original on 2010-12-25
1312:
1301:from the original on 2011-10-02
1284:
1253:
1225:Cowling, James; Myers, Daniel;
1218:
1187:
1138:
1029:
1018:from the original on 2016-03-05
981:
970:from the original on 2015-04-02
437:Delegated Proof of Stake (DPoS)
347:
2038:Distributed computing problems
1807:. In Zurawski, Richard (ed.).
1521:Driscoll, Kevin (2012-12-11).
1470:IEEE Transactions on Computers
956:
906:Avizienis, A.; Laprie, J.-C.;
879:Lamport, Leslie (2016-12-19).
872:
827:
558:
547: – Type of data structure
77:fault-tolerant computer system
13:
1:
551:
205:
82:
2000:Apress, Berkeley, CA, 2022.
1749:10.1007/978-3-031-07535-3_12
813:10.1016/0026-2714(79)90211-7
801:Microelectronics Reliability
690:10.1007/978-3-540-39878-3_19
253:
7:
1965:10.1109/ACCESS.2019.2901858
1601:10.1007/978-3-642-45065-5_3
1099:10.1007/978-3-7091-8871-2_6
533:Quantum Byzantine agreement
503:
392:Cryptocurrency applications
335:In 1999, Miguel Castro and
91:among multiple components.
59:Byzantine agreement problem
10:
2064:
1939:
1294:The Next 700 BFT Protocols
541: – Thought experiment
134:
55:Byzantine generals problem
32:Byzantine (disambiguation)
29:
2006:10.1007/978-1-4842-8179-6
1235:. Proceedings of the 7th
1009:10.1137/s0097539790187084
644:10.1109/DASC.2004.1390734
360:Applications in computing
294:security-critical systems
75:) is the resilience of a
69:Byzantine fault tolerance
18:Byzantine Fault Tolerance
1886:10.1109/DASC.2001.963311
638:. pp. 6.D.4–61–11.
527:Paxos (computer science)
516:Brooks–Iyengar algorithm
483:Applications in aviation
265:Byzantine-fault-tolerant
188:Edsger W. Dijkstra Prize
2033:Public-key cryptography
1437:10.1145/1294261.1294280
1278:10.1145/1658357.1658358
1212:10.1145/1095809.1095817
306:safety-critical systems
302:public-key cryptography
178:of the sufficiency of 3
145:interactive consistency
1731:Handbook on Blockchain
1523:"Real System Failures"
459:51% Attack Mitigation:
99:
2048:Theory of computation
1641:US patent 7475318
1396:10.1109/IPDPS.2015.21
1173:10.1145/571637.571640
858:10.1145/322186.322188
768:10.1145/357172.357176
599:10.1145/357172.357176
539:Two Generals' Problem
422:blockchain technology
416:Blockchain Technology
377:Military applications
97:
43:distributed computing
1805:"Chapter 48:SAFEbus"
1669:10.1109/HASE.2005.23
1390:. pp. 904–913.
1052:. pp. 346–355.
466:Decentralized Trust:
455:in this sequence.
356:DASHlink web pages.
143:, who dubbed it the
30:For other uses, see
1492:10.1109/TC.2011.221
1058:10.1109/DSN.2005.31
924:10.1109/TDSC.2004.2
887:. SRI International
785:on 7 February 2017.
1663:. pp. 34–43.
1371:on August 5, 2013.
445:Hyperledger Fabric
433:Safety Mechanisms:
314:digital signatures
298:digital signatures
128:digital signatures
100:
1998:978-1-4842-8178-9
1895:978-0-7803-7034-0
1848:978-3-540-42673-8
1818:978-1-4822-0733-0
1790:"Node Operations"
1758:978-3-031-07535-3
1678:978-0-7695-2377-4
1610:978-3-642-45064-8
1563:(11): 1226–1231.
1405:978-1-4799-8649-1
1108:978-3-7091-8873-6
1067:978-0-7695-2282-1
699:978-3-540-20126-7
653:978-0-7803-8539-9
149:SRI International
63:Byzantine failure
16:(Redirected from
2055:
1985:
1967:
1933:
1932:
1930:
1929:
1914:
1908:
1907:
1873:
1867:
1866:
1864:
1863:
1857:
1840:
1829:
1823:
1822:
1800:
1794:
1793:
1786:
1780:
1779:, p. 28716.
1774:
1768:
1767:
1766:
1765:
1742:
1722:
1716:
1715:
1713:
1712:
1697:
1691:
1690:
1656:
1650:
1649:
1648:
1644:
1637:
1631:
1630:
1587:
1581:
1580:
1569:10.1109/43.41508
1552:
1546:
1545:
1543:
1542:
1518:
1512:
1511:
1485:
1465:
1459:
1458:
1424:
1418:
1417:
1379:
1373:
1372:
1367:. Archived from
1354:
1348:
1347:
1345:
1344:
1338:
1327:
1316:
1310:
1309:
1307:
1306:
1288:
1282:
1281:
1257:
1251:
1250:
1222:
1216:
1215:
1191:
1185:
1184:
1166:
1142:
1136:
1135:
1127:
1121:
1120:
1086:
1080:
1079:
1043:
1037:
1033:
1027:
1026:
1024:
1023:
1017:
994:
985:
979:
978:
976:
975:
960:
954:
953:
935:
903:
897:
896:
894:
892:
876:
870:
869:
851:
831:
825:
824:
807:(3): 190. 1979.
796:
787:
786:
784:
778:. Archived from
761:
743:
731:
720:
719:
677:
666:
665:
631:
618:
617:
615:
592:
574:
562:
386:class submarines
190:for this paper.
21:
2063:
2062:
2058:
2057:
2056:
2054:
2053:
2052:
2023:
2022:
2014:
1958:: 28712–28725.
1942:
1937:
1936:
1927:
1925:
1916:
1915:
1911:
1896:
1874:
1870:
1861:
1859:
1855:
1849:
1838:
1830:
1826:
1819:
1801:
1797:
1788:
1787:
1783:
1775:
1771:
1763:
1761:
1759:
1723:
1719:
1710:
1708:
1698:
1694:
1679:
1657:
1653:
1646:
1638:
1634:
1611:
1593:Middleware 2013
1588:
1584:
1553:
1549:
1540:
1538:
1519:
1515:
1483:10.1.1.408.9972
1466:
1462:
1447:
1425:
1421:
1406:
1380:
1376:
1355:
1351:
1342:
1340:
1336:
1325:
1317:
1313:
1304:
1302:
1289:
1285:
1258:
1254:
1247:
1227:Liskov, Barbara
1223:
1219:
1192:
1188:
1164:10.1.1.127.6130
1143:
1139:
1128:
1124:
1109:
1087:
1083:
1068:
1044:
1040:
1034:
1030:
1021:
1019:
1015:
992:
986:
982:
973:
971:
962:
961:
957:
904:
900:
890:
888:
877:
873:
832:
828:
798:
797:
790:
782:
741:
732:
723:
700:
678:
669:
654:
632:
621:
613:
572:
563:
559:
554:
506:
485:
441:double-spending
430:
418:
398:Bitcoin network
394:
379:
371:fault injectors
362:
350:
319:Schrödinger CRC
256:
208:
137:
85:
39:Byzantine fault
35:
28:
23:
22:
15:
12:
11:
5:
2061:
2051:
2050:
2045:
2040:
2035:
2021:
2020:
2013:
2012:External links
2010:
2009:
2008:
1986:
1941:
1938:
1935:
1934:
1909:
1894:
1868:
1847:
1824:
1817:
1795:
1781:
1769:
1757:
1717:
1692:
1677:
1651:
1632:
1609:
1582:
1547:
1513:
1460:
1445:
1419:
1404:
1374:
1349:
1311:
1283:
1252:
1245:
1217:
1186:
1137:
1122:
1107:
1081:
1066:
1038:
1028:
1003:(4): 873–933.
997:SIAM J. Comput
980:
955:
908:Randell, Brian
898:
871:
849:10.1.1.68.4044
842:(2): 228–234.
826:
788:
759:10.1.1.64.2312
752:(3): 387–389.
721:
698:
667:
652:
619:
590:10.1.1.64.2312
583:(3): 382–401.
556:
555:
553:
550:
549:
548:
542:
536:
530:
524:
519:
513:
505:
502:
484:
481:
429:
426:
417:
414:
410:proof of stake
393:
390:
378:
375:
367:fault coverage
361:
358:
349:
346:
337:Barbara Liskov
326:
325:
322:
290:
255:
252:
207:
204:
176:Leslie Lamport
141:Robert Shostak
136:
133:
84:
81:
26:
9:
6:
4:
3:
2:
2060:
2049:
2046:
2044:
2041:
2039:
2036:
2034:
2031:
2030:
2028:
2019:
2016:
2015:
2007:
2003:
1999:
1995:
1991:
1987:
1983:
1979:
1975:
1971:
1966:
1961:
1957:
1953:
1949:
1944:
1943:
1923:
1919:
1913:
1905:
1901:
1897:
1891:
1887:
1883:
1879:
1872:
1854:
1850:
1844:
1837:
1836:
1828:
1820:
1814:
1810:
1806:
1799:
1791:
1785:
1778:
1773:
1760:
1754:
1750:
1746:
1741:
1736:
1732:
1728:
1721:
1707:
1703:
1696:
1688:
1684:
1680:
1674:
1670:
1666:
1662:
1655:
1642:
1636:
1628:
1624:
1620:
1616:
1612:
1606:
1602:
1598:
1594:
1586:
1578:
1574:
1570:
1566:
1562:
1558:
1551:
1536:
1532:
1528:
1524:
1517:
1509:
1505:
1501:
1497:
1493:
1489:
1484:
1479:
1475:
1471:
1464:
1456:
1452:
1448:
1446:9781595935915
1442:
1438:
1434:
1430:
1423:
1415:
1411:
1407:
1401:
1397:
1393:
1389:
1385:
1378:
1370:
1366:
1362:
1361:
1353:
1335:
1331:
1324:
1323:
1315:
1300:
1296:
1295:
1287:
1279:
1275:
1271:
1267:
1263:
1256:
1248:
1246:1-931971-47-1
1242:
1238:
1234:
1233:
1228:
1221:
1213:
1209:
1205:
1201:
1197:
1190:
1182:
1178:
1174:
1170:
1165:
1160:
1156:
1152:
1148:
1141:
1133:
1126:
1118:
1114:
1110:
1104:
1100:
1096:
1092:
1085:
1077:
1073:
1069:
1063:
1059:
1055:
1051:
1050:
1042:
1032:
1014:
1010:
1006:
1002:
998:
991:
984:
969:
965:
959:
951:
947:
943:
939:
934:
929:
925:
921:
917:
913:
909:
902:
886:
882:
875:
867:
863:
859:
855:
850:
845:
841:
837:
830:
822:
818:
814:
810:
806:
802:
795:
793:
781:
777:
773:
769:
765:
760:
755:
751:
747:
740:
736:
730:
728:
726:
717:
713:
709:
705:
701:
695:
691:
687:
683:
676:
674:
672:
663:
659:
655:
649:
645:
641:
637:
630:
628:
626:
624:
612:
608:
604:
600:
596:
591:
586:
582:
578:
571:
567:
561:
557:
546:
543:
540:
537:
534:
531:
528:
525:
523:
520:
517:
514:
511:
510:Atomic commit
508:
507:
501:
499:
498:SpaceX Dragon
494:
490:
480:
477:
473:
471:
470:decentralized
467:
463:
460:
456:
454:
450:
446:
442:
438:
434:
425:
423:
413:
411:
407:
406:proof-of-work
403:
399:
389:
387:
385:
374:
372:
368:
357:
355:
345:
341:
338:
333:
330:
323:
320:
315:
311:
307:
303:
299:
295:
291:
287:
283:
279:
275:
271:
266:
262:
261:
260:
251:
247:
245:
244:dependability
241:
237:
232:
230:
225:
221:
220:failure modes
216:
212:
203:
201:
197:
191:
189:
185:
181:
177:
173:
169:
165:
161:
157:
152:
150:
146:
142:
132:
129:
126:
125:cryptographic
120:
118:
112:
108:
106:
96:
92:
90:
80:
78:
74:
70:
66:
64:
60:
56:
51:
49:
44:
40:
33:
19:
1989:
1955:
1951:
1926:. Retrieved
1912:
1877:
1871:
1860:. Retrieved
1834:
1827:
1808:
1798:
1784:
1772:
1762:, retrieved
1730:
1720:
1709:. Retrieved
1706:Swan Bitcoin
1705:
1695:
1660:
1654:
1635:
1592:
1585:
1560:
1556:
1550:
1539:. Retrieved
1526:
1516:
1476:(1): 16–30.
1473:
1469:
1463:
1428:
1422:
1387:
1377:
1369:the original
1359:
1352:
1341:. Retrieved
1321:
1314:
1303:. Retrieved
1293:
1286:
1265:
1261:
1255:
1231:
1220:
1199:
1195:
1189:
1150:
1146:
1140:
1131:
1125:
1090:
1084:
1048:
1041:
1031:
1020:. Retrieved
1000:
996:
983:
972:. Retrieved
958:
918:(1): 11–33.
915:
911:
901:
889:. Retrieved
884:
874:
839:
835:
829:
804:
800:
780:the original
749:
745:
681:
635:
580:
576:
560:
486:
475:
474:
465:
464:
458:
457:
432:
431:
419:
395:
383:
380:
363:
351:
348:Applications
342:
334:
331:
327:
318:
285:
281:
277:
273:
269:
264:
257:
248:
233:
217:
213:
209:
192:
183:
179:
171:
167:
163:
159:
155:
153:
144:
138:
121:
117:"null" value
113:
109:
101:
86:
72:
68:
67:
62:
58:
54:
52:
38:
36:
1952:IEEE Access
1157:: 398–461.
735:Lamport, L.
566:Lamport, L.
2027:Categories
1928:2016-07-21
1862:2015-03-05
1764:2024-01-27
1740:1909.07453
1711:2024-01-27
1541:2015-03-02
1343:2010-02-17
1305:2011-10-04
1022:2012-06-14
974:2015-03-02
552:References
402:blockchain
206:Mitigation
83:Definition
1974:2169-3536
1619:0302-9743
1577:0278-0070
1500:0018-9340
1478:CiteSeerX
1159:CiteSeerX
1117:0932-5581
950:215753451
942:1545-5971
933:1903/6459
844:CiteSeerX
821:0026-2714
754:CiteSeerX
708:0302-9743
585:CiteSeerX
491:(via its
254:Solutions
200:Byzantine
89:consensus
1982:84185792
1922:Archived
1904:61489128
1853:Archived
1687:21468069
1627:31337539
1535:Archived
1527:DASHlink
1414:16310807
1334:Archived
1299:Archived
1272:: 1–39.
1181:18793794
1076:14096385
1013:Archived
968:Archived
891:18 March
776:55899582
716:12690337
662:15549497
611:Archived
607:55899582
504:See also
384:Virginia
229:security
196:Albanian
48:allegory
1940:Sources
1508:8157723
1455:6685352
866:6429068
135:History
61:, or a
1996:
1980:
1972:
1902:
1892:
1845:
1815:
1755:
1685:
1675:
1647:
1625:
1617:
1607:
1575:
1506:
1498:
1480:
1453:
1443:
1412:
1402:
1330:USENIX
1243:
1237:USENIX
1206:: 59.
1179:
1161:
1115:
1105:
1074:
1064:
948:
940:
864:
846:
819:
774:
756:
714:
706:
696:
660:
650:
605:
587:
453:Klever
449:Cosmos
284:> 3
1978:S2CID
1970:eISSN
1900:S2CID
1856:(PDF)
1839:(PDF)
1735:arXiv
1683:S2CID
1623:S2CID
1504:S2CID
1451:S2CID
1410:S2CID
1337:(PDF)
1326:(PDF)
1268:(4).
1202:(5).
1177:S2CID
1153:(4).
1072:S2CID
1036:2015.
1016:(PDF)
993:(PDF)
946:S2CID
862:S2CID
783:(PDF)
772:S2CID
742:(PDF)
712:S2CID
658:S2CID
614:(PDF)
603:S2CID
573:(PDF)
493:ARINC
404:with
1994:ISBN
1890:ISBN
1843:ISBN
1813:ISBN
1753:ISBN
1673:ISBN
1615:ISSN
1605:ISBN
1573:ISSN
1531:NASA
1496:ISSN
1441:ISBN
1400:ISBN
1241:ISBN
1113:ISSN
1103:ISBN
1062:ISBN
938:ISSN
893:2019
817:ISSN
704:ISSN
694:ISBN
648:ISBN
451:and
396:The
354:NASA
310:CRCs
240:IFIP
236:IEEE
224:node
105:rout
57:, a
2002:doi
1960:doi
1882:doi
1745:doi
1665:doi
1597:doi
1565:doi
1488:doi
1433:doi
1392:doi
1274:doi
1208:doi
1169:doi
1095:doi
1054:doi
1005:doi
928:hdl
920:doi
854:doi
809:doi
764:doi
686:doi
640:doi
595:doi
164:n+1
73:BFT
2029::
1992:.
1976:.
1968:.
1954:.
1950:.
1920:.
1898:.
1888:.
1851:.
1751:,
1743:,
1729:,
1704:.
1681:.
1671:.
1621:.
1613:.
1603:.
1571:.
1559:.
1533:.
1529:.
1525:.
1502:.
1494:.
1486:.
1474:62
1472:.
1449:.
1439:.
1408:.
1398:.
1386:.
1332:.
1266:27
1264:.
1200:39
1198:.
1175:.
1167:.
1151:20
1149:.
1111:.
1101:.
1070:.
1060:.
1011:.
1001:26
999:.
995:.
966:.
944:.
936:.
926:.
914:.
883:.
860:.
852:.
840:27
838:.
815:.
805:19
803:.
791:^
770:.
762:.
748:.
744:.
724:^
710:.
702:.
692:.
670:^
656:.
646:.
622:^
609:.
601:.
593:.
579:.
575:.
447:,
373:.
296:,
246:.
160:n+
65:.
37:A
2004::
1984:.
1962::
1956:7
1931:.
1906:.
1884::
1865:.
1821:.
1792:.
1747::
1737::
1714:.
1689:.
1667::
1629:.
1599::
1579:.
1567::
1561:8
1544:.
1510:.
1490::
1457:.
1435::
1416:.
1394::
1346:.
1308:.
1280:.
1276::
1249:.
1214:.
1210::
1183:.
1171::
1119:.
1097::
1078:.
1056::
1025:.
1007::
977:.
952:.
930::
922::
916:1
895:.
868:.
856::
823:.
811::
766::
750:4
718:.
688::
664:.
642::
597::
581:4
286:t
282:n
278:n
274:t
270:n
180:n
172:n
168:n
156:n
71:(
34:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.