FLP Impossibility
FLP Impossibility is an academic proof that relates to reaching consensus among distributed nodes when intra-node messaging is asynchronous (i.e. when there is no upper bound on the amount of time a node may take to retrieve, process and respond to incoming messages; when asynchronous, it is impossible for other nodes to tell whether a node has failed, or is simply taking a long time to do its processing).
FLP Impossibility states no deterministic consensus protocol can be found that will guarantee all of ‘termination’, ‘agreement’, ‘validity’ and ‘fault tolerance’ in an asynchronous system. 'termination’ - all non-faulty nodes eventually decide on a value. ‘agreement’ - all nodes that decide on a value, do so on the same value. ‘validity’ - the value that has been decided must have been proposed by some process. ‘fault tolerance’ – the consensus protocol can recover from a failure of a participating node. As ‘fault tolerance’ is considered to be crucial for blockchains, consensus algorithm designers therefore must choose between either ‘termination’ or ‘consistency’ (i.e. ‘consistency’ is ‘agreement’ and ’validity’).
‘Permissionless’ Versus ‘Permissioned’ Blockchains
Blockchains may be categorized as either permissionless or permissioned. Permissionless blockchains are open networks publicly available for use (e.g. Bitcoin and Ethereum). Permissioned blockchains have close-ended participation, and are aimed at consortia. Any client may submit transactions, but only certain validating nodes the nodes in permissioned networks are semi-trusted and have been vetted, registered, and identified. Permissioned networks are usually smaller than permissionless ones.
Given these differences in trust levels and network size, different consensus algorithms will be appropriate for permissionless and for permissioned networks. Some consensus models designed for permissioned networks do not scale well beyond about twenty peering nodes (due to requirements for intra-node messaging) and cannot have any open-ended participation.
Transaction Rate
Choice of consensus algorithm can also be influenced by the expected rate of transactions recorded on the blockchain. Ledgers that are used to record financial transactions often require high transaction rates with relatively few participants and immediate finality of commitment. Consumer markets, on the other hand, require substantial aggregate throughput across many participants, but short-term finality is less important.
‘Double Spend’
In the case of blockchains underlying cryptocurrencies, the focus of consensus algorithm design is usually Byzantine failures (i.e. specifically, malicious attempts to ‘double spend’, perhaps through a Sybil or ‘51%’ attack).