indefinitely—an unlikely outcome with random faults, but a fact of life with hostile security faults.

Computers used to have paid staff watching them. Software was small enough to debug credibly. Computing needs changed slowly. Leaving reliability to hardware worked well. The world has changed: In the hurly-burly of networked consumer computing, the more CEO Software we add to a system, the more breakable it gets. Today’s crashed machines may be just canaries in the coal mine.

To see how robustness and efficiency can trade off, consider sorting a list by comparing pairs of items. This is considered a solved problem in computer science, with solid theory and many efficient algorithms. “Quick sort” and “merge sort” are particularly widely used. When sorting a long list, either one blows the doors off “bubble sort,” which basically makes many passes over the list and swaps adjacent items if they compare out of order. Computer scientists love to hate bubble sort, because it is inefficient but easy to reinvent. It keeps popping up in software like a weed.

Efficient sorting algorithms make comparisons that often move items long distances. Bubble sort does not do that. It compares items repeatedly. It only moves items one position at a time. Bubble sorting a billion items would involve a billion billion comparisons and take years. Quick sorting a billion items took under 10 minutes on my laptop: It is an efficient algorithm for big tasks.

Yet some tasks are small, like sorting my shopping list by price. Even inefficient bubble sort will do that in the blink of an eye. Is it always best to do even small jobs as fast as possible? Maybe not.

As a demonstration, imagine sort-
ing just 52 items, like a shuffled deck
of cards. I used1 stock implementa-
tions of quick and merge sorts, and
hand-coded a totally unoptimized
bubble sort. Each algorithm picks
pairs of cards to compare, and passes
them to a ‘card comparison compo-
nent’ to determine their order.

Here’s the twist: Imagine that component is unreliable. Maybe malware corrupted it. Maybe sunspots cooked it. We don’t know why. For this demonstration, the card comparison component usually works fine, but on 10% of comparisons it gives a random answer. It might claim 3♠ > 7♢ , or Q♥ = 9♣, or whatever.

Given such faults, a sorting algorithm’s output might well be incorrect. I scored the output error by adding up each card’s distance from its proper position—ranging from 0, for the correct deck order, up to 1,352 (that is, 522/2), for worst cases like getting the whole deck backward.

Averaged over 1,000 shuffled decks, the errors made by each sorting algorithm are shown in Figure 2.

Now whose doors have fallen off? Bubble sort’s inefficient repeated comparisons repair many faults, and its inefficient short moves minimize the damage of the rest.

 

figure 1. Crashed computers are a common sight.

P h o t o g r a P h s b y D e e P a k s a r D a , C l I V e D a r r a , l a s e r b u r n e r s