The FLP Theorem has been famously covered by the paper-trail blog post. It still makes sense to do a TL;DR of it though.

Distributed systems usually record values, be that storing values or processing events. To get a distributed system to agree to a value (or that a message was received), one would use a consensus algorithm. The catch is that consensus algorithms are synchronous and can slow down your system.

This, in the past, has opened a discussion on whether it is possible to have consensus in an asynchronous setting. The FLP Impossibility Theorem, described in the paper titled “The Impossibility of Consensus with One Faulty Process”, proves that it isn’t possible to achieve consensus asynchronously.

Impossibility is proven by demonstrating that there is a state that the distributed system can be in, which it will never be able to transition out of.

The first argument is demonstrated by looking at all possible end results of your system, finding a result where a single change would cause a different outcome, and stipulating that if there were an error (as there is assumed to be one) in such a configuration, then the outcome is non-determinstic.

The second argument lies in the thought that since messages can arrive unordered and late, there exists a configuration where the outcome is ultimately determined by the result of a single node. Given that this node’s message can be late or not, it would cause any algorithm to be bivalent or non-deterministic.

I have simplified the arguemnts above, they are actually more different from eachother in the details. I highly encourage readers to have a look the brief tour of FLP linked above to better understand the reasoning.