Lecture
Consensus is generally understood as the process by which a group of individuals reaches a single decision, achieving agreement on some question. In doing so, no formal vote is held — the decision is taken on the basis that a majority of participants raise no objection. It should be noted that the term “consensus” refers not only to the decision-making process itself, but also to the decision actually reached as a result of that procedure, that is, to the outcome.
A fundamental problem in distributed computing and multi-agent systems is achieving overall system reliability in the presence of a number of faulty processes. This often requires coordinating processes to reach consensus, or to agree on some data value that is needed during computation. Examples of applications of consensus include agreeing on which transactions to commit to a database and in what order, state machine replication, and atomic broadcasts. Real-world applications that often require consensus include cloud computing, clock synchronization, PageRank, opinion formation, smart grids, state estimation, drone control (and control of multiple robots/agents in general), load balancing, blockchain, and others.
The consensus problem requires agreement among several processes (or agents) on a single data value. Some processes (agents) may fail or be unreliable for other reasons, so consensus protocols must be fault-tolerant or resilient to failures. Processes must somehow propose their candidate values, communicate with each other, and agree on a single consensus value.
The consensus problem is a fundamental problem in the control of multi-agent systems. One approach to achieving consensus is for all processes (agents) to reach agreement on the value held by the majority. In this context, a majority requires at least half of the available votes (where each process is given one vote). However, one or more faulty processes may distort the resulting outcome, such that consensus cannot be reached, or is reached incorrectly.
Protocols that solve consensus problems are designed to handle a limited number of faulty processes. For these protocols to be useful, they must satisfy a number of requirements. For example, in a trivial protocol all processes could simply output the binary value 1. This is useless, and so the requirement is changed so that the output must somehow 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 on an output value only once, and this decision cannot be reversed. A process is called correct during an execution if it does not fail. A consensus protocol tolerating stopping failures must satisfy the following properties.
termination
Eventually, every correct process decides on some value.
integrity
If all correct processes proposed the same value 
, then any correct process must decide .
agreement
Every correct process must agree on the same value.
Depending on the application, various variants of the definition of integrity may be required. For example, a weaker type of integrity would be that the decision value equals a value proposed by some correct process, not necessarily by all of them. Integrity condition is also known in the literature as validity.
A protocol that can correctly guarantee consensus among n processes, of which at most t fail, is called t-resilient.
When evaluating the performance of consensus protocols, two factors are of interest: running time and message complexity. Running time is given in Big O notation as the number of rounds of message exchange, as a function of some input parameters (usually the number of processes and/or the size of the input domain). Message complexity refers to the volume of message traffic generated by the protocol. Other factors may include memory usage and message size.
Different computation models can define the “consensus problem”. Some models may deal with fully connected graphs, while others deal with rings and trees. In some models message authentication is allowed, whereas in others processes are fully anonymous. Shared-memory models, in which processes interact by accessing objects in shared memory, are also an important area of research.
In most communication protocol models, participants communicate over authenticated channels. This means that messages are not anonymous, and recipients know the source of every message they receive. Some models assume a stronger, transferable form of authentication, in which each message is signed by its sender, so that the recipient knows not only the immediate source of each message, but also the participant who originally created the message. This stricter type of authentication is achieved using digital signatures, and when this stronger form of authentication is available, protocols can tolerate a larger number of faults.
Two different authentication models are often called the oral and written communication models. In the oral communication model, only the immediate source of information is known, whereas in the stronger, written communication models, each step along the recipient’s path learns not only the immediate source of the message but also the message’s communication history.
In most consensus protocol models, participants communicate over authenticated channels. This means that a message is not anonymous, and recipients know the source of every message they receive. Some models provide for a stronger form of authentication, in which each message is signed by its sender, so that the recipient knows not only the immediate source of each message, but also the participant who wrote the message. This stricter type of authentication is achieved using digital signatures, and when this form of authentication is available, protocols can tolerate more faults.
Two different authentication models are often called the oral and written models of communication. In the oral model of communication, only the immediate source of information is known, whereas in written models of communication, each step along the path to the recipient learns not only the immediate source of the message but also the communication history.
There are two types of failures that can occur in a process: a crash failure or a Byzantine failure. A crash occurs when a process suddenly halts and cannot be restarted. A Byzantine failure is a failure in which absolutely no conditions are imposed. For example, they can arise as a result of malicious actions by an adversary.
Let us consider the Byzantine Generals Problem in detail.
Byzantine consensus is a general definition of the problem of interaction among several participants of a network located remotely and receiving a task from a center. Moreover, some of the network participants, including the center itself, may turn out to be attackers. In other words, a Byzantine protocol algorithm must ensure communication among remote network participants while excluding fraudulent operations, that is, ensure transaction security.
The idea of Byzantine consensus emerged in the 1980s. Its essence is as follows. It is the eve of a battle for Byzantium. The Byzantine army consists, for example, of 4 legions, located at a distance from one another. At a certain time, each of the legion generals receives an order from the command center to attack or retreat. The development of events is as follows:
The task is clear, but what is the guarantee that there are no traitors among the generals who will carry out the order in reverse? And what is the guarantee that the commander-in-chief himself will not turn out to be a traitor, sending different orders to different generals? Conclusion: the generals must exchange information with one another, excluding erroneous data. More precisely, they must exchange information about the size of the legions loyal to Byzantium, and draw conclusions about the number of traitor legions. The task assumes that out of N generals, N-1 could turn out to be traitors.
The principle of agreement is that all loyal generals, as a result of exchanging information, arrive at the same decision, ignoring the data from the traitor general. Let us return to the example. The principle of information exchange is as follows:
And logically, for three of the generals the figures will be the same in all three blocks, and only for one will there be discrepancies.
Thus, the loyal generals arrive at agreement, excluding the traitor’s opinion. The example is simplified, but it clearly shows how network participants arrive at a single decision, excluding false ones.
The consensus problem can be considered in asynchronous or synchronous systems. Although real-world communication is often asynchronous in nature, modeling synchronous systems is more practical and often simpler, given that asynchronous systems are naturally associated with more problems than synchronous ones.
In synchronous systems, it is assumed that all communication takes place within a session. In a single session a process can send all the messages it needs, while receiving all messages from other processes. Thus, no message from one session can affect messages sent in that same session.
In a fully asynchronous system, there is no single solution that can tolerate even one failure, even if only the property of nontriviality is required. This result is sometimes called the FLP impossibility proof, named after its authors Michael J. Fischer [en], Nancy Lynch, and Mike Paterson [en], who received the Dijkstra Prize for this significant work. The FLP result does not say that consensus can never be achieved: only that, under the assumptions of the model, no algorithm can always achieve consensus within a bounded time.
In the most traditional single-value consensus protocols, such as Paxos, interacting nodes agree on a single value, such as an integer, which may be of variable size to encode useful metadata, such as a transaction committed to a database.
A special case of the single-value consensus problem, called binary consensus, restricts the input, and hence the output domain, to a single binary digit {0,1}. Although binary consensus protocols are not very useful by themselves, they are often used as building blocks in more general consensus protocols, especially for asynchronous consensus.
In multi-valued consensus protocols, such as Multi-Paxos and Raft, the goal is to agree not on just a single value, but on a series of values over time, forming a gradually growing history. Although multi-valued consensus can be achieved naively by running several iterations of a single-value consensus protocol in a row, many optimizations and other considerations, such as support for reconfiguration, can make multi-valued consensus protocols more efficient in practice.
There are two types of failures a process may suffer: a crash failure or a Byzantine failure. A crash failure occurs when a process abruptly stops and does not resume. Byzantine failures are failures on which absolutely no conditions are imposed. For example, they can arise as a result of malicious actions by an attacker. A process that has suffered a Byzantine failure can send inconsistent or contradictory data to other processes, or it can go to sleep and then resume operation after a long delay. Of the two types of failures, Byzantine failures are far more destructive.
Accordingly, a consensus protocol that tolerates Byzantine failures must be resilient to all possible faults that can occur.
A stronger version of consensus that tolerates Byzantine failures is given by strengthening the integrity constraint:
Honesty
If a correct process decides , then must have been proposed by some correct process.
The consensus problem can be considered in the case of asynchronous or synchronous systems. Although real-world data exchange is often asynchronous in nature, it is more practical and often simpler to model synchronous systems , given that asynchronous systems are naturally associated with more problems than synchronous ones.
In synchronous systems, it is assumed that all communication takes place in rounds. In a single round, a process can send all the messages required, while simultaneously receiving all messages from other processes. Thus, no message from one round can affect messages sent in the same round.
In a fully asynchronous message-passing distributed system, in which at least one process may experience a crash failure, the famous FLP impossibility result proved that a deterministic algorithm for achieving consensus is impossible. This impossibility result arises from worst-case scheduling scenarios that are unlikely in practice, except in adversarial situations such as an intelligent denial-of-service attacker on the network. In most ordinary situations, process scheduling has a degree of natural randomness.
In the asynchronous model, some types of failures can be handled by a synchronous consensus protocol. For example, the loss of a communication channel can be modeled as a process that has suffered a Byzantine failure.
Randomized 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 on the network.
Consensus algorithms traditionally assume that the set of participating nodes is fixed and given from the outset: that is, some prior (manual or automatic) setup process has permissioned a specific 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 Sybil attack on an open consensus group can defeat even a Byzantine consensus algorithm, simply by creating enough virtual participants to overcome the fault-tolerance threshold.
A permissionless consensus protocol, by contrast, allows anyone on the network to join dynamically and participate without prior permission, but instead introduces some other form of artificial cost or barrier to entry to mitigate the Sybil attack threat. Bitcoin introduced the first permissionless consensus protocol, based on cryptographic proof of work, in which participants compete to solve cryptographic hash puzzles, and with some probability earn the right to commit blocks and earn associated rewards proportional to the computational effort expended. Partly motivated by the high energy cost of this approach, subsequent permissionless consensus protocols have proposed or adopted other alternative participation rules to defend against Sybil attacks, such as proof of stake, proof of space, and proof of authority.
The consensus problems of interest are as follows.
A collection of n processes, numbered from 0 to n-1, send messages to each other. Process 0 must broadcast a value to all processes such that:
Formal requirements for an agreement protocol may include:
agreement
All processes must agree on the same value.
weak validity
For each correct process, its output must be the input of some correct process.
strong validity
If all processes receive the same value, then they must all output that value.
termination
All processes must decide on an initial value.
For n processes in a partially synchronous system (the system cycles through good and bad periods of synchronization), each process chooses a private value. Processes exchange data with each other in a session to determine a common value and build a consensus vector with the following requirements:
There exists a t-resilient anonymous synchronous protocol that solves the Byzantine Generals problem, [10] [11] , if
and the weak Byzantine generals case , where
is the number of failures and 
is the number of processes.
For systems with processors, of which 
are Byzantine, it has been shown that there is no algorithm that solves the consensus problem for 
in the oral messages model. [12] The proof is constructed by first showing impossibility for the case of three nodes
and using this result to argue about partitions of processors. In the written messages model there are protocols that can
.
In a fully asynchronous system there is no consensus solution that can withstand one or more failures, even if only the property of non-triviality is required. This result is sometimes called the FLP impossibility proof, after its authors Michael J. Fischer, Nancy Lynch and Michael Paterson, who received the Dijkstra Prize for this important work. The FLP result has been mechanically verified for conformance, even under the fairness assumption. [13] However, FLP does not claim that consensus can never be reached: it simply states that, under the model's assumptions, no algorithm can always reach consensus in bounded time. In practice, this is unlikely.
Other protocols used by cryptocurrencies include proof of importance, proof of location, proof of activity, proof of elapsed time. All of these are regarded as an alternative to proof of work, again because of the abundance of computing power the latter requires.
Many real-time strategy games use a modified Lockstep [en] protocol as a consensus protocol to manage game state among players. As a result of each in-game action, a delta of the game state broadcast is sent to all other players, along with a hash of the shared game state. Each player confirms the change by applying the delta to its own game state and comparing game state hashes. If the hashes do not agree, a vote is held, and those players whose game state is in the minority are disconnected and removed from the game (known as desynchronization).
Another well-known approach is called MSR-type algorithms, which are widely used from computer science to control theory.
The Paxos consensus algorithm of Lamport, and its variants such as Raft, are pervasively used in widely deployed distributed and cloud computing systems. These algorithms are typically synchronous, depend on an elected leader to make progress, and tolerate only crash failures, not Byzantine failures.
An example of a polynomial-time binary consensus protocol that tolerates Byzantine failures is the Phase King algorithm [14] by Garay and Berman. The algorithm solves the consensus problem in the synchronous message-passing model with n processes and up to f failures, when n > 4 f . The Phase King algorithm has f+ 1 phases, with 2 rounds per phase. Each process tracks its preferred output (initially equal to the process's own input value). In the first round of each phase, each process broadcasts its preferred value to all other processes. It then receives 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 identifier matches the number of the current phase is assigned as the phase king. The king broadcasts the majority value it observed in the first round, and serves as the tiebreaker. Each process then updates its preferred value as follows. If the count of the majority value a process observed in the first round is greater than n / 2 + f, the process changes its preference to that majority value; otherwise it uses the phase king's value. At the end of phase f + 1, the processes output their preferred values.
Google implemented a distributed lock service library called Chubby . [15] Chubby stores lock information in small files, which are stored in a replicated database in order to provide high availability in the event of failures. The database is implemented on top of a fault-tolerant log layer based on the Paxos consensus algorithm. In this scheme, Chubby clients communicate with the Paxos master to access / update the replicated log; i.e. to read / write files. [16]
Many peer-to-peer online real-time strategy games use a modified Lockstep protocol as a consensus protocol to manage game state among players in the game. Each in-game action results in a broadcast of the game state delta to all other players in the game, along with a hash of the shared game state. Each player confirms the change by applying the delta to its own game state and comparing game state hashes. If the hash codes do not match, a vote is held, and those players whose game state is in the minority are disconnected and removed from the game (this is called desynchronization).
Another well-known approach, called MSR-type algorithms, is widely used from computer science to control theory.
| Source | Synchrony | Authentication | Threshold | Rounds | Notes |
|---|---|---|---|---|---|
| Pease-Shostak-Lamport | Synchronous | Oral |  |
 |
full communication  |
| Pease-Shostak-Lamport | Synchronous | Written |  |
|
full communication |
| Ben-Or | Asynchronous | Oral |  |
 (expected) |
expected  rounds, when  |
| Dolev et al. [21] | Synchronous | Oral | |
 |
full communication  |
| Dolev-Strong | Synchronous | Written | |
|
full communication  |
| Dolev-Strong | Synchronous | Written | |
 |
full communication  |
| Feldman-Micali | Synchronous | Oral | |
(expected) |
|
| Katz-Koo | Synchronous | Written |  |
(expected) |
PKI required |
| PBFT [24] | Asynchronous (safety) - Synchronous (liveness) | Oral | |
||
| HoneyBadger [25] | Asynchronous | Oral | |
 (expected) |
for data transmission  - requires public-key encryption |
| Abraham et al. [26] | Synchronous | Written | |
 |
|
| Byzantine agreement made trivial | Synchronous | Signatures | |
 (expected) |
Digital signature required |
| Name | principle | performance | finality |
|---|---|---|---|
| Proof-of-Work (PoW) | Difficult to find a solution, but easy to verify the result. | low | probabilistic |
| Proof-of-Stake (PoS) | The network trusts a validator who stakes their own resources as collateral for the opportunity to create blocks: the larger the stake, the higher the probability the network will allow the block to be created. | high | probabilistic |
| Delegated Proof-of-Stake (DPoS) | Participants delegate the production of new blocks to a small, fixed number of elected validators. High competition, but very profitable. | high | probabilistic |
| Proof-of-Activity (PoA) | A hybrid of PoW and PoS. | low | probabilistic |
| Proof-of-Location (PoL) | Beacons are used to detect a node in a synchronous state, then timestamp its presence. | medium | immediate |
| Proof-of-Importance (PoI) | Like PoS, but with additional properties that affect your rating. | high | probabilistic |
| Proof-of-Elapsed-Time (PoET) | Blocks are created in an environment with equal periods. | medium | probabilistic |
proof of work (Proof-of-Work, PoW ), typical case: bitcoin network credits
proof of stake (Proof-of-Stake, PoS , also translated as proof of ownership), typical case: Ethereum
Delegated-Proof-of-Stake (DPoS), typical case: EOS
Typical case of Proof-of-space (Proof-of-space, PoSpace, also known as Proof-of-Capacity, PoC): Filecoin
Paxos
Bitcoin uses proof of work to achieve permissionless consensus in its open peer-to-peer network. To extend the Bitcoin blockchain or distributed ledger, miners attempt to solve a cryptographic puzzle, in which the 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 its proposed version of the next block of transactions added to the ledger and eventually accepted by all other nodes. Since any node in the network can attempt to solve the proof-of-work problem, a Sybil attack is in principle impossible unless the attacker controls more than 50% of the network's computational resources.
Other cryptocurrencies (i.e. DASH, NEO, Stratis, ...) use proof of stake, in which nodes compete to add blocks and receive rewards proportional to the share of the existing cryptocurrency allocated and locked, or staked, for some period of time. One of the advantages of the “proof of stake” system over the “proof of work” system is the high energy consumption required by the latter, at least with current technology. For example, bitcoin mining (2018) is estimated to consume non-renewable energy resources in an amount comparable to entire countries such as the Czech Republic or Jordan. [29]
Some cryptocurrencies, such as Ripple, use a node validation system to verify the ledger. This system, used by Ripple, called the Ripple Protocol Consensus Algorithm (RPCA), works in stages: Step 1: each server compiles a list of valid candidate transactions; Step 2: each server combines all candidates from its unique node list (UNL) and votes on their validity; Step 3: transactions that pass the minimum threshold move to the next round; Step 4: the final round requires 80% agreement [30]
Other participation rules used in permissionless consensus protocols to impose barriers to entry and resist Sybil attacks include proof of authority, proof of space, proof of burn, or proof of elapsed time. These alternatives are again largely motivated by the large amount of computing power consumed by proof of work. [31] Proof of capacity is used by crypto coins such as Burstcoin.
In contrast to the permissionless participation rules above, each of which rewards participants proportionally to the amount invested in some action or resource, proof-of-personhood protocols aim to give each real human participant exactly one unit of voting power in permissionless consensus, regardless of economic investment. [32] [33] Proposed approaches for achieving individual distribution of consensus power for proof of personhood include physical pseudonyms, [34] social networks, [35] pseudonymized government-issued identities, [36] and biometrics. [37]
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 that helps concurrent processes interact to reach agreement.
There are two main methods for creating such a concurrent object. Traditionally, designers use a critical section to solve this problem, meaning that only one process is allowed to visit the concurrent object at a time, while others must wait until that process exits the critical section. This method is simple and easy to implement. However, systems with critical sections face the risk of failure if some process dies inside the critical section or stalls for an unacceptably long time.
Another implementation of a concurrent object is called a wait-free implementation, which can guarantee consensus in a finite number of steps. Is an object of a given type powerful enough to solve consensus problems? Maurice Herlihy gave a “hierarchy of impossibility and universality”. [38]
| Consensus number | Objects |
|---|---|
 |
Read/write registers |
 |
test-and-set, swap, fetch-and-add, queue, stack |
| ... | ... |
 |
n-register assignment |
| ... | ... |
 |
memory-to-memory move and swap, augmented queue, compare-and-swap, fetch-and-cons, sticky byte |
The consensus number in the hierarchy denotes the maximum number of processes in a system that can reach consensus on a given object. Objects with a higher consensus number cannot be implemented by objects with a lower consensus number.
According to the hierarchy, read/write registers cannot achieve consensus even in a two-process system. A data structure such as a stack, queue, etc., can provide consensus between two processes. Why can these objects not achieve consensus among a larger number of processes? An effective way to prove this is to take advantage of bivalency. Suppose the output is binary; a state is bivalent if both of the two outputs are possible, and if the output reachable from a state is only 0/1, the state is called 0-valent / 1-valent. The basic idea is to create a contradiction by performing some operations to obtain a state that is simultaneously 0-valent and 1-valent.
However, some concurrent objects are universal, meaning that they can achieve consensus among any number of processes and can simulate any other objects. The way to simulate other objects using universal objects is to construct a sequence of operations with that concurrent object. [38]
Comments