The Independence

Put three engineers in three separate rooms, give each the same specification, and let none of them talk to the others. Each writes a program to do the job. Then run all three at once on every input and let them vote: whatever answer two of them agree on is the one you keep. The appeal is immediate and almost moral. People working alone make different mistakes; a blunder in the first room is unlikely to be copied in the second, still less in the third; so when two of the programs agree, their agreement is unlikely to be a shared error, and the majority is almost surely right. This is N-version programming, proposed at UCLA by Algirdas Avižienis and Liming Chen in the late 1970s, and its promise was reliability bought not by making one program perfect — no one can — but by making several programs independent and letting them correct each other.

The whole promise rides on one word. If the versions fail independently — if a fault in one carries no information about a fault in another — then the arithmetic is overwhelming. A program that goes wrong on one input in a thousand, run in triplicate under a majority vote, produces a wrong majority only when two of the three fail on the very same input; and if their failures are independent, that is roughly a one-in-a-million coincidence, near enough to never. Independence is the multiplier that turns three mediocre programs into one excellent system. Avižienis was careful about this. He called the independence not a fact but "the fundamental conjecture" of the approach, and treated whether it held as a thing to be established by experiment, not assumed.

In the mid-1980s John Knight and Nancy Leveson set out to test it. They had twenty-seven programmers, working independently at two universities, write twenty-seven versions of one program from a single specification — an anti-missile "launch interceptor" that reads radar data and decides whether to fire. The versions were good: individually they returned the right answer on better than nine hundred and ninety-nine inputs out of every thousand, and six of the twenty-seven ran a full million test cases without a single error. Then Knight and Leveson asked the only question that mattered. When the versions failed, did they fail independently — each on its own inputs — or did they fail together, on the same ones?

They failed together. Across a million tests there were more than a thousand inputs on which two or more versions failed at once — hundreds on which three failed, dozens on which five or six went wrong together, a couple on which eight of the twenty-seven failed on the identical input. Under the assumption of independence this should have been vanishingly rare; instead it was ordinary. The statistic they computed to test independence came out above a hundred, where anything past about two would have been enough to reject it with ninety-nine percent confidence. The versions had been written by different people, in different rooms, who never met — and still they made their mistakes in the same places.

It is worth being exact about what this did and did not show, because the result is easy to overstate. Knight and Leveson did not prove that N-version programming does not work, and they said so in as many words: the reliability of a voting system may simply be lower than the independence arithmetic predicts, not that it is nothing. What they refuted was the single load-bearing word. The versions were not independent. And once independence is gone the multiplier is gone with it — you can no longer multiply three thousandths into a billionth and call the system ultra-reliable, because the failures you were counting on to be unrelated are related.

The reason they are related has nothing to do with copying. Independent programmers really do write independent code; what they cannot make independent is the problem. Some inputs are simply harder to get right than others — a boundary case, a coincidence of values, a place where the specification hides a subtlety — and a hard input is hard for everyone. David Eckhardt and Larry Lee captured exactly this in a model. Give each input a "difficulty": the fraction of all possible programmers who would get it wrong. If every input were equally difficult, failures would be independent and the arithmetic would hold. But difficulty is not uniform; it varies across the inputs, and that variation is the correlation. The moment you see one version fail, you have learned something — that the input was probably one of the hard ones — and that makes the next version likelier to fail on it too. The failures move together not because the programs resemble each other but because the hardness is in the problem, and every program, however independently written, is facing the same problem.

And here the correction system meets the one thing it cannot see. A majority vote compares the versions against each other; it never compares them against the truth, because if it could do that it would not need them. So the vote can only catch a failure that stands alone — one version wrong while the others are right, outvoted and overruled. Against a correlated failure it is not merely weak; it is inverted. When a hard input trips two of the three versions the same way, the vote finds its majority — for the wrong answer — and hands it back not flagged but certified. The error does not slip past the checker. It is ratified by it. Agreement, which was supposed to be the signature of correctness, is produced just as readily by a shared mistake, and the voter has no way to tell the two apart.

Engineers have a name for this — common-mode failure, the failure that strikes the redundant channels together because they share a cause — and they know it is what actually kills redundant systems, far more than the random, independent faults the redundancy was built to survive. Its sharpest form is a flaw in the shared specification: every version inherits it, every version implements it faithfully, and every version is therefore wrong in the same way and votes for it in unison. The most expensive demonstration flew on the fourth of June, 1996. The Ariane 5 rocket carried two inertial reference systems for redundancy, running in parallel so that if one failed the other would take over. They ran identical hardware and identical software — code inherited, in the part that mattered, from Ariane 4, where it had been correct. Seconds into the flight, a horizontal-velocity value, building up far faster on the new rocket's trajectory than anything the older one had produced, overflowed a conversion from a 64-bit number into a 16-bit one. The active unit hit the overflow and shut itself down. The backup, running the same code on the same data, had hit the same overflow one data cycle before — it was already dead. There were two units so that one could fail. But they could not fail independently: the redundancy that looked like two was, to a fault they shared, only one. The rocket tore itself apart moments later.

This is the general shape of the thing, and it reaches well past software. A checking system can catch only the errors it does not share; whatever a verifier has in common with the thing it verifies is precisely where it goes blind. A lone checker that shares the fault simply fails to fire, and the error passes unnoticed. But where the check is a comparison among instances — a vote, a second reader, a redundant channel — a shared error is worse than unnoticed: the instances agree, and agreement is read as confirmation. Hand a proof to a second reader who reasons exactly as the first did, and a flaw a stranger would catch at once passes them both, the second reading multiplying confidence without multiplying scrutiny. The shared blind spot never announces itself, because from the inside a correlated error and a correct answer look the same: both produce agreement. This is why the redundancy that matters is redundancy of failure modes, not of instances — three of the same thing are one thing, and the only check that catches a mistake is one built to fail differently from the mistake it is checking. Independence was never a technicality in the arithmetic. It was the whole of what the arithmetic was buying, and it cannot be had by running the same thing twice. Agreement is evidence of truth only to the degree that those who agree could have failed apart; when they cannot, their agreement is worth no more than one of them alone. And when the problem itself makes them fail together, unanimity is not the refutation of error. It is its most convincing disguise.