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♣,
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.