In distributed computing, the overall system reliability in the presence of a number of faulty processes.

Consensus requires agreement among a number of processes or agents for a single data value. Some of these might fail or be unreliable in other ways, so consensus protocols must be fault tolerant. The processes must put forth their candidate values, communicate with one another, and agree on a single value. 

A consensus protocol tolerating halting failures must satisfy the following properties:

  • Termination: A liveness property in which every correct (non-faulty) process eventually decides some value.

  • Integrity: The ability to recover from the failure of a participating node.

  • Agreement: A safety property, in which every correct process must agree on the same value.

Failures can refer to either a fail-stop, when a process stops communicating or a Byzantine fault, where a process send faulty or malicious data. The term Byzantine is taken from a simile by Leslie Lamport about a group of generals of the Byzantine army camped with their troops around an enemy city. Communicating only by messenger, the generals must agree upon a common battle plan. However, one or more of them may be traitors who will try to confuse the others. An algorithm resilient to such failures is called Byzantine fault-tolerant.

In the case of cryptocurrencies such as Bitcoin, nodes in the network must agree upon a common order of transactions. They do so by timestamping transactions into blocks, which are hashed and linked into a chain. Miners produce computational work into finding nonce which would produce a block hash under a certain size, called the target. If the block is valid under the protocol rules, nodes accept the block as canonical, reaching a consensus. 

In the case that multiple blocks are valid, the longest chain –carrying the most proof-of-work– is accepted as canonical. This is the essence of Nakamoto consensus.