Comment by tzs | Hacker News Reader

Comment by tzs | Hacker News Reader

Parent Full thread

Those "have N copies and compare them" systems then have the issue that whatever does the comparison is a single point of failure. You could use multiple comparison units and have a second level comparison check them, but then that is your single point of failure, and so on.

I've been told, but never actually looked it up, that there is a theorem that proves you always have to have at least one single point of failure.

I don't know if the following is actually true, or just a rumor, but I've heard that at least one aircraft whose mission called for very high reliability didn't have a comparison unit: the redundancy extended all the way to having the 3 independent flight control computers each control a separate actuator on each flight control surface. If one of the systems went bad and tried to move the surface incorrectly, the other two would physically overpower it.

That still has a single point of failure, but now that point is the control surface itself. If your control surface itself has failed it no longer matters if the 3 computers controlling it agree.

> I've been told, but never actually looked it up, that there is a theorem that proves you always have to have at least one single point of failure.

In what context? There's a theorem that arbitrarily-reliable computation can be done with noisy components, as long as the noise is below some threshold (e.g. picture less than 1 error per 10 operations). [1]

1: von Neumann, J. (1956). "Probabilistic Logics and Synthesis of Reliable Organisms from Unreliable Components", in Automata Studies, eds. C. Shannon and J. McCarthy, Princeton University Press, pp. 43–98 http://www.cyclify.com/wiki/images/a/af/Von_Neumann_Probabil...

So long as you can trade off robustness for performance, the fact that there must be a single point of failure is less important. You make the single point of failure more robust. In the example of the control surface, perhaps some ionizing radiation could flip bits in the flight control computers, but it takes a physical collision to damage the control surface.

To argue otherwise is to imply that all designs and all systems are equally robust, which is clearly not true.

This is something I'd always wondered about and never gotten a straight answer to. You're the first person I've seen who explicitly confirmed my suspicion that every system has a single point of failure. Would love to find a reference for this...

I thought the way these things worked is that each of the N computers can see the state of the other N-1 computers; if your local state differs from the majority opinion you overwrite it, thereby joining the majority.

I'm curious if this SPoF theory stops at computer/real world interfaces (such as the control surface <-> computers). Or if this generalizes into purely computational models. In my mind I can't find any purely computational model using distributed techniques that succumbs to the SPoF "theory." But the computer/real world interface is trivially obvious in just about every context.

I don't think it's strictly true that you always have to have a single point of failure. Trivial counterexamples: 6 people carrying a sofa, an ant colony, BitTorrent.

The closest thing I can remember encountering to what you describe is the "Contracrostipunctus" chapter in Douglas Hofstadter's Godel, Escher, Bach, where he writes a dialog featuring record players as an analogy to Godel's Incompleteness Theorem (which only applies to "formal systems" - descriptive mathematical languages). He does go on to explore a real-world example of the principle in the form of viruses - a cell cannot fully defend against DNA modification using only instructions found in its DNA. The same principle applies to cracking copy protection in games - no matter how elaborate the validity checks, there's always a single point of failure in the form of the final decision - "if(checks_pass){run_game()}" - which can be trivially short circuited with a debugger.

I'm not a good enough mathematician to fully understand the limits of Godel's Theorem. But it seems to me that all of the above applications are examples of some sort of well defined formal computational system, and you can't generalize it to "everything has a single point of failure" without some carefully defined rules as to what constitutes the boundaries of system.

http://www.math.yorku.ca/Who/Faculty/Brettler/3500_06/Godels...

Reply on news.ycombinator.com