On FLP Impossibility

FLP impossibility is one of those results that everyone talks about, but many people don’t really understand. Presented in a short, yet hugely influential 9 page paper, it relates a consensus algorithm’s safety and liveness properties to the network of computers trying to achieve consensus.

The fundamental question proposed by the FLP paper is this:

In a fully asynchronous system, is there a deterministic consensus algorithm that can be safe, live, and fault tolerant?

Intuitively, it seems like the answer to this should be yes. I mean, if just one of the computers is faulty out of thousands, surely there’s a way to get consensus despite this one rogue node? Since the result has “impossibility” in the name, you may be unsurprised to hear the answer is a resounding “No.”

All this means is that you can’t have all of asynchrony, safety, liveness, and fault tolerance. So, if you want to stay on an asynchronous network, you might be able to make a safe and live algorithm, but you wouldn’t be able to tolerate faults. Or if you want fault tolerance, you will have to sacrifice at least one of safety, liveness, and full asynchrony.

Since on the blockchain safety, liveness, and fault tolerance are non-negotiable, the key for us blockchainers is the “fully asynchronous system” part of the FLP statement. In the blockchain context, FLP impossibility says that you can’t have a blockchain without some serious restrictions on the network model. This network model, sometimes called a network formalization, is a concrete mathematical model that tells you exactly how the computers in consensus communicate, how quickly they can send messages, how reliably their messages will arrive, and so forth.

With this in mind…

FLP impossibility DOES NOT say:

• We can only have either safety or liveness, but not both. We can have both, and Casanova demonstrates this.
• Consensus is impossible in general.

FLP impossibility DOES say:

• That we can’t have safety, liveness, full asynchrony, and fault tolerance all at the same time.

Many consensus algorithms, including Casanova, have shown that with some minimal network assumptions you can have all three of safety, liveness, and fault tolerance. Often, these assumptions are minimal and reasonable conditions. The assumption we used in Casanova, called partial synchrony, only assumes that messages get delivered within some bounded time ∆. In practice, if you design your network well, you can not only measure ∆ but you can optimize it to speed up consensus.

Algorithms like Casanova that use such minimal and reasonable network assumptions show that FLP impossibility is not nearly as restrictive as it sounds. Consensus is possible on a distributed system. In particular, it’s possible to have safety, liveness, and fault tolerance on a blockchain.