1053:+ 1 phases, with 2 rounds per phase. Each process keeps track of its preferred output (initially equal to the process's own input value). In the first round of each phase each process broadcasts its own preferred value to all other processes. It then receives the values from all processes and determines which value is the majority value and its count. In the second round of the phase, the process whose id matches the current phase number is designated the king of the phase. The king broadcasts the majority value it observed in the first round and serves as a tie breaker. Each process then updates its preferred value as follows. If the count of the majority value the process observed in the first round is greater than
95:. These protocols must satisfy several requirements to be useful. For instance, a trivial protocol could have all processes output binary value 1. This is not useful; thus, the requirement is modified such that the production must depend on the input. That is, the output value of a consensus protocol must be the input value of some process. Another requirement is that a process may decide upon an output value only once, and this decision is irrevocable. A method is correct in an execution if it does not experience a failure. A consensus protocol tolerating halting failures must satisfy the following properties.
274:, the goal is to agree on not just a single value but a series of values over time, forming a progressively-growing history. While multi-valued consensus may be achieved naively by running multiple iterations of a single-valued consensus protocol in succession, many optimizations and other considerations such as reconfiguration support can make multi-valued consensus protocols more efficient in practice.
2284:
attempt to solve a cryptographic puzzle, where probability of finding a solution is proportional to the computational effort expended in hashes per second. The node that first solves such a puzzle has their proposed version of the next block of transactions added to the ledger and eventually accepted
742:
It can be shown that variations of these problems are equivalent in that the solution for a problem in one type of model may be the solution for another problem in another type of model. For example, a solution to the Weak
Byzantine General problem in a synchronous authenticated message passing model
198:
Varying models of computation may define a "consensus problem". Some models may deal with fully connected graphs, while others may deal with rings and trees. In some models message authentication is allowed, whereas in others processes are completely anonymous. Shared memory models in which processes
189:
in the number of rounds of message exchange as a function of some input parameters (typically the number of processes and/or the size of the input domain). Message complexity refers to the amount of message traffic that is generated by the protocol. Other factors may include memory usage and the size
300:
s are failures in which absolutely no conditions are imposed. For example, they may occur as a result of the malicious actions of an adversary. A process that experiences a
Byzantine failure may send contradictory or conflicting data to other processes, or it may sleep and then resume activity after
219:
is signed by the sender, so that a receiver knows not just the immediate source of every message, but the participant that initially created the message. This stronger type of authentication is achieved by digital signatures, and when this stronger form of authentication is available, protocols can
87:
The consensus problem is a fundamental problem in controlling multi-agent systems. One approach to generating consensus is for all processes (agents) to agree on a majority value. In this context, a majority requires at least one more than half of the available votes (where each process is given a
2304:
for some time period. One advantage of a 'proof of stake' over a 'proof of work' system, is the high energy consumption demanded by the latter. As an example, Bitcoin mining (2018) is estimated to consume non-renewable energy sources at an amount similar to the entire nations of Czech
Republic or
1095:
as a consensus protocol in order to manage game state between players in a game. Each game action results in a game state delta broadcast to all other players in the game along with a hash of the total game state. Each player validates the change by applying the delta to their own game state and
2344:
protocols aim to give each real human participant exactly one unit of voting power in permissionless consensus, regardless of economic investment. Proposed approaches to achieving one-per-person distribution of consensus power for proof of personhood include physical pseudonym parties, social
690:
processes in a partially synchronous system (the system alternates between good and bad periods of synchrony), each process chooses a private value. The processes communicate with each other by rounds to determine a public value and generate a consensus vector with the following requirements:
450:
puzzles, and probabilistically earn the right to commit blocks and earn associated rewards in proportion to their invested computational effort. Motivated in part by the high energy cost of this approach, subsequent permissionless consensus protocols have proposed or adopted other alternative
363:
The consensus problem may be considered in the case of asynchronous or synchronous systems. While real world communications are often inherently asynchronous, it is more practical and often easier to model synchronous systems, given that asynchronous systems naturally involve more issues than
231:
models. In an oral communication model, the immediate source of information is known, whereas in stronger, written communication models, every step along the receiver learns not just the immediate source of the message, but the communication history of the message.
259:, restricts the input, and hence the output domain, to a single binary digit {0,1}. While not highly useful by themselves, binary consensus protocols are often useful as building blocks in more general consensus protocols, especially for asynchronous consensus.
2593:
According to the hierarchy, read/write registers cannot solve consensus even in a 2-process system. Data structures like stacks and queues can only solve consensus between two processes. However, some concurrent objects are universal (notated in the table with
2353:
To solve the consensus problem in a shared-memory system, concurrent objects must be introduced. A concurrent object, or shared object, is a data structure which helps concurrent processes communicate to reach an agreement. Traditional implementations using
980:
In a fully asynchronous system there is no consensus solution that can tolerate one or more crash failures even when only requiring the non triviality property. This result is sometimes called the FLP impossibility proof named after the authors
406:
consensus algorithms can circumvent the FLP impossibility result by achieving both safety and liveness with overwhelming probability, even under worst-case scheduling scenarios such as an intelligent denial-of-service attacker in the network.
162:
may be appropriate, according to the application. For example, a weaker type of integrity would be for the decision value to equal a value that some correct process proposed – not necessarily all of them. There is also a condition known as
1076:. Chubby maintains lock information in small files which are stored in a replicated database to achieve high availability in the face of failures. The database is implemented on top of a fault-tolerant log layer which is based on the
743:
leads to a solution for Weak
Interactive Consistency. An interactive consistency algorithm can solve the consensus problem by having each process choose the majority value in its consensus vector as its consensus value.
2285:
by all other nodes. As any node in the network can attempt to solve the proof-of-work problem, a Sybil attack is infeasible in principle unless the attacker has over 50% of the computational resources of the network.
1032:
An example of a polynomial time binary consensus protocol that tolerates
Byzantine failures is the Phase King algorithm by Garay and Berman. The algorithm solves consensus in a synchronous message passing model with
399:
In an asynchronous model, some forms of failures can be handled by a synchronous consensus protocol. For instance, the loss of a communication link may be modeled as a process which has suffered a
Byzantine failure.
371:. In one round, a process may send all the messages it requires, while receiving all messages from other processes. In this manner, no message from one round may influence any messages sent within the same round.
3740:
1001:. However, FLP does not state that consensus can never be reached: merely that under the model's assumptions, no algorithm can always reach consensus in bounded time. In practice it is highly unlikely to occur.
79:
The consensus problem requires agreement among a number of processes (or agents) on a single data value. Some of the processes (agents) may fail or be unreliable in other ways, so consensus protocols must be
391:
for achieving consensus is impossible. This impossibility result derives from worst-case scheduling scenarios, which are unlikely to occur in practice except in adversarial situations such as an intelligent
3344:
1096:
comparing the game state hashes. If the hashes do not agree then a vote is cast, and those players whose game state is in the minority are disconnected and removed from the game (known as a desync.)
2369:
of a concurrent object is defined to be the maximum number of processes in the system which can reach consensus by the given object in a wait-free implementation. Objects with a consensus number of
2308:
Some cryptocurrencies, such as Ripple, use a system of validating nodes to validate the ledger. This system used by Ripple, called Ripple
Protocol Consensus Algorithm (RPCA), works in rounds:
797:
3945:
Divya
Siddarth; Sergey Ivliev; Santiago Siri; Paula Berman (13 Oct 2020). "Who Watches the Watchmen? A Review of Subjective Approaches for Sybil-resistance in Proof of Personhood Protocols".
415:
Consensus algorithms traditionally assume that the set of participating nodes is fixed and given at the outset: that is, that some prior (manual or automatic) configuration process has
430:
consensus protocol, in contrast, allows anyone in the network to join dynamically and participate without prior permission, but instead imposes a different form of artificial cost or
419:
a particular known group of participants who can authenticate each other as members of the group. In the absence of such a well-defined, closed group with authenticated members, a
31:, or agree on some data value that is needed during computation. Example applications of consensus include agreeing on what transactions to commit to a database in which order,
1475:
1593:
423:
against an open consensus group can defeat even a
Byzantine consensus algorithm, simply by creating enough virtual participants to overwhelm the fault tolerance threshold.
3733:
3847:
2084:
3332:
1746:
1702:
1637:
1412:
1334:
1269:
1225:
909:
2612:
2576:
2223:
2159:
2048:
2005:
1923:
1848:
1516:
1375:
1160:
1807:
975:
2542:
2117:
1953:
1878:
1546:
1445:
552:
4050:
Deepak Maram; Harjasleen Malvai; Fan Zhang; Nerla Jean-Louis; Alexander Frolov; Tyler Kell; Tyrone Lobban; Christine Moy; Ari Juels; Andrew Miller (28 Sep 2020).
2340:
Contrasting with the above permissionless participation rules, all of which reward participants in proportion to amount of investment in some action or resource,
1773:
1664:
1296:
1187:
939:
2481:
2446:
2407:
2387:
2244:
2180:
880:
860:
837:
817:
733:
713:
636:
616:
592:
572:
523:
503:
352:
332:
146:
126:
1029:
systems. These algorithms are typically synchronous, dependent on an elected leader to make progress, and tolerate only crashes and not
Byzantine failures.
3323:
3795:
3221:
Bisping, Benjamin; et al. (2016), "Mechanical Verification of a Constructive Proof for FLP", in Blanchette, Jasmin Christian; Merz, Stephan (eds.),
2882:
4379:
4374:
3021:
88:
vote). However, one or more faulty processes may skew the resultant outcome such that consensus may not be reached or may be reached incorrectly.
3103:
27:
is to achieve overall system reliability in the presence of a number of faulty processes. This often requires coordinating processes to reach
4351:
4188:
3989:
3238:
3205:
2940:
2773:
2614:), which means they can solve consensus among any number of processes and they can simulate any other objects through an operation sequence.
2305:
Jordan, while the total energy consumption of Ethereum, the largest proof of stake network, is just under that of 205 average US households.
3297:. Proceedings of the 7th Symposium on Operating Systems Design and Implementation. USENIX Association Berkeley, CA, USA. pp. 335–350.
3169:
2670:
211:
This means that messages are not anonymous, and receivers know the source of every message they receive. Some models assume a stronger,
84:
or resilient. The processes must put forth their candidate values, communicate with one another, and agree on a single consensus value.
2358:
face the risk of crashing if some process dies inside the critical section or sleeps for an intolerably long time. Researchers defined
3880:
2837:
4139:
4254:
4202:
3298:
738:
all messages sent in a round by a correct process are received in the same round by all correct processes (consistency property).
4227:
Fich, Faith; Hendler, Danny; Shavit, Nir (25 July 2004). "On the inherent weakness of conditional synchronization primitives".
1099:
Another well-known approach is called MSR-type algorithms which have been used widely from computer science to control theory.
3843:
3493:
Ben-Or, Michael (1983). "Another advantage of free choice (extended abstract): Completely asynchronous agreement protocols".
480:
3623:
3923:
3821:
3440:
Dibaji, S. M. (July 2017). "Resilient consensus of second-order agent networks: Asynchronous update rules with delays".
758:
4083:
Mohammad-Javad Hajialikhani; Mohammad-Mahdi Jahanara (20 June 2018). "UniqueID: Decentralized Proof-of-Unique-Human".
3904:
Maria Borge; Eleftherios Kokoris-Kogias; Philipp Jovanovic; Linus Gasser; Nicolas Gailly; Bryan Ford (29 April 2017).
2628:
2584:
2489:
447:
3413:
Dibaji, S. M. (May 2015). "Consensus of second-order multi-agent systems in the presence of locally bounded faults".
2409:
or lower, but cannot implement any objects with a higher consensus number. The consensus numbers form what is called
1061:, the process changes its preference to that majority value; otherwise it uses the phase king's value. At the end of
248:, cooperating nodes agree on a single value such as an integer, which may be of variable size so as to encode useful
2732:
2501:
2497:
2315:
Step 2: each server amalgamates all candidates coming from its Unique Nodes List (UNL) and votes on their veracity;
752:
304:
Thus, a consensus protocol tolerating Byzantine failures must be resilient to every possible error that can occur.
64:
3707:
3671:
3620:
Proceedings of the Third Symposium on Operating Systems Design and Implementation, New Orleans, USA, February 1999
307:
A stronger version of consensus tolerating Byzantine failures is given by strengthening the Integrity constraint:
4322:
4058:
3559:
Feldman, Pesech; Micali, Sylvio (1997). "An optimal probabilistic protocol for synchronous Byzantine agreement".
2268:, a difficulty adjustment function and a reorganization function to achieve permissionless consensus in its open
1960:
32:
1073:
1069:
1010:
998:
393:
267:
245:
4320:
Saks, M.; Zaharoglou, F. (2000). "Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge".
3787:
3253:
Berman, Piotr; Garay, Juan A. (1993). "Cloture Votes: n/4-resilient Distributed Consensus in t + 1 rounds".
2457:
388:
170:
A protocol that can correctly guarantee consensus amongst n processes of which at most t fail is said to be
60:
4290:
4232:
3377:
3225:, Lecture Notes in Computer Science, vol. 9807, Springer International Publishing, pp. 107–122,
3143:
3077:
2918:
2862:
2359:
1022:
44:
20:
4052:"CanDID: Can-Do Decentralized Identity with Legacy Compatibility, Sybil-Resistance, and Accountability"
3028:
3818:"The Merge - Implications on the Electricity Consumption and Carbon Footprint of the Ethereum Network"
1450:
882:
are Byzantine, it has been shown that there exists no algorithm that solves the consensus problem for
3459:
3062:
403:
379:
In a fully asynchronous message-passing distributed system, in which at least one process may have a
3382:
2923:
1553:
4295:
4237:
3148:
3082:
2800:
2341:
167:
in the literature which refers to the property that a message sent by a process must be delivered.
92:
396:
in the network. In most normal situations, process scheduling has a degree of natural randomness.
4308:
4260:
4194:
4131:
4084:
4022:
4012:
3946:
3766:
3508:
3475:
3449:
3395:
3270:
3161:
3095:
3002:
2950:
2829:
2812:
2792:
2330:
2277:
1088:
982:
460:
24:
4344:
Blockchain Consensus - An Introduction to Classical, Blockchain, and Quantum Consensus Protocols
3695:
Abraham, Ittai; Devadas, Srinivas; Dolev, Danny; Nayak, Kartik; Ren, Ling (September 11, 2017).
3128:
2914:
2905:
2054:
4347:
4250:
4184:
3985:
3660:
CCS '16: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security
3234:
3201:
2936:
2769:
2666:
2623:
2326:
1719:
1671:
1610:
1381:
1303:
1242:
1194:
1092:
885:
671:: If all correct processes receive the same input value, then they must all output that value.
431:
289:
283:
2597:
2561:
2199:
2135:
2024:
1981:
1899:
1824:
1492:
1351:
1136:
91:
Protocols that solve consensus problems are designed to deal with a limited number of faulty
4355:
4331:
4300:
4242:
4176:
4123:
4032:
3977:
3915:
3663:
3591:
3568:
3539:
3498:
3467:
3422:
3387:
3336:
3262:
3226:
3153:
3087:
2992:
2928:
2874:
2821:
2761:
2701:
2580:
2450:
2355:
1018:
997:
for this significant work. The FLP result has been mechanically verified to hold even under
271:
56:
36:
4281:
Herlihy, M.; Shavit, N. (1999). "The topological structure of asynchronous computability".
4229:
Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing
3869:
2804:
2756:
Aguilera, M. K. (2010). "Stumbling over Consensus Research: Misunderstandings and Issues".
1780:
948:
446:
and a difficulty adjustment function, in which participants compete to solve cryptographic
301:
a lengthy delay. Of the two types of failures, Byzantine failures are far more disruptive.
4173:
Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing
4108:
2962:
2633:
2518:
2453:
2410:
2093:
1929:
1854:
1522:
1421:
1077:
1026:
528:
199:
communicate by accessing objects in shared memory are also an important area of research.
40:
2587:, memory-to-memory move and swap, queue with peek operation, fetch&cons, sticky byte
1752:
1643:
1275:
1166:
918:
3911:
3526:
Dolev, Danny; Fisher, Michael J.; Fowler, Rob; Lynch, Nancy; Strong, H. Raymond (1982).
3463:
3289:
4165:
3058:
2658:
2466:
2431:
2392:
2372:
2334:
2296:, in which nodes compete to append blocks and earn associated rewards in proportion to
2293:
2229:
2165:
1014:
994:
865:
845:
822:
802:
718:
698:
621:
601:
577:
557:
508:
488:
456:
452:
337:
317:
186:
131:
111:
81:
3544:
3527:
915:. The proof is constructed by first showing the impossibility for the three-node case
4368:
4014:
Genuine Personal Identifiers and Mutual Sureties for Sybil-Resilient Community Growth
3973:
3495:
Proceedings of the second annual ACM symposium on Principles of distributed computing
3471:
3368:
LeBlanc, Heath J. (April 2013). "Resilient Asymptotic Consensus in Robust Networks".
2833:
2493:
2265:
990:
443:
3512:
3399:
3099:
2692:
Dolev, D.; Strong, H.R. (1983). "Authenticated algorithms for Byzantine agreement".
4312:
4264:
4198:
4135:
3479:
3426:
3274:
3193:
3165:
3006:
2485:
2269:
435:
420:
4036:
4018:
3967:
2932:
665:: For each correct process, its output must be the input of some correct process.
177:
In evaluating the performance of consensus protocols two factors of interest are
3230:
2796:
2765:
2318:
Step 3: transactions passing the minimum threshold are passed to the next round;
986:
3905:
2325:
Other participation rules used in permissionless consensus protocols to impose
4359:
4335:
3648:
3572:
2273:
68:
52:
3817:
3612:
3391:
1084:
in order to access/update the replicated log; i.e., read/write to the files.
4246:
4180:
3981:
3919:
3667:
3340:
288:
There are two types of failures a process may undergo, a crash failure or a
3844:"Electricity consumption per capita worldwide in 2022, by selected country"
2906:"Unifying Byzantine Consensus Algorithms with Weak Interactive Consistency"
2878:
2362:
as the guarantee that the algorithm completes in a finite number of steps.
4304:
4127:
3503:
3157:
3091:
3022:"The Consensus Problem in Unreliable Distributed Systems (A Brief Survey)"
207:
In most models of communication protocol participants communicate through
2289:
367:
In synchronous systems, it is assumed that all communications proceed in
249:
48:
3596:
3335:. Portland, Oregon, USA: ACM Press New York, NY, USA. pp. 398–407.
2997:
2980:
2825:
2720:
4051:
3696:
3652:
3528:"An Efficient Algorithm for Byzantine Agreement without Authentication"
3266:
2261:
751:
There is a t-resilient anonymous synchronous protocol which solves the
439:
3788:"Bitcoin is an energy hog. Where is all that electricity coming from?"
2345:
networks, pseudonymized government-issued identities, and biometrics.
941:
and using this result to argue about partitions of processors. In the
3771:
2760:. Lecture Notes in Computer Science. Vol. 5959. pp. 59–72.
2312:
Step 1: every server compiles a list of valid candidate transactions;
375:
The FLP impossibility result for asynchronous deterministic consensus
3907:
Proof-of-Personhood: Redemocratizing Permissionless Cryptocurrencies
2705:
640:
for any two correct processes, each process receives the same value.
4089:
4027:
3951:
3454:
203:
Communication channels with direct or transferable authentication
2805:"Impossibility of distributed consensus with one faulty process"
3291:
The Chubby lock service for loosely-coupled distributed systems
3127:
Lamport, Leslie; Marshall Pease; Robert Shostak (April 1980).
2913:. Lecture Notes in Computer Science. Vol. 5293. pp.
442:
introduced the first permissionless consensus protocol using
255:
A special case of the single-value consensus problem, called
3912:
IEEE Security & Privacy on the Blockchain (IEEE S&B)
3588:
On Expected Constant-Round Protocols for Byzantine Agreement
1080:. In this scheme, Chubby clients communicate with the Paxos
39:. Real-world applications often requiring consensus include
652:
Formal requirements for a consensus protocol may include:
296:
occurs when a process abruptly stops and does not resume.
677:: All processes must eventually decide on an output value
451:
participation rules for Sybil attack protection, such as
223:
The two different authentication models are often called
4011:
Gal Shahaf; Ehud Shapiro; Nimrod Talmon (October 2020).
1065:+ 1 phases the processes output their preferred values.
554:
communicate by sending messages to one another. Process
4231:. Association for Computing Machinery. pp. 80–87.
4175:. Association for Computing Machinery. pp. 26–35.
3974:
1st Workshop on Social Network Systems - SocialNets '08
3969:
An Offline Foundation for Online Accountable Pseudonyms
2787:
2785:
3868:
Schwartz, David; Youngs, Noah; Britto, Arthur (2014).
2903:
Milosevic, Zarko; Martin Hutle; Andre Schiper (2009).
778:
763:
4116:
ACM Transactions on Programming Languages and Systems
3070:
ACM Transactions on Programming Languages and Systems
2600:
2564:
2521:
2469:
2434:
2395:
2375:
2300:, or existing cryptocurrency allocated and locked or
2232:
2202:
2168:
2138:
2096:
2057:
2027:
1984:
1932:
1902:
1857:
1827:
1783:
1755:
1722:
1674:
1646:
1613:
1556:
1525:
1495:
1453:
1424:
1384:
1354:
1306:
1278:
1245:
1197:
1169:
1139:
951:
921:
888:
868:
848:
825:
805:
761:
721:
701:
659:: All correct processes must agree on the same value.
624:
604:
580:
560:
531:
511:
491:
471:
Three agreement problems of interest are as follows.
340:
320:
134:
114:
108:
If all the correct processes proposed the same value
102:
Eventually, every correct process decides some value.
2751:
2749:
2389:
can implement any object with a consensus number of
154:
Every correct process must agree on the same value.
2904:
2606:
2570:
2536:
2475:
2440:
2401:
2381:
2238:
2217:
2174:
2153:
2111:
2078:
2042:
1999:
1947:
1917:
1872:
1842:
1801:
1767:
1740:
1696:
1658:
1631:
1587:
1540:
1510:
1469:
1439:
1406:
1369:
1328:
1290:
1263:
1219:
1181:
1154:
969:
933:
903:
874:
854:
831:
811:
792:{\displaystyle {\tfrac {t}{n}}<{\tfrac {1}{3}}}
791:
727:
707:
630:
610:
586:
566:
546:
517:
497:
346:
326:
140:
120:
2719:Gong, Li; Lincoln, Patrick; Rushby, John (1995).
3370:IEEE Journal on Selected Areas in Communications
3333:Symposium on Principles of Distributed Computing
3322:Tushar, C.; Griesemer, R.; Redstone, J. (2007).
2863:"Time- and Space-Efficient Randomized Consensus"
618:is correct, then every correct process receives
354:must have been proposed by some correct process.
4166:"The multiplicative power of consensus numbers"
3765:Chen, Jing; Micali, Silvio (2016). "ALGORAND".
2321:Step 4: the final round requires 80% agreement.
747:Solvability results for some agreement problems
252:such as a transaction committed to a database.
4019:International Conference on Social Informatics
3129:"Reaching Agreement in the Presence of Faults"
2974:
2972:
2725:Dependable Computing for Critical Applications
2687:
2685:
2683:
2681:
4164:Imbs, Damien; Raynal, Michel (25 July 2010).
3331:. Proceedings of the Twenty-Sixth Annual ACM
2665:(3rd ed.), Addison-Wesley, p. 452,
8:
4102:
4100:
3325:Paxos Made Live – An Engineering Perspective
715:, then all correct processes receive either
411:Permissioned versus permissionless consensus
3697:"Efficient Synchronous Byzantine Consensus"
2652:
2650:
2648:
2337:, proof of burn, or proof of elapsed time.
799:and the Weak Byzantine Generals case where
644:It is also known as The General's Problem.
3966:Ford, Bryan; Strauss, Jacob (April 2008).
1021:, are used pervasively in widely deployed
4294:
4236:
4088:
4026:
3950:
3870:"The Ripple Protocol Consensus Algorithm"
3770:
3595:
3543:
3502:
3453:
3381:
3200:(2nd ed.). Wiley. pp. 101–103.
3147:
3081:
2996:
2922:
2721:"Byzantine Agreement with authentication"
2599:
2563:
2520:
2468:
2433:
2413:'s hierarchy of synchronization objects.
2394:
2374:
2231:
2201:
2167:
2137:
2095:
2056:
2026:
1983:
1931:
1901:
1856:
1826:
1782:
1754:
1721:
1685:
1673:
1645:
1612:
1567:
1555:
1524:
1494:
1460:
1452:
1423:
1395:
1383:
1353:
1317:
1305:
1277:
1244:
1208:
1196:
1168:
1138:
1049:. In the phase king algorithm, there are
950:
920:
887:
867:
847:
824:
804:
777:
762:
760:
720:
700:
623:
603:
579:
559:
530:
510:
490:
339:
319:
133:
113:
63:(and multiple robots/agents in general),
3611:Castro, Miguel; Liskov, Barbara (1999).
3053:
3051:
3049:
2663:Distributed Systems: Concepts and Design
2415:
1101:
383:, it has been proven in the famous 1985
4342:Bashir, Imran. "Blockchain Consensus."
3647:Miller, Andrew; Xia, Yu; Croman, Kyle;
3586:Katz, Jonathan; Koo, Chiu-Yuen (2006).
2644:
128:, then any correct process must decide
3824:from the original on September 5, 2023
3798:from the original on February 16, 2023
2958:
2948:
945:there are protocols that can tolerate
387:by Fischer, Lynch and Paterson that a
3926:from the original on 12 November 2020
3746:from the original on December 7, 2022
3613:"Practical Byzantine Fault Tolerance"
2981:"The Weak Byzantine Generals Problem"
7:
4208:from the original on 27 January 2022
359:Asynchronous and synchronous systems
220:tolerate a larger number of faults.
4064:from the original on 9 October 2022
3653:"The honey badger of BFT protocols"
215:form of authentication, where each
3734:"Byzantine agreement made trivial"
2601:
2565:
2257:Permissionless consensus protocols
14:
4107:Herlihy, Maurice (January 1991).
3732:Micali, Sylvio (March 19, 2018).
3713:from the original on July 4, 2023
3061:; Shostak, R.; Pease, M. (1982).
2911:Principles of Distributed Systems
2329:and resist sybil attacks include
2188:Byzantine Agreement Made Trivial
2119:- requires public-key encryption
467:Equivalency of agreement problems
4145:from the original on 5 June 2011
3472:10.1016/j.automatica.2017.03.008
3063:"The Byzantine Generals Problem"
1470:{\displaystyle f<{\sqrt {n}}}
158:Variations on the definition of
4380:Fault-tolerant computer systems
3886:from the original on 2017-08-29
3850:from the original on 2023-09-05
3677:from the original on 2023-06-03
3629:from the original on 2018-03-04
3304:from the original on 2009-12-14
3175:from the original on 2007-01-28
3109:from the original on 2017-02-07
2885:from the original on 2023-02-16
2843:from the original on 2023-01-30
2735:from the original on 2020-01-05
735:or nothing (integrity property)
236:Inputs and outputs of consensus
4375:Distributed computing problems
3786:Irfan, Umair (June 18, 2019).
3427:10.1016/j.sysconle.2015.02.005
2106:
2100:
2073:
2061:
1942:
1936:
1867:
1861:
1796:
1787:
1691:
1678:
1588:{\displaystyle O(f^{3}\log f)}
1582:
1560:
1434:
1428:
1401:
1388:
1323:
1310:
1214:
1201:
819:is the number of failures and
481:Terminating Reliable Broadcast
475:Terminating Reliable Broadcast
1:
3739:. Cambridge, MA: CSAIL, MIT.
3651:; Song, Dawn (October 2016).
3545:10.1016/S0019-9958(82)90776-8
3415:Systems & Control Letters
2288:Other cryptocurrencies (e.g.
2272:network. To extend Bitcoin's
1017:, and variants of it such as
314:If a correct process decides
4354:Apress, Berkeley, CA, 2022.
4037:10.1007/978-3-030-60975-7_24
2933:10.1007/978-3-642-10877-8_24
2250:Requires digital signatures
839:is the number of processes.
682:Weak Interactive Consistency
594:to all processes such that:
278:Crash and Byzantine failures
266:consensus protocols such as
244:consensus protocols such as
4109:"Wait-Free Synchronization"
3255:Theory of Computing Systems
3231:10.1007/978-3-319-43144-4_7
3223:Interactive Theorem Proving
2766:10.1007/978-3-642-11294-2_4
2629:Quantum Byzantine agreement
2585:load-link/store-conditional
1973:Synchronous (liveness)
695:if a correct process sends
185:. Running time is given in
16:Concept in computer science
4396:
2861:Aspnes, James (May 1993).
1971:Asynchronous (safety)
753:Byzantine Generals problem
478:
394:denial-of-service attacker
281:
4360:10.1007/978-1-4842-8179-6
4336:10.1137/S0097539796307698
4323:SIAM Journal on Computing
3704:Cryptology ePrint Archive
3573:10.1137/S0097539790187084
3561:SIAM Journal on Computing
2694:SIAM Journal on Computing
2292:, NEO, STRATIS, ...) use
2079:{\displaystyle O(\log n)}
1961:Public Key Infrastructure
1087:Many peer-to-peer online
1078:Paxos consensus algorithm
1068:Google has implemented a
505:processes, numbered from
33:state machine replication
19:A fundamental problem in
3392:10.1109/JSAC.2013.130413
1741:{\displaystyle n>f+1}
1697:{\displaystyle O(n^{2})}
1632:{\displaystyle n>f+1}
1407:{\displaystyle O(2^{n})}
1329:{\displaystyle O(n^{f})}
1264:{\displaystyle n>f+1}
1220:{\displaystyle O(n^{f})}
1070:distributed lock service
1005:Some consensus protocols
904:{\displaystyle n\leq 3f}
385:FLP impossibility result
240:In the most traditional
4247:10.1145/1011767.1011780
4181:10.1145/1835698.1835705
3982:10.1145/1435497.1435503
3920:10.1109/EuroSPW.2017.46
3668:10.1145/2976749.2978399
3532:Information and Control
3341:10.1145/1281100.1281103
2661:; Tim Kindberg (2001),
2607:{\displaystyle \infty }
2571:{\displaystyle \infty }
2218:{\displaystyle n>3f}
2154:{\displaystyle n>2f}
2043:{\displaystyle n>3f}
2000:{\displaystyle n>3f}
1918:{\displaystyle n>2f}
1843:{\displaystyle n>3f}
1511:{\displaystyle n>3f}
1370:{\displaystyle n>5f}
1155:{\displaystyle n>3f}
1013:consensus algorithm by
389:deterministic algorithm
209:authenticated channels.
2879:10.1006/jagm.1993.1022
2608:
2572:
2546:n-register assignment
2538:
2477:
2442:
2403:
2383:
2240:
2219:
2176:
2155:
2113:
2080:
2044:
2001:
1949:
1919:
1874:
1844:
1803:
1769:
1742:
1698:
1660:
1633:
1589:
1542:
1512:
1471:
1441:
1408:
1371:
1330:
1292:
1265:
1231:Pease-Shostak-Lamport
1221:
1183:
1156:
1125:Pease-Shostak-Lamport
971:
943:written-messages model
935:
905:
876:
856:
833:
813:
793:
729:
709:
632:
612:
588:
574:must transmit a value
568:
548:
519:
499:
348:
328:
142:
122:
4305:10.1145/331524.331529
4128:10.1145/114005.102808
3820:. September 7, 2022.
3504:10.1145/800221.806707
3198:Distributed Computing
3158:10.1145/322186.322188
3092:10.1145/357172.357176
2867:Journal of Algorithms
2609:
2573:
2539:
2478:
2443:
2404:
2384:
2241:
2220:
2177:
2156:
2114:
2090:per tx communication
2081:
2045:
2002:
1950:
1920:
1875:
1845:
1804:
1802:{\displaystyle O(nf)}
1770:
1743:
1699:
1661:
1634:
1590:
1543:
1513:
1472:
1442:
1409:
1372:
1331:
1293:
1266:
1222:
1184:
1157:
1091:games use a modified
972:
970:{\displaystyle n=f+1}
936:
906:
877:
862:processors, of which
857:
834:
814:
794:
730:
710:
633:
613:
589:
569:
549:
520:
500:
349:
329:
229:written communication
194:Models of computation
143:
123:
51:, opinion formation,
45:clock synchronization
21:distributed computing
3288:Burrows, M. (2006).
3020:Fischer, Michael J.
2979:Lamport, L. (1983).
2598:
2562:
2537:{\displaystyle 2n-2}
2519:
2467:
2454:read/write registers
2432:
2393:
2373:
2230:
2200:
2166:
2136:
2112:{\displaystyle O(n)}
2094:
2055:
2025:
1982:
1948:{\displaystyle O(1)}
1930:
1900:
1873:{\displaystyle O(1)}
1855:
1825:
1781:
1777:total communication
1753:
1720:
1672:
1668:total communication
1644:
1611:
1554:
1550:total communication
1541:{\displaystyle 2f+3}
1523:
1493:
1451:
1440:{\displaystyle O(1)}
1422:
1382:
1352:
1304:
1300:total communication
1276:
1243:
1195:
1191:total communication
1167:
1137:
1037:processes and up to
999:fairness assumptions
949:
919:
886:
866:
846:
823:
803:
759:
719:
699:
622:
602:
578:
558:
547:{\displaystyle n-1,}
529:
509:
489:
338:
318:
132:
112:
3597:10.1007/11818175_27
3464:2017arXiv170103430M
2998:10.1145/2402.322398
2826:10.1145/3149.214121
2342:proof of personhood
1768:{\displaystyle f+2}
1659:{\displaystyle f+1}
1291:{\displaystyle f+1}
1182:{\displaystyle f+1}
1041:failures, provided
993:who were awarded a
934:{\displaystyle n=3}
913:oral-messages model
75:Problem description
25:multi-agent systems
4283:Journal of the ACM
3976:. pp. 31–36.
3706:. Paper 2017/307.
3662:. pp. 31–42.
3497:. pp. 27–30.
3267:10.1007/BF01187072
3136:Journal of the ACM
2985:Journal of the ACM
2813:Journal of the ACM
2657:George Coulouris;
2604:
2568:
2534:
2473:
2438:
2399:
2379:
2331:proof of authority
2278:distributed ledger
2236:
2215:
2172:
2151:
2109:
2076:
2040:
1997:
1945:
1915:
1870:
1840:
1799:
1765:
1738:
1694:
1656:
1629:
1585:
1538:
1508:
1467:
1437:
1404:
1367:
1326:
1288:
1261:
1217:
1179:
1152:
1089:real-time strategy
983:Michael J. Fischer
967:
931:
901:
872:
852:
829:
809:
789:
787:
772:
725:
705:
628:
608:
584:
564:
544:
515:
495:
461:proof of authority
364:synchronous ones.
344:
324:
225:oral communication
183:message complexity
138:
118:
4352:978-1-4842-8178-9
4190:978-1-60558-888-9
3991:978-1-60558-124-8
3240:978-3-319-43144-4
3207:978-0-471-45324-6
2942:978-3-642-10876-1
2775:978-3-642-11293-5
2624:Uniform consensus
2591:
2590:
2476:{\displaystyle 2}
2441:{\displaystyle 1}
2402:{\displaystyle n}
2382:{\displaystyle n}
2356:critical sections
2327:barriers to entry
2254:
2253:
2239:{\displaystyle 9}
2175:{\displaystyle 8}
1465:
1093:lockstep protocol
875:{\displaystyle f}
855:{\displaystyle n}
842:For systems with
832:{\displaystyle n}
812:{\displaystyle t}
786:
771:
728:{\displaystyle v}
708:{\displaystyle v}
631:{\displaystyle v}
611:{\displaystyle 0}
587:{\displaystyle v}
567:{\displaystyle 0}
518:{\displaystyle 0}
498:{\displaystyle n}
347:{\displaystyle v}
327:{\displaystyle v}
298:Byzantine failure
290:Byzantine failure
284:Byzantine failure
141:{\displaystyle v}
121:{\displaystyle v}
53:smart power grids
37:atomic broadcasts
4387:
4339:
4330:(5): 1449–1483.
4316:
4298:
4269:
4268:
4240:
4224:
4218:
4217:
4215:
4213:
4207:
4170:
4161:
4155:
4154:
4152:
4150:
4144:
4113:
4104:
4095:
4094:
4092:
4080:
4074:
4073:
4071:
4069:
4063:
4056:
4047:
4041:
4040:
4030:
4008:
4002:
4001:
3999:
3998:
3963:
3957:
3956:
3954:
3942:
3936:
3935:
3933:
3931:
3901:
3895:
3894:
3892:
3891:
3885:
3874:
3865:
3859:
3858:
3856:
3855:
3840:
3834:
3833:
3831:
3829:
3814:
3808:
3807:
3805:
3803:
3783:
3777:
3776:
3774:
3762:
3756:
3755:
3753:
3751:
3745:
3738:
3729:
3723:
3722:
3720:
3718:
3712:
3701:
3692:
3686:
3685:
3683:
3682:
3676:
3657:
3644:
3638:
3637:
3635:
3634:
3628:
3617:
3608:
3602:
3601:
3599:
3583:
3577:
3576:
3556:
3550:
3549:
3547:
3523:
3517:
3516:
3506:
3490:
3484:
3483:
3457:
3437:
3431:
3430:
3410:
3404:
3403:
3385:
3365:
3359:
3358:
3356:
3355:
3349:
3343:. Archived from
3330:
3319:
3313:
3312:
3310:
3309:
3303:
3296:
3285:
3279:
3278:
3250:
3244:
3243:
3218:
3212:
3211:
3190:
3184:
3183:
3181:
3180:
3174:
3151:
3133:
3124:
3118:
3117:
3115:
3114:
3108:
3085:
3067:
3055:
3044:
3043:
3041:
3039:
3034:on 22 April 2014
3033:
3027:. Archived from
3026:
3017:
3011:
3010:
3000:
2976:
2967:
2966:
2960:
2956:
2954:
2946:
2926:
2908:
2900:
2894:
2893:
2891:
2890:
2858:
2852:
2851:
2849:
2848:
2842:
2809:
2789:
2780:
2779:
2753:
2744:
2743:
2741:
2740:
2716:
2710:
2709:
2689:
2676:
2675:
2672:978-0201-61918-8
2654:
2613:
2611:
2610:
2605:
2581:compare-and-swap
2577:
2575:
2574:
2569:
2543:
2541:
2540:
2535:
2482:
2480:
2479:
2474:
2447:
2445:
2444:
2439:
2416:
2408:
2406:
2405:
2400:
2388:
2386:
2385:
2380:
2367:consensus number
2349:Consensus number
2245:
2243:
2242:
2237:
2224:
2222:
2221:
2216:
2181:
2179:
2178:
2173:
2160:
2158:
2157:
2152:
2118:
2116:
2115:
2110:
2085:
2083:
2082:
2077:
2049:
2047:
2046:
2041:
2006:
2004:
2003:
1998:
1954:
1952:
1951:
1946:
1924:
1922:
1921:
1916:
1879:
1877:
1876:
1871:
1849:
1847:
1846:
1841:
1808:
1806:
1805:
1800:
1774:
1772:
1771:
1766:
1747:
1745:
1744:
1739:
1703:
1701:
1700:
1695:
1690:
1689:
1665:
1663:
1662:
1657:
1638:
1636:
1635:
1630:
1594:
1592:
1591:
1586:
1572:
1571:
1547:
1545:
1544:
1539:
1517:
1515:
1514:
1509:
1476:
1474:
1473:
1468:
1466:
1461:
1446:
1444:
1443:
1438:
1413:
1411:
1410:
1405:
1400:
1399:
1376:
1374:
1373:
1368:
1335:
1333:
1332:
1327:
1322:
1321:
1297:
1295:
1294:
1289:
1270:
1268:
1267:
1262:
1226:
1224:
1223:
1218:
1213:
1212:
1188:
1186:
1185:
1180:
1161:
1159:
1158:
1153:
1102:
976:
974:
973:
968:
940:
938:
937:
932:
910:
908:
907:
902:
881:
879:
878:
873:
861:
859:
858:
853:
838:
836:
835:
830:
818:
816:
815:
810:
798:
796:
795:
790:
788:
779:
773:
764:
734:
732:
731:
726:
714:
712:
711:
706:
637:
635:
634:
629:
617:
615:
614:
609:
593:
591:
590:
585:
573:
571:
570:
565:
553:
551:
550:
545:
524:
522:
521:
516:
504:
502:
501:
496:
485:A collection of
434:to mitigate the
432:barrier to entry
353:
351:
350:
345:
333:
331:
330:
325:
257:binary consensus
147:
145:
144:
139:
127:
125:
124:
119:
57:state estimation
4395:
4394:
4390:
4389:
4388:
4386:
4385:
4384:
4365:
4364:
4319:
4280:
4277:
4275:Further reading
4272:
4257:
4226:
4225:
4221:
4211:
4209:
4205:
4191:
4168:
4163:
4162:
4158:
4148:
4146:
4142:
4111:
4106:
4105:
4098:
4082:
4081:
4077:
4067:
4065:
4061:
4054:
4049:
4048:
4044:
4010:
4009:
4005:
3996:
3994:
3992:
3965:
3964:
3960:
3944:
3943:
3939:
3929:
3927:
3903:
3902:
3898:
3889:
3887:
3883:
3872:
3867:
3866:
3862:
3853:
3851:
3842:
3841:
3837:
3827:
3825:
3816:
3815:
3811:
3801:
3799:
3785:
3784:
3780:
3764:
3763:
3759:
3749:
3747:
3743:
3736:
3731:
3730:
3726:
3716:
3714:
3710:
3699:
3694:
3693:
3689:
3680:
3678:
3674:
3655:
3646:
3645:
3641:
3632:
3630:
3626:
3615:
3610:
3609:
3605:
3590:. CRYPTO 2006.
3585:
3584:
3580:
3558:
3557:
3553:
3525:
3524:
3520:
3492:
3491:
3487:
3439:
3438:
3434:
3412:
3411:
3407:
3383:10.1.1.310.5354
3367:
3366:
3362:
3353:
3351:
3347:
3328:
3321:
3320:
3316:
3307:
3305:
3301:
3294:
3287:
3286:
3282:
3252:
3251:
3247:
3241:
3220:
3219:
3215:
3208:
3192:
3191:
3187:
3178:
3176:
3172:
3131:
3126:
3125:
3121:
3112:
3110:
3106:
3065:
3057:
3056:
3047:
3037:
3035:
3031:
3024:
3019:
3018:
3014:
2978:
2977:
2970:
2957:
2947:
2943:
2924:10.1.1.180.4229
2902:
2901:
2897:
2888:
2886:
2860:
2859:
2855:
2846:
2844:
2840:
2807:
2801:Paterson, M. S.
2791:
2790:
2783:
2776:
2755:
2754:
2747:
2738:
2736:
2718:
2717:
2713:
2706:10.1137/0212045
2691:
2690:
2679:
2673:
2656:
2655:
2646:
2642:
2634:Byzantine fault
2620:
2596:
2595:
2560:
2559:
2517:
2516:
2465:
2464:
2430:
2429:
2420:
2391:
2390:
2371:
2370:
2351:
2259:
2246:
2228:
2227:
2198:
2197:
2164:
2163:
2134:
2133:
2092:
2091:
2086:
2053:
2052:
2023:
2022:
1980:
1979:
1972:
1955:
1928:
1927:
1898:
1897:
1880:
1853:
1852:
1823:
1822:
1813:Feldman-Micali
1779:
1778:
1751:
1750:
1718:
1717:
1681:
1670:
1669:
1642:
1641:
1609:
1608:
1563:
1552:
1551:
1521:
1520:
1491:
1490:
1449:
1448:
1420:
1419:
1414:
1391:
1380:
1379:
1350:
1349:
1313:
1302:
1301:
1274:
1273:
1241:
1240:
1204:
1193:
1192:
1165:
1164:
1135:
1134:
1072:library called
1027:cloud computing
1007:
947:
946:
917:
916:
884:
883:
864:
863:
844:
843:
821:
820:
801:
800:
757:
756:
749:
717:
716:
697:
696:
684:
669:Strong validity
650:
620:
619:
600:
599:
576:
575:
556:
555:
527:
526:
507:
506:
487:
486:
483:
477:
469:
413:
377:
361:
336:
335:
316:
315:
286:
280:
238:
205:
196:
130:
129:
110:
109:
77:
61:control of UAVs
41:cloud computing
17:
12:
11:
5:
4393:
4391:
4383:
4382:
4377:
4367:
4366:
4363:
4362:
4340:
4317:
4296:10.1.1.78.1455
4276:
4273:
4271:
4270:
4255:
4238:10.1.1.96.9340
4219:
4189:
4156:
4122:(1): 124–149.
4096:
4075:
4042:
4003:
3990:
3958:
3937:
3896:
3860:
3835:
3809:
3778:
3757:
3724:
3687:
3639:
3603:
3578:
3567:(4): 873–933.
3551:
3538:(3): 257–274.
3518:
3485:
3432:
3405:
3376:(4): 766–781.
3360:
3314:
3280:
3245:
3239:
3213:
3206:
3185:
3149:10.1.1.68.4044
3142:(2): 228–234.
3119:
3083:10.1.1.64.2312
3076:(3): 382–401.
3045:
3012:
2968:
2959:|journal=
2941:
2895:
2873:(3): 414–431.
2853:
2820:(2): 374–382.
2793:Fischer, M. J.
2781:
2774:
2745:
2711:
2700:(4): 656–666.
2677:
2671:
2659:Jean Dollimore
2643:
2641:
2638:
2637:
2636:
2631:
2626:
2619:
2616:
2603:
2589:
2588:
2578:
2567:
2556:
2555:
2552:
2548:
2547:
2544:
2533:
2530:
2527:
2524:
2513:
2512:
2509:
2505:
2504:
2483:
2472:
2461:
2460:
2448:
2437:
2426:
2425:
2422:
2398:
2378:
2350:
2347:
2335:proof of space
2323:
2322:
2319:
2316:
2313:
2294:proof of stake
2258:
2255:
2252:
2251:
2248:
2235:
2225:
2214:
2211:
2208:
2205:
2195:
2192:
2189:
2185:
2184:
2182:
2171:
2161:
2150:
2147:
2144:
2141:
2131:
2128:
2125:
2124:Abraham et al.
2121:
2120:
2108:
2105:
2102:
2099:
2088:
2075:
2072:
2069:
2066:
2063:
2060:
2050:
2039:
2036:
2033:
2030:
2020:
2017:
2014:
2010:
2009:
2007:
1996:
1993:
1990:
1987:
1977:
1974:
1969:
1965:
1964:
1957:
1944:
1941:
1938:
1935:
1925:
1914:
1911:
1908:
1905:
1895:
1892:
1889:
1885:
1884:
1882:
1869:
1866:
1863:
1860:
1850:
1839:
1836:
1833:
1830:
1820:
1817:
1814:
1810:
1809:
1798:
1795:
1792:
1789:
1786:
1775:
1764:
1761:
1758:
1748:
1737:
1734:
1731:
1728:
1725:
1715:
1712:
1709:
1705:
1704:
1693:
1688:
1684:
1680:
1677:
1666:
1655:
1652:
1649:
1639:
1628:
1625:
1622:
1619:
1616:
1606:
1603:
1600:
1596:
1595:
1584:
1581:
1578:
1575:
1570:
1566:
1562:
1559:
1548:
1537:
1534:
1531:
1528:
1518:
1507:
1504:
1501:
1498:
1488:
1485:
1482:
1478:
1477:
1464:
1459:
1456:
1436:
1433:
1430:
1427:
1416:
1403:
1398:
1394:
1390:
1387:
1377:
1366:
1363:
1360:
1357:
1347:
1344:
1341:
1337:
1336:
1325:
1320:
1316:
1312:
1309:
1298:
1287:
1284:
1281:
1271:
1260:
1257:
1254:
1251:
1248:
1238:
1235:
1232:
1228:
1227:
1216:
1211:
1207:
1203:
1200:
1189:
1178:
1175:
1172:
1162:
1151:
1148:
1145:
1142:
1132:
1129:
1126:
1122:
1121:
1118:
1115:
1112:
1111:Authentication
1109:
1106:
1015:Leslie Lamport
1006:
1003:
995:Dijkstra Prize
966:
963:
960:
957:
954:
930:
927:
924:
900:
897:
894:
891:
871:
851:
828:
808:
785:
782:
776:
770:
767:
748:
745:
740:
739:
736:
724:
704:
683:
680:
679:
678:
672:
666:
660:
649:
646:
642:
641:
638:
627:
607:
583:
563:
543:
540:
537:
534:
514:
494:
479:Main article:
476:
473:
468:
465:
457:proof of space
453:proof of stake
428:permissionless
412:
409:
376:
373:
360:
357:
356:
355:
343:
323:
312:
279:
276:
237:
234:
204:
201:
195:
192:
187:Big O notation
156:
155:
152:
149:
137:
117:
106:
103:
100:
82:fault-tolerant
76:
73:
71:, and others.
65:load balancing
15:
13:
10:
9:
6:
4:
3:
2:
4392:
4381:
4378:
4376:
4373:
4372:
4370:
4361:
4357:
4353:
4349:
4345:
4341:
4337:
4333:
4329:
4325:
4324:
4318:
4314:
4310:
4306:
4302:
4297:
4292:
4288:
4284:
4279:
4278:
4274:
4266:
4262:
4258:
4256:1-58113-802-4
4252:
4248:
4244:
4239:
4234:
4230:
4223:
4220:
4204:
4200:
4196:
4192:
4186:
4182:
4178:
4174:
4167:
4160:
4157:
4141:
4137:
4133:
4129:
4125:
4121:
4117:
4110:
4103:
4101:
4097:
4091:
4086:
4079:
4076:
4060:
4053:
4046:
4043:
4038:
4034:
4029:
4024:
4020:
4016:
4015:
4007:
4004:
3993:
3987:
3983:
3979:
3975:
3971:
3970:
3962:
3959:
3953:
3948:
3941:
3938:
3925:
3921:
3917:
3913:
3909:
3908:
3900:
3897:
3882:
3878:
3871:
3864:
3861:
3849:
3845:
3839:
3836:
3823:
3819:
3813:
3810:
3797:
3793:
3789:
3782:
3779:
3773:
3768:
3761:
3758:
3742:
3735:
3728:
3725:
3709:
3705:
3698:
3691:
3688:
3673:
3669:
3665:
3661:
3654:
3650:
3643:
3640:
3625:
3621:
3614:
3607:
3604:
3598:
3593:
3589:
3582:
3579:
3574:
3570:
3566:
3562:
3555:
3552:
3546:
3541:
3537:
3533:
3529:
3522:
3519:
3514:
3510:
3505:
3500:
3496:
3489:
3486:
3481:
3477:
3473:
3469:
3465:
3461:
3456:
3451:
3447:
3443:
3436:
3433:
3428:
3424:
3420:
3416:
3409:
3406:
3401:
3397:
3393:
3389:
3384:
3379:
3375:
3371:
3364:
3361:
3350:on 2014-12-12
3346:
3342:
3338:
3334:
3327:
3326:
3318:
3315:
3300:
3293:
3292:
3284:
3281:
3276:
3272:
3268:
3264:
3260:
3256:
3249:
3246:
3242:
3236:
3232:
3228:
3224:
3217:
3214:
3209:
3203:
3199:
3195:
3194:Attiya, Hagit
3189:
3186:
3171:
3167:
3163:
3159:
3155:
3150:
3145:
3141:
3137:
3130:
3123:
3120:
3105:
3101:
3097:
3093:
3089:
3084:
3079:
3075:
3071:
3064:
3060:
3054:
3052:
3050:
3046:
3030:
3023:
3016:
3013:
3008:
3004:
2999:
2994:
2990:
2986:
2982:
2975:
2973:
2969:
2964:
2952:
2944:
2938:
2934:
2930:
2925:
2920:
2916:
2912:
2907:
2899:
2896:
2884:
2880:
2876:
2872:
2868:
2864:
2857:
2854:
2839:
2835:
2831:
2827:
2823:
2819:
2815:
2814:
2806:
2802:
2798:
2794:
2788:
2786:
2782:
2777:
2771:
2767:
2763:
2759:
2752:
2750:
2746:
2734:
2730:
2726:
2722:
2715:
2712:
2707:
2703:
2699:
2695:
2688:
2686:
2684:
2682:
2678:
2674:
2668:
2664:
2660:
2653:
2651:
2649:
2645:
2639:
2635:
2632:
2630:
2627:
2625:
2622:
2621:
2617:
2615:
2586:
2582:
2579:
2558:
2557:
2553:
2550:
2549:
2545:
2531:
2528:
2525:
2522:
2515:
2514:
2510:
2507:
2506:
2503:
2499:
2495:
2494:fetch-and-add
2491:
2487:
2484:
2470:
2463:
2462:
2459:
2455:
2452:
2449:
2435:
2428:
2427:
2423:
2418:
2417:
2414:
2412:
2396:
2376:
2368:
2363:
2361:
2357:
2348:
2346:
2343:
2338:
2336:
2332:
2328:
2320:
2317:
2314:
2311:
2310:
2309:
2306:
2303:
2299:
2295:
2291:
2286:
2283:
2279:
2275:
2271:
2267:
2266:proof of work
2263:
2256:
2249:
2233:
2226:
2212:
2209:
2206:
2203:
2196:
2193:
2190:
2187:
2186:
2183:
2169:
2162:
2148:
2145:
2142:
2139:
2132:
2129:
2126:
2123:
2122:
2103:
2097:
2089:
2070:
2067:
2064:
2058:
2051:
2037:
2034:
2031:
2028:
2021:
2018:
2015:
2012:
2011:
2008:
1994:
1991:
1988:
1985:
1978:
1975:
1970:
1967:
1966:
1962:
1958:
1939:
1933:
1926:
1912:
1909:
1906:
1903:
1896:
1893:
1890:
1887:
1886:
1883:
1864:
1858:
1851:
1837:
1834:
1831:
1828:
1821:
1818:
1815:
1812:
1811:
1793:
1790:
1784:
1776:
1762:
1759:
1756:
1749:
1735:
1732:
1729:
1726:
1723:
1716:
1713:
1710:
1708:Dolev-Strong
1707:
1706:
1686:
1682:
1675:
1667:
1653:
1650:
1647:
1640:
1626:
1623:
1620:
1617:
1614:
1607:
1604:
1601:
1599:Dolev-Strong
1598:
1597:
1579:
1576:
1573:
1568:
1564:
1557:
1549:
1535:
1532:
1529:
1526:
1519:
1505:
1502:
1499:
1496:
1489:
1486:
1483:
1480:
1479:
1462:
1457:
1454:
1431:
1425:
1417:
1396:
1392:
1385:
1378:
1364:
1361:
1358:
1355:
1348:
1345:
1342:
1339:
1338:
1318:
1314:
1307:
1299:
1285:
1282:
1279:
1272:
1258:
1255:
1252:
1249:
1246:
1239:
1236:
1233:
1230:
1229:
1209:
1205:
1198:
1190:
1176:
1173:
1170:
1163:
1149:
1146:
1143:
1140:
1133:
1130:
1127:
1124:
1123:
1119:
1116:
1113:
1110:
1107:
1104:
1103:
1100:
1097:
1094:
1090:
1085:
1083:
1079:
1075:
1071:
1066:
1064:
1060:
1056:
1052:
1048:
1044:
1040:
1036:
1030:
1028:
1024:
1020:
1016:
1012:
1004:
1002:
1000:
996:
992:
991:Mike Paterson
988:
984:
978:
964:
961:
958:
955:
952:
944:
928:
925:
922:
914:
898:
895:
892:
889:
869:
849:
840:
826:
806:
783:
780:
774:
768:
765:
754:
746:
744:
737:
722:
702:
694:
693:
692:
689:
681:
676:
673:
670:
667:
664:
663:Weak validity
661:
658:
655:
654:
653:
647:
645:
639:
625:
605:
597:
596:
595:
581:
561:
541:
538:
535:
532:
512:
492:
482:
474:
472:
466:
464:
462:
458:
454:
449:
445:
444:proof of work
441:
437:
433:
429:
424:
422:
418:
410:
408:
405:
401:
397:
395:
390:
386:
382:
381:crash failure
374:
372:
370:
365:
358:
341:
321:
313:
310:
309:
308:
305:
302:
299:
295:
294:crash failure
291:
285:
277:
275:
273:
269:
265:
260:
258:
253:
251:
247:
243:
235:
233:
230:
226:
221:
218:
214:
210:
202:
200:
193:
191:
190:of messages.
188:
184:
180:
175:
173:
168:
166:
161:
153:
150:
135:
115:
107:
104:
101:
98:
97:
96:
94:
89:
85:
83:
74:
72:
70:
66:
62:
58:
54:
50:
46:
42:
38:
34:
30:
26:
22:
4343:
4327:
4321:
4286:
4282:
4228:
4222:
4210:. Retrieved
4172:
4159:
4147:. Retrieved
4119:
4115:
4078:
4066:. Retrieved
4045:
4013:
4006:
3995:. Retrieved
3968:
3961:
3940:
3928:. Retrieved
3906:
3899:
3888:. Retrieved
3876:
3863:
3852:. Retrieved
3838:
3828:September 5,
3826:. Retrieved
3812:
3800:. Retrieved
3791:
3781:
3772:1607.01341v9
3760:
3748:. Retrieved
3727:
3715:. Retrieved
3703:
3690:
3679:. Retrieved
3659:
3642:
3631:. Retrieved
3619:
3606:
3587:
3581:
3564:
3560:
3554:
3535:
3531:
3521:
3494:
3488:
3445:
3441:
3435:
3418:
3414:
3408:
3373:
3369:
3363:
3352:. Retrieved
3345:the original
3324:
3317:
3306:. Retrieved
3290:
3283:
3258:
3254:
3248:
3222:
3216:
3197:
3188:
3177:. Retrieved
3139:
3135:
3122:
3111:. Retrieved
3073:
3069:
3036:. Retrieved
3029:the original
3015:
2988:
2984:
2910:
2898:
2887:. Retrieved
2870:
2866:
2856:
2845:. Retrieved
2817:
2811:
2797:Lynch, N. A.
2757:
2737:. Retrieved
2728:
2724:
2714:
2697:
2693:
2662:
2592:
2496:, wait-free
2486:test-and-set
2366:
2364:
2360:wait-freedom
2352:
2339:
2324:
2307:
2301:
2297:
2287:
2281:
2270:peer-to-peer
2260:
2016:Asynchronous
2013:HoneyBadger
1481:Dolev et al.
1447:rounds when
1343:Asynchronous
1098:
1086:
1081:
1067:
1062:
1058:
1054:
1050:
1046:
1042:
1038:
1034:
1031:
1008:
979:
942:
912:
841:
750:
741:
687:
685:
674:
668:
662:
656:
651:
643:
484:
470:
436:Sybil attack
427:
425:
421:Sybil attack
417:permissioned
416:
414:
402:
398:
384:
380:
378:
368:
366:
362:
306:
303:
297:
293:
287:
264:multi-valued
263:
261:
256:
254:
242:single-value
241:
239:
228:
224:
222:
216:
213:transferable
212:
208:
206:
197:
182:
179:running time
178:
176:
171:
169:
164:
159:
157:
90:
86:
78:
28:
18:
4149:19 December
3930:21 December
3877:Ripple Labs
3649:Shi, Elaine
3448:: 123–132.
3059:Lamport, L.
2758:Replication
2191:Synchronous
2127:Synchronous
1891:Synchronous
1816:Synchronous
1711:Synchronous
1602:Synchronous
1484:Synchronous
1234:Synchronous
1128:Synchronous
1023:distributed
987:Nancy Lynch
675:Termination
598:if process
268:Multi-Paxos
172:t-resilient
99:Termination
4369:Categories
4289:(6): 858.
4090:1806.07583
4068:28 October
4028:1904.09630
3997:2020-10-28
3952:2008.05300
3890:2023-07-03
3854:2023-09-05
3802:August 28,
3681:2023-07-04
3633:2019-05-28
3455:1701.03430
3442:Automatica
3354:2008-02-06
3308:2014-10-28
3179:2007-07-25
3113:2015-08-29
2991:(3): 668.
2889:2020-10-28
2847:2017-11-13
2739:2019-05-28
2640:References
2274:blockchain
2247:(expected)
2194:Signatures
2087:(expected)
1956:(expected)
1881:(expected)
1415:(expected)
404:Randomized
282:See also:
69:blockchain
4291:CiteSeerX
4233:CiteSeerX
3879:(Draft).
3421:: 23–29.
3378:CiteSeerX
3144:CiteSeerX
3078:CiteSeerX
2961:ignored (
2951:cite book
2919:CiteSeerX
2834:207660233
2602:∞
2566:∞
2529:−
2419:Consensus
2068:
1959:Requires
1888:Katz-Koo
1577:
1418:expected
1114:Threshold
1108:Synchrony
893:≤
657:Agreement
648:Consensus
536:−
311:Integrity
160:integrity
151:Agreement
105:Integrity
93:processes
29:consensus
4212:22 April
4203:Archived
4140:Archived
4059:Archived
3924:Archived
3881:Archived
3848:Archived
3822:Archived
3796:Archived
3741:Archived
3708:Archived
3672:Archived
3624:Archived
3513:38215511
3400:11287513
3299:Archived
3261:: 3–19.
3196:(2004).
3170:Archived
3104:Archived
3100:55899582
3038:21 April
2883:Archived
2838:Archived
2803:(1985).
2733:Archived
2618:See also
2424:Objects
2290:Ethereum
438:threat.
250:metadata
165:validity
49:PageRank
4313:5797174
4265:9313205
4199:3179361
4136:2181446
3750:May 28,
3717:July 4,
3480:7467466
3460:Bibcode
3275:6102847
3166:6429068
3007:1574706
2915:300–314
2411:Herlihy
2262:Bitcoin
2130:Written
1894:Written
1714:Written
1605:Written
1340:Ben-Or
1237:Written
911:in the
440:Bitcoin
334:, then
217:message
4350:
4311:
4293:
4263:
4253:
4235:
4197:
4187:
4134:
3988:
3511:
3478:
3398:
3380:
3273:
3237:
3204:
3164:
3146:
3098:
3080:
3005:
2939:
2921:
2832:
2772:
2669:
2451:atomic
2421:number
2302:staked
2282:miners
1963:(PKI)
1120:Notes
1117:Rounds
1105:Source
1082:master
1074:Chubby
1045:> 4
989:, and
459:, and
369:rounds
35:, and
4309:S2CID
4261:S2CID
4206:(PDF)
4195:S2CID
4169:(PDF)
4143:(PDF)
4132:S2CID
4112:(PDF)
4085:arXiv
4062:(PDF)
4055:(PDF)
4023:arXiv
3947:arXiv
3884:(PDF)
3873:(PDF)
3767:arXiv
3744:(PDF)
3737:(PDF)
3711:(PDF)
3700:(PDF)
3675:(PDF)
3656:(PDF)
3627:(PDF)
3616:(PDF)
3509:S2CID
3476:S2CID
3450:arXiv
3396:S2CID
3348:(PDF)
3329:(PDF)
3302:(PDF)
3295:(PDF)
3271:S2CID
3257:. 2.
3173:(PDF)
3162:S2CID
3132:(PDF)
3107:(PDF)
3096:S2CID
3066:(PDF)
3032:(PDF)
3025:(PDF)
3003:S2CID
2841:(PDF)
2830:S2CID
2808:(PDF)
2502:stack
2498:queue
2458:mutex
2298:stake
2264:uses
1968:PBFT
1057:/2 +
1011:Paxos
755:, if
246:Paxos
4348:ISBN
4251:ISBN
4214:2021
4185:ISBN
4151:2011
4070:2020
3986:ISBN
3932:2020
3830:2023
3804:2019
3752:2019
3719:2023
3235:ISBN
3202:ISBN
3040:2014
2963:help
2937:ISBN
2770:ISBN
2667:ISBN
2554:...
2511:...
2490:swap
2365:The
2207:>
2143:>
2032:>
2019:Oral
1989:>
1976:Oral
1907:>
1832:>
1819:Oral
1727:>
1618:>
1500:>
1487:Oral
1458:<
1359:>
1346:Oral
1250:>
1144:>
1131:Oral
1025:and
1019:Raft
1009:The
775:<
686:For
448:hash
292:. A
272:Raft
270:and
227:and
181:and
23:and
4356:doi
4332:doi
4301:doi
4243:doi
4177:doi
4124:doi
4033:doi
3978:doi
3916:doi
3792:Vox
3664:doi
3592:doi
3569:doi
3540:doi
3499:doi
3468:doi
3423:doi
3388:doi
3337:doi
3263:doi
3227:doi
3154:doi
3088:doi
2993:doi
2929:doi
2875:doi
2822:doi
2762:doi
2702:doi
2551:...
2508:...
2500:or
2276:or
2065:log
1574:log
525:to
262:In
4371::
4346:.
4328:29
4326:.
4307:.
4299:.
4287:46
4285:.
4259:.
4249:.
4241:.
4201:.
4193:.
4183:.
4171:.
4138:.
4130:.
4120:11
4118:.
4114:.
4099:^
4057:.
4031:.
4021:.
4017:.
3984:.
3972:.
3922:.
3914:.
3910:.
3875:.
3846:.
3794:.
3790:.
3702:.
3670:.
3658:.
3622:.
3618:.
3565:26
3563:.
3536:52
3534:.
3530:.
3507:.
3474:.
3466:.
3458:.
3446:81
3444:.
3419:79
3417:.
3394:.
3386:.
3374:31
3372:.
3269:.
3259:26
3233:,
3168:.
3160:.
3152:.
3140:27
3138:.
3134:.
3102:.
3094:.
3086:.
3072:.
3068:.
3048:^
3001:.
2989:30
2987:.
2983:.
2971:^
2955::
2953:}}
2949:{{
2935:.
2927:.
2917:.
2909:.
2881:.
2871:14
2869:.
2865:.
2836:.
2828:.
2818:32
2816:.
2810:.
2799:;
2795:;
2784:^
2768:.
2748:^
2731:.
2729:10
2727:.
2723:.
2698:12
2696:.
2680:^
2647:^
2583:,
2492:,
2488:,
2456:,
2333:,
2280:,
985:,
977:.
463:.
455:,
426:A
174:.
67:,
59:,
55:,
47:,
43:,
4358::
4338:.
4334::
4315:.
4303::
4267:.
4245::
4216:.
4179::
4153:.
4126::
4093:.
4087::
4072:.
4039:.
4035::
4025::
4000:.
3980::
3955:.
3949::
3934:.
3918::
3893:.
3857:.
3832:.
3806:.
3775:.
3769::
3754:.
3721:.
3684:.
3666::
3636:.
3600:.
3594::
3575:.
3571::
3548:.
3542::
3515:.
3501::
3482:.
3470::
3462::
3452::
3429:.
3425::
3402:.
3390::
3357:.
3339::
3311:.
3277:.
3265::
3229::
3210:.
3182:.
3156::
3116:.
3090::
3074:4
3042:.
3009:.
2995::
2965:)
2945:.
2931::
2892:.
2877::
2850:.
2824::
2778:.
2764::
2742:.
2708:.
2704::
2532:2
2526:n
2523:2
2471:2
2436:1
2397:n
2377:n
2234:9
2213:f
2210:3
2204:n
2170:8
2149:f
2146:2
2140:n
2107:)
2104:n
2101:(
2098:O
2074:)
2071:n
2062:(
2059:O
2038:f
2035:3
2029:n
1995:f
1992:3
1986:n
1943:)
1940:1
1937:(
1934:O
1913:f
1910:2
1904:n
1868:)
1865:1
1862:(
1859:O
1838:f
1835:3
1829:n
1797:)
1794:f
1791:n
1788:(
1785:O
1763:2
1760:+
1757:f
1736:1
1733:+
1730:f
1724:n
1692:)
1687:2
1683:n
1679:(
1676:O
1654:1
1651:+
1648:f
1627:1
1624:+
1621:f
1615:n
1583:)
1580:f
1569:3
1565:f
1561:(
1558:O
1536:3
1533:+
1530:f
1527:2
1506:f
1503:3
1497:n
1463:n
1455:f
1435:)
1432:1
1429:(
1426:O
1402:)
1397:n
1393:2
1389:(
1386:O
1365:f
1362:5
1356:n
1324:)
1319:f
1315:n
1311:(
1308:O
1286:1
1283:+
1280:f
1259:1
1256:+
1253:f
1247:n
1215:)
1210:f
1206:n
1202:(
1199:O
1177:1
1174:+
1171:f
1150:f
1147:3
1141:n
1063:f
1059:f
1055:n
1051:f
1047:f
1043:n
1039:f
1035:n
965:1
962:+
959:f
956:=
953:n
929:3
926:=
923:n
899:f
896:3
890:n
870:f
850:n
827:n
807:t
784:3
781:1
769:n
766:t
723:v
703:v
688:n
626:v
606:0
582:v
562:0
542:,
539:1
533:n
513:0
493:n
342:v
322:v
148:.
136:v
116:v
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.