Why Impossibility Proofs Matter in Distributed Systems
Kyle Kingsbury highlights a striking observation from Nancy Lynch's classic paper, A Hundred Impossibility Proofs for Distributed Computing: at first glance, impossibility results seem useless because they don't enable computers to perform any new tasks. Yet, as Lynch argues, their value is significant.
The most obvious benefit is that an impossibility proof tells you precisely when to stop trying to design or optimize an algorithm. This guidance is valuable both for theoretical research and for practical systems engineering.
Of course, real-world developers often persist in pursuit of an impossible goal. Lynch suggests this isn't necessarily stubbornness—it's flexibility. If perfect guarantees can't be achieved, perhaps a solution that works with "sufficiently high probability" is acceptable. In such cases, the real impact of the impossibility result is to force developers to sharpen their claims about what their system actually accomplishes, replacing vague ambitions with precise, achievable specifications.
