The Divine Random in Computing

We'll find all its secrets and make them our own;
A yarn to weave and be woven.
We'll choose among the least likely chosen
And build a castle stone by stone.

Alan Turing - Superhero

(Courtesy technewspedia.com)

Hollywood seems enamored these days with the superhero story. Movies about Thor, Spiderman, and Superman, all have basically the same plot. In his youth, our hero discovers a unique ability, a superpower, which he then uses to save the world from an evil arch-villain in violently dramatic fashion. Later, the very people whose lives he spared begin to fear his superpower and persecute him for his eccentricities. The superhero becomes despondent and, eventually, turns to the only being who has the means to end his suffering — himself.

Of course, there are no superheroes in real life, but there was a man whose biography pretty much mirrors the superhero story — the British mathematician Alan Turing. Turing discovered his superpower, a genius for mathematical logic and computing, at the age of twenty-four when, as a graduate student, he published a paper entitled, "On Computable Numbers, with an Application to the Entscheidungsproblem.” I'll have more to say about the ideas in this paper later, but suffice to say that Turing's result is one of the most profound triumphs of rationality. Turing took his superpower into World War II and used it to battle the Nazis. He designed a computer called the "Bombe" that he and his team used to crack the German Enigma Code, thus freeing Allied shipping and supply lines from the dreaded U-Boats and saving England from the arch-villain Adolph Hitler.

Replica of Turing's 'Bombe' Code Breaker

(Courtesy Wikimedia)

After the war, Turing returned to his studies, published his dissertation, and initially received well-deserved gratitude at home and abroad. Ultimately, as the superhero plot dictates, his fellow citizens became suspicious of Turing's research and perhaps a bit jealous of his intellect. More troubling for Turing, the Brits, whom he had helped rescue from Fascism, were creeped out by his sexual preferences — Turing was gay. The British courts convicted him of gross indecency and sentenced him to a regimen of hormone injections designed to completely suppress his sex drive, not knowing what side-effects that might cause. Turing, a fan of fairy tales like Sleeping Beauty, became depressed, and one morning in 1954 (coincidentally the year of my birth) his housekeeper found him dead with a partially eaten, cyanide-laced apple on his bedside table.

Turing's remarkable 1936 paper defined both the beginning and the end of a new branch of mathematics — computation theory. In the first third of the paper, he formally defined a simple but robust computer now called a Turing Machine (TM). In the second third of the paper he proved that his little machine is universal, that it is capable of performing any computation any other computer can perform. In fact, any machine that can reasonably be called a computer, past or future, laptop or supercomputer, is no more powerful than a simple TM. Modern computers may be and generally are faster in performing some computations, but however elaborate they may be, a TM can accomplish the same thing, eventually. Turing's goal in this was to find an intuitive but formal definition of the phrase "by mechanical means," a phrase that is used quite a lot in mathematics and science.

If Turing had stopped and published the first two thirds of his paper, it would still have been an incredible achievement. It provides us with a universally applicable, easy to understand definition of what we mean by the word "algorithm", an orderly, step-by-step, procedure for doing something like verifying the proof of a mathematical theorem. Turing conjectured that we mean a computer program, specifically a Turing Machine, and today most mathematicians agree with his conjecture. Any effective method for doing something, any method that does not require ingenuity or creativity, exists if and only if there is a TM whose steps encode that method. That's an amazingly general concept which is widely known as the Church-Turing Thesis (Church was Turing's teacher, among many other accomplishments).

But Turing didn't stop after just defining what computation means in a formal sense. The final section of his paper went on to prove there are problems, infinitely many of them, that are not soluble by any TM, and therefore no deterministic procedure exists for finding all the answers. In particular, he proved there are infinitely many real numbers whose digits cannot be computed by any TM, or by any mechanical means whatsoever. I wish I could give you a concrete example of such an uncomputable number, but I cannot, and no one can. Turing proved they are out there, but to provide a finite recipe for producing one of them is fundamentally impossible! It turns out to be quite difficult to identify individual objects floating in the sea of randomness, and when we do find them they're often fuzzy and difficult to crisply discern.

Though we are unable to provide a recipe to produce all the digits of any given uncomputable number, Turing did define a specific problem that he proved could not be solved by any algorithm — the Halting Problem. Is it possible to write a compiler that, given the source code and input data of any other program, will tell us whether the program will ever halt on that input data? The answer is, no such program can possibly exist because it would lead to a logical paradox akin to the "everything I say is a lie" conundrum. Much has already been written about the halting problem, so I won't dwell on it here. It will, however, come up again when we talk about randomness in mathematics.

Our working, informal definition of a random number is any number that is (i.e. whose digits are) universally unpredictable. We've seen that nature provides copious examples of quantities whose measures at the nano-scale are random in this sense. Turing's result shows there are numbers that cannot be computed by any finite algorithm and the Church-Turing Thesis allows us to extend that to mean such numbers cannot be produced by any effective procedure whatsoever. In other words, the shortest, most compact way to describe such a number is to simply list all its digits!

Now you may think these unnameable, unspeakable numbers are rare and difficult to find, and you'd be half right about that. But they are most assuredly not rare. In fact, if you threw a very, very sharp dart and hit the real number line, the probability of hitting such an unnameable number is 1. There is a countably infinite number of nameable numbers, but an uncountably infinite number of unnameable ones. Gregory Chaitin, an American mathematician and computing theorist whom we will talk more about in the chapter on randomness in mathematics, has a name for these real numbers whose shortest possible exact descriptions are the numbers themselves. He calls them algorithmically random, but admits the concept may actually be the best definition of randomness in all its generality.

In physics, we began with the ambition to discover a small set of general principles with which all the universe could be explained, only to find that most of the universe is in fact beyond human grasp. Now, in the more orderly and man-made world of computation, we find that almost everything is uncomputable. There are infinitely many numbers, infinitely many problems, for which even the most powerful and sophisticated computer will be all but useless. Random numbers, in the sense discussed here, cannot be computed and can only come from some source outside the computer.

Turing completed his PhD dissertation at Princeton after the war. While accepting his own conclusion that some problems, like the Halting Problem, were just not tractable, he still wondered what a computer would look like if it could solve such problems, if it could somehow perform magic. In his dissertation, he augmented his TMs to include an "oracle," a magic device that could answer certain unanswerable questions. For example, a Halting Oracle was assumed to be able to discern, somehow, whether any given TM will eventually halt or whether it will run forever. Surprisingly, he found that such super-Turing machines are still limited in their abilities. A super-TM augmented with a halting oracle, for example, still suffers an inability to solve the Halting Problem as it applies to super-TMs. Modern computer scientists still use the idea of oracles to study the limits of computing. A random oracle, a function that always generates the same truly random number when given the same input, is widely used as an ideal cryptographic hash function. In Teaching Robots to Sneeze, we examined how to build what we might call a truly random oracle, which has no input parameters.

Last week, nearly sixty years after his suicide, Queen Elizabeth II granted Alan Turing a posthumous pardon for his supposed crimes. I've noticed that much of the reporting and discussion of this important event has focused on Turing's accomplishments and discoveries, which I find slightly ironic given that he spent so much of his short life contemplating the undiscoverable, the unknowable. Legendary superheroes often have a quiet place, a lair, in which to meditate and seek inspiration. Superman had his Fortress of Solitude, Batman his Batcave, and Alan Turing had the Divine Random.

Teaching Robots to Sneeze

Modern digital computers are not designed to do unexpected things. When they do occur, these are usually called "failures."

But, as I discussed in The Divine Random in Physics, sometimes it's highly desirable, even necessary, to do something that is universally unpredictable. Or, in other words, to compute a truly random number. Even the phrase is possibly an oxymoron, because if you can compute something, or program a computer to compute it, can that ever be truly random? (I will discuss the relationship between computability and randomness in more detail later on.)

Now, if you've written much software, you may be wondering what the big deal is. After all, every operating system and pretty much every programming language has built-in functions called random() or rand() that generate random numbers for you using deep, complex mathematics that, thankfully, we programmers don't need to understand in order to use the functions. Unfortunately, despite their names, these functions do not produce random numbers in the sense that we have used the term here. In fact, the numbers computed by these so-called pseudo-random number generators (PRNGs) are completely, 100% predictable. They do have a sometimes useful property called statistical uniformity or statistical randomness, but they are in no way truly random. Think of the successive digits of the number pi, which are statistically random, but easily predictable by anyone who can divide the circumference of a circle by its diameter.

The extensive use of such PRNGs in commercial and government cryptography products has caused immeasurable harm, the extent of which is only just beginning to emerge. A few weeks ago, it was revealed that the default and recommended PRNG algorithm, whose formidable name is Dual Elliptic Curve Deterministic Random Bit Generator, used by many commercial companies in the US and abroad contains a backdoor vulnerability that was deliberately inserted by its inventor. That inventor, the US National Security Agency or NSA, now has the capability to predict pseudo-random sequences for any software that uses the tainted PRNG. If this doesn't seem all that important to you, consider this. According to the New York Times article,

The agency has circumvented or cracked much of the encryption, or digital scrambling, that guards global commerce and banking systems, protects sensitive data like trade secrets and medical records, and automatically secures the e-mails, Web searches, Internet chats and phone calls of Americans and others around the world...

Incidentally, the tainted algorithm was adopted so widely, despite its known origins in the NSA, because another US government agency, the National Institute of Standards and Technology, NIST, blessed it as a standard and recommended that it be used wherever possible. Government contractors and vendors supplying cryptography products to the federal government were then required to be certified, which certification included the requirement to use a certain PRNG algorithm.

PRNGs aren't all bad. There are many applications, e.g. Monte Carlo simulation and automated testing, where a repeatable stream of statistically random numbers is just what the doctor ordered. But there are other uses, cryptography being one, for which only the best, genuinely random, numbers will do. Another area where universally unpredictable, truly random numbers are highly desirable is for UUIDs - Universally Unique IDentifiers - used, for example, in massively scalable digital storage clusters that have global namespaces. Here, each stored object, and there may be billions or trillions of them, is assigned a UUID that is different from every other object's UUID. Not only that, it is different from every other UUID ever used or that ever will be used. Thus the term "universal." Such UUIDs become the true names for these objects, in the sense discussed in Satnam and other Dangers.

There are several different ways to generate UUIDs that are guaranteed to be unique. Most of these involve some sort of centralized naming authority. For example, the namespace for Internet URLs is ultimately managed by the Internet Assigned Numbers Authority, IANA. But deterministically generating UUIDs in this way is slow and requires a great deal of cooperation. And did I mention there's still some pseudo-government entity controlling the namespace?

An alternative approach, using large, truly random numbers for UUIDs, can't guarantee uniqueness, but it can make it very, very unlikely that two different objects will receive the same UUID (a "collision"). And if the calculable probability of a collision of truly random UUIDs is smaller than the probability of an undetected hardware or software failure in the deterministic algorithms (see Provably Probable is Better than Probably Provable), then the truly random approach has an important practical advantage over the "deterministic" ones. Namely, each process in a distributed network can, in theory, generate UUIDs independently of every other process; no cooperation with other processes or with a central naming authority is required.

Which brings us, finally, to the main topic of this chapter. How can we program a modern digital computer to do something that is universally unpredictable — truly random? How can we teach a robot to sneeze?

Consider the following programming problem. We have four server-class computers, no keyboards or mice attached, all plugged into the same power strip. The servers are all identical - same hardware, same memory, same peripherals. All are networked together through a single network switch. The power strip is switched on so that all four computers start at the same moment and they all boot the exact same operating system, say Linux, and then synchronize their clocks. They then auto-execute an application program whose sole task is to generate a 128-bit truly random number and share it with the other servers. Each server stores the four numbers generated in this round, then compares its number against all previously recorded ones. If its generated number is different from every other number ever generated by any of the servers, it reboots itself and the whole process starts over again. If there is ever a duplicate number generated, an alarm goes off, lights flash, sirens wail, and the V.P. of Engineering gets a frantic phone call in the middle of an otherwise relaxing and much needed vacation in Taos, New Mexico.

There are several different ways to solve this problem, and some are better than others. A naive (meaning terrible) approach would be to simply look around the system to find "random" or unpredictable values, then hash them together to form a candidate number. Simply scrambling the value of the real-time clock would generate a number that is statistically unique across reboots, but every server would likely generate the same value, since their clocks are synchronized. You could mix in other more or less random values, like the serial numbers of peripherals, if available, or the MAC addresses of the network interface cards. But these numbers are static across reboots, so the same machine would find the same values each time and from them generate the same candidate number. Also, these numbers are unique only if you trust the central naming authorities, usually manufacturers associations, that assigned them. Specifically in the case of MAC addresses for NICs, manufacturers are assigned blocks of numbers they then use in serial fashion for their network cards. Since our servers come from the same manufacturer and perhaps the same batch, there is a good chance the MACs are very close to one another. Contrary to common belief, MAC addresses can also be reused over time.

A better all-around approach is to use measured timings for hardware-related events, which relies in one way or another on detecting and measuring small discrepancies (a.k.a failures) in the hardware. The Linux operating system (and most commercial Unix variants) includes a random number generator like this in its kernel. This mechanism measures tiny variations in interrupt timings in various hardware drivers, including keyboard, mouse, hard disk, and network drivers, to accumulate an "entropy pool" of randomness. When an application wishes to use a random number, it simply reads from a special device called /dev/random and asks for some number of bytes of randomness. If there is sufficient entropy in the pool at the time of the request, the kernel returns the requested number of bytes of randomness and reduces the pool by the same number of bytes. If there is not sufficient entropy yet, the read from /dev/random will block until enough randomness accumulates.

The word entropy here is an allusion to Claude Shannon's idea of entropy in communication theory. The actual calculation of this supposed measure of randomness in the Linux random number generator is somewhat mysterious and ill-understood. Even though the source code for it is publicly available, there seems to be no good explanation for why it might work, in theory. Nevertheless, it is clear that the best sources for randomness are the human interfaces; the keyboard and mouse. Ironically, the best way for a robot to do something unexpected is to ask a human! For our sample network of servers, which is based on a real world cluster of storage servers I once helped design, there are no human interfaces from which to draw randomness. Analysis has shown that other sources, notably hard disk drivers, are very poor sources of randomness, generating something like one bit of entropy per minute of operation. It seems the Linux random number pool is exceedingly shallow, which is once again ironic given that we know randomness is not a kiddie pool in the middle of our otherwise deterministic universe, but rather a vast ocean of unpredictability surrounding us all.

There is a way to draw randomness directly from that ocean by using specialized devices called Quantum Random Number Generators, QRNGs. As the name suggests, these devices tap into quantum-level phenomena, including the mother of all weirdness, quantum entanglement, to pull randomness from between the grid lines of the rational universe. Unfortunately, these devices are generally not a part of standard, off-the-shelf, computers like the ones we have conjectured for our example network. Given the importance of this kind of functionality for effective cryptography, that's a little odd, don't you think? If I were a conspiracy theorist, I would suspect the NSA has had a part in this omission.

But the sad fact is, to solve our proposed puzzle using only commodity servers, we cannot rely on fancy QRNGs, at least not today. The question now boils down to this: How can we tap into the realm of quantum-level events using ordinary hardware?

One answer my colleagues and I came up with is to measure the tiny irregularities in the heartbeat of every digital computer, the CPU clock. This clock is derived from a very mundane source: a physically vibrating quartz crystal — basically an atomic tuning fork. Most modern CPUs use a crystal oscillator that vibrates in the neighborhood of 30-80 million times per second and that signal is then multiplied electrically to produce a clock frequency of three or four billion cycles per second, which is the rate at which the computer can execute its simplest instructions. Although modern crystal oscillators are highly stable in their frequencies, things like temperature, humidity and external vibrations do cause small variations to occur, and when the frequency is multiplied by electrical circuits, so is the noise. That's usually okay, since CPUs are remarkably tolerant of lower or higher clock frequencies — most will run just fine at half the clock rate and can generally be overclocked a bit to run faster. But if we could measure these small variations in the vibrational frequency of chemical bonds between individual atoms of a crystal lattice, that would be a good source of quantum randomness. The challenge there is, how can a computer measure variations in its own heartbeat without some sort of external reference?

Luckily, there is a second clock within most every modern computer, one that uses an independent crystal oscillator as its frequency source — the real-time clock or RTC. It is quite important for different computers within a network to agree on what time it is, or at least on how long a second is. To do this, most computers use a much lower-frequency, and less noisy, crystal oscillator operating down near the 100-thousand cycles per second range to measure the passage of time. Of course, this second crystal is subject to the same kind of noise as the CPU oscillator, though less so because of its lower frequency. But that's good for our purposes! We can simply count how many CPU clock cycles occur within each RTC cycle, subtract successive samples and contribute the least-significant few digits to the entropy pool. Conceptually, this sampling can be done by executing a simple instruction loop a few million times and asking the RTC how long it took to complete. Given the realities of things like hardware interrupts and process scheduling, the details are of course more complicated, but the solution remains practical and it works for almost any commercially-available digital computer.

Computers do exactly what we tell them to do. When they don't, we typically think of it as a failure. But unexpected does not always mean faulty. Not only is it useful for software developers to plan to fail when designing complex systems, it is sometimes necessary to actually elicit and embrace failures, to swim briefly in the ocean of randomness. Randomness, one could argue, is at the very core of humanity and human creativity, and it isn't possible to program a computer to do something completely unexpected. To teach a robot to sneeze, we must allow her to surprise us.

Peer Pubs

The land of academic publishing and peer-reviewed journals is a strange land indeed. The business is dominated by a handful of publishing companies, notably the big four: Elsevier, Springer, John Wiley & Sons, and Informa. And don't think its just a niche market; those companies make tons of money and are hugely profitable. In the first quarter of 2011, Wiley made over $250 million with a profit margin of 43%! The largest of the four, Elsevier, made over $1.1 billion in 2010 and 36% of that went straight to the shareholders as profit. Wow. How in the world can there be such a giant market for publications like The Journal of Small Ruminant Research ("The official journal of the International Goat Association")? And why is it such a profitable business?

Well, here's how it works. These refereed journals are periodic anthologies of  scholarly papers and articles on fairly narrow topics (like goat research). They are written, understandably, by academics and researchers and they often document painstaking research and, sometimes, groundbreaking results in thousands of different fields of study. To ensure the accuracy, novelty, and relevance of these results, a long-standing peer review process has evolved in which highly reputable members of the same research community review, accept, or reject submissions. The collections are planned and organized usually by an editor, who is also a member of the same research community, like, for example, the community of researchers in the field of parallel and distributed computing.

Great!, you say. We want these smart, creative researchers to make gobs of money because they are actually adding huge value to our body of knowledge and, eventually, our economy as well. Out of those billions of dollars, how much does the author of one of these articles get paid? Well, nothing typically. They probably are getting a salary from a university or corporate research lab, and publishing research is considered part of their jobs, so they rarely get paid anything by the publishing companies. And besides, they get their name on the papers and enjoy all the fame and glory that comes from publishing a well-prepared, carefully researched treatise on ruminant husbandry or, ahem, byzantine agreement.

So what about the reviewers, whose names do not go up in lights? Yeah, they don't usually get paid either. Again, it's an expected part of their jobs. The editors? Nope.  It is such an honor to be asked to edit a series or even a volume of these prestigious publications that members of that same research community (heck, let's just call it a teamspace) do it for free. So basically, all the intellectual heavy lifting required to produce one of these journals is born by the teamspace itself with little or no monetary compensation expected.

The publishers keep all those $billions for themselves. But surely they provide some useful service, right? The answer is, they used to. In the old days, before the Internet, the publishers handled typesetting, copy editing, printing, distribution, and promotion (marketing). But today, either that stuff is being done by the teamspaces themselves (typesetting, copy editing, promotion) or simply isn't required anymore.  We love the Internet! It makes things cheaper for us consumers and more readily available to all of us. Since the hard work of peer-reviewed publishing is being done free of charge by all those various teamspaces, and since printing and distribution costs have essentially disappeared, I bet you think those journals and the research papers they contain can be had for a song now. Right?

Think again. A year's subscription to the Elsevier journal pictured above, just twelve issues, will cost a library about $1,200.  And that's the online cost! The publishers simply turn a switch  to give you access to somebody else's hard work and they charge you $100 per month per journal for that. University libraries must buy hundreds, perhaps thousands of these subscriptions and most researchers have little choice in the matter because they are required by their employers to publish in certain journals. The kind of open access we've come to expect on the Internet doesn't exist for these types of works, because the publishers make the authors sign over copyrights, again without compensation.  And then to pour salt on an already infected wound, the publishers spend some of that unearned revenue to lobby congress to pass vile, anti-competitive, anti-Internet laws with sickeningly misleading titles like the Research Works Act (RWA), the Stop Online Piracy Act (SOPA), and the Protect Intellectual Property Act (PIPA).

To state the obvious, the international research community is composed of a bunch of really smart folks, and they won't allow this situation to persist for too much longer. Already, nearly 8,000 of them have signed a petition, a bill of rights really, called The Cost of Knowledge, pledging to boycott Elsevier's publications. And there appears to be stirrings of a broader revolt against this ridiculous status quo in the blogosphere.

Most researchers agree that the only real value-add provided by the publishers in this scenario is to provide a framework in which peer review can take place. Not that they actually do the reviews, that's done by the peers themselves. But they provide a framework, a societal network where researchers on any particular topic can socialize, collaborate, swap critiques and comments, reach consensus about which papers to publish in a given issue, and recognize and honor those members who have contributed in a positive way to the body of knowledge. It turns out, reputation is big in academia.  Does this framework sound familiar?

The land of academic publishing will, almost inevitably, evolve into something like the Ethosphere. There's little doubt about this, in my opinion.  To phrase it another way, an Ethosphere teamspace as I've described it in this blog is nothing more nor less than a topical, peer-reviewed, online publication without the parasitic middlemen.

In the Ethosphere, perhaps knowledge needn't cost so much after all.

A Random Story

So randomness and probabilities are inevitable parts of any discussion of distributed consensus. Just how comfortable are we with the fact that our daily choices must be guided, at least in part, by the laws of probability?

When we get behind the wheel of an automobile or strap ourselves into an airplane seat, we are literally trusting our lives to the laws of probability. Since we can't know everything about the pilot of the airplane or the other drivers on the road with us, we wrap ourselves every day in the comfortable knowledge that, with high probability, we will survive to see another day.

But when it comes to computer programs and programmers, we are much more demanding. We expect computers to be deterministic. Period. They perform exactly the same instructions over and over and any deviation from that determinism we call a "bug" or a "fault." We demand that our family photos be kept safe even in the eventuality of multiple, byzantine faults. When you check yourself into a hospital, the chances that an accident or mistake will lead to the loss of your life are quite a bit higher than the chances that an accident or mistake will result in the loss of that kitty cat picture on Facebook. (Small caveat: I totally made that up.)

The fact is, we accept that the universe is stochastic but demand that computers be deterministic. Here's a true story about how I once forced a customer of mine to face that bias and, I hope, start to change his attitude a bit.

While I was at Caringo (they probably still do this) we would periodically conduct training classes for customers of our products, which includes CAStor, a scalable, distributed object storage solution. I would typically join the students and instructors for lunch one day to answer any technical questions they had about the products.  During one such training class, I learned from the instructors that one of the students was being vocally skeptical about one of the foundational assumptions we had made in the product.

CAStor can store billions, even trillions of distinct data objects, each of which has a universally unique identifier (UUID) associated with it.  Other similar products on the market generate these UUIDs in a deterministic fashion that necessarily involves a central naming authority - an expensive and fragile solution IMHO. CAStor's innovation in this area was to instead use a large truly random number for these UUIDs, removing the requirement for a central authority and significantly simplifying the generation and management overhead.

Using this mechanism, the chances that two distinct objects will be assigned exactly the same UUID are very, very, very (to the 42nd power) small. But it is possible and, of course, it would be a bad thing if it happened, which is exactly the objection being raised by our skeptical student.  I mean, we're talking about computers here, and he expected a deterministic guarantee that such a collision is not possible.

So I expected a question along these lines during our meet-the-architect lunch. But it didn't come.  At the end of the lunch, after we'd all finished our deli sandwiches, I decided to bring up the topic myself. I went into the kitchen of our corporate offices and retrieved a wine glass that had been sitting on the top shelf collecting dust. Back in the training room, I tapped the glass with my pen to get everyone's attention and, without saying a word, placed the glass into my empty lunch sack, twisted it shut, and put it on the conference table. Then I picked up a heavy metal power strip and, again without a word to the class, pounded the sack with the power strip until the glass was thoroughly shattered.

Everyone moved away from me there in the training room. The instructors, whom I hadn't warned about this, considered calling building security.

After a brief pause for effect, I picked up the lunch sack and began shaking it vigorously. Then I asked, "Who here believes the glass will spontaneously reassemble itself if I keep shaking the bag?"

No one answered. So I upped the ante.

"What if I continue shaking it like this all day?  All year?"  Nobody answered.

"What if I continue shaking the sack for the rest of my life? Who believes the glass shards will accidentally find their way back in the exact same configuration they started in to reform the wine glass?"

Finally, the troublemaker student answered. He timidly said, "Well, it could happen."

"Exactly," I said.  "It could happen. And if any of you believe it actually will, I recommend you should not buy our product." And I left the room.

I'm happy to report that our "troublemaker" student became a big believer in our product and is still a customer.

Provably Probable Social Choice

There is a strong theoretical similarity between computer networks and people networks. Here we will discuss a surprising fact that has been proven to be true for both human and computer networks.

Without a coin to flip, there is no safe way for independent entities to reach consensus! 

The previous chapter contained a light treatment of a fairly heavy theoretical topic in computer science, Byzantine Agreement (BA), and an exploration of how randomness is an essential requirement in overcoming certain impossibility results in distributed computing. As it turns out, there are some tantalizingly strong similarities between the theory of distributed agreement and the theory of social choice (SC).

Recall that the BA problem setup involves a number of distributed processes each of which starts out with an initial value for some variable. We might call this initial value the "authentic" or "honest" value of a process, because all properly functioning processes will honestly report this value to all others. The goal of any BA algorithm is to allow the processes to vote for their authentic value and to compute, eventually, a global value in such a way that two straightforward requirements are met:

1. If all well-behaved processes have the same authentic value, then the global consensus value must be that value.
2. If the well-behaved processes do not all agree on the same authentic value, they must still agree on some global value; it doesn't matter which one.

To make it more interesting, the problem allows for the possibility of faulty processes that do not honestly report their authentic value choices but rather attempt to game the system to influence the agreed upon result, or to prevent any agreement from being reached. If we place no constraints at all on the types of failures the faulty processes can experience, then we may as well assume the nefarious nodes are consciously trying to thwart our algorithm and that they have complete access to all the information they need to do so.

Already we can start to see similarities between BA and SC (voting) problems. We have a number of independent processes (voters), each of which has its own preferred value (candidate) and they must report (vote) in order to agree on (elect) a global winner in a fair manner. Some of the entities may be faulty (dishonest) and instead report (vote) strategically, using information about partial results to unfairly game the system in favor of their authentic choice.

Terminology note: The social choice literature seems to use the terms "strategic voting" and "tactical voting" interchangeably to mean voting for some candidate who is not your authentically preferred one in order to try to influence the election in your favor. Here we will use "tactical voting" because it describes better what's actually going on.

A very interesting question to ask for both BA and SC is this: Is it possible to devise an algorithm in which the non-faulty (honest) processes (voters) can overcome the evil impact of one or a few faulty (dishonest) ones so they cannot unfairly influence the result?  Not surprisingly, many mathematicians have examined this and similar questions and, perhaps surprisingly, the answers have been rather discouraging.

In the area of Byzantine Agreement, it was proven in 1985 that, for any practical scenario (where, e.g.,  message delivery times are unpredictable) there is no deterministic algorithm that will prevent even a single faulty process from influencing the results of the agreement. All the great work and research to find solutions in this area depends on randomness in some way to solve this important problem.

So what about the Social Choice arena? Around the same time (1984) Michael Dummett published several proofs of a decade-old conjecture now called the Gibbard-Satterthwaite theorem which is about voting algorithms used to select one winner from a group of three or more candidates based on voters' preferences. To paraphrase, the theorem states that for any reasonable scenario (where, e.g., there are no blacklisted candidates and the winner is not chosen by a single dictator) there is no deterministic algorithm that will prevent even a single tactical voter from influencing the results of the election. Sound familiar?

There is a more well-known, but in some ways less interesting, result in social choice called Arrow's Impossibility Theorem that has a lot in common with the G-S theorem discussed above. Dr. Kenneth Arrow received the Nobel Prize in Economics for his work related to this theorem in 1972. Professor Nancy Lynch received the Knuth Prize in 2007, in part for her seminal work on the impossibility proof for Byzantine Agreement. Yet, as near as I can tell, neither discipline has cited the other in all these years, despite the striking similarities of the problems and results and the huge amount of research activity associated with the two independent fields.

Don't get me wrong. I'm not saying these two canonical problems are identical, or even that there is a common underlying body of theory (though I believe there very well might me). But even the differences in the problem statements are illuminating and may indicate areas for further research in one field or the other. For example, the BA problem statement requires every non-faulty process be able to independently compute and verify the agreed upon value. There is no central authority to tabulate votes in BA, whereas in SC, it is typically assumed the independent voters submit their preferences which are then tallied in one place by a trusted central authority. But would it be a useful requirement for each voter in a SC scenario to be able to independently verify the results of an election? I believe this could be the basis of a reasonable formal definition of election transparency, a very useful property of real elections.

There are also areas where the typical formulations of SC problems are actually more stringent than BA. Remember the validity requirement for BA is, if every non-faulty process begins with the exact same initial value, then the algorithm must choose that value. If even one good process has a different value, then a correct BA algorithm is free to choose any value at all, as long as everyone agrees with it in the end. For SC, however, we must agree to elect a candidate based on more flexible requirements. An alternative validity rule might be, if a plurality of non-faulty processes have the same preferred value, the algorithm must choose that value. Or more generally, the algorithm must choose the winning candidate such that voters are the least unhappy about the result. This suggests some interesting extensions to the BA problem, such as Synchronous Byzantine Plurality.  I have no idea whether that problem has been studied or results reported in the literature, but reasoning by analogy (always a tricky thing to do) with the Gibbard-Satterthwait theorem, I would guess that synchronous BA with a plurality rather than unanimity constraint would be impossible in a deterministic way.

Despite all the interesting complexities with these two fields of study, one can definitively say that no completely robust solution to either BA or SC is possible without randomness. Faulty and/or malicious participants can always overwhelm honest participants to influence agreements and elections.  Without a coin to flip, there is no safe way for independent entities to reach consensus!

New Directions

Some of you know that I stepped down as Caringo's Chief Architect last summer to pursue my next endeavor. I'm still very positive about the company and its products, and, most importantly, the team of very bright software folks who continue to work on CAStor and the future of the cloud.

My interest in distributed computing has not waned, and I will continue to write about related topics here as the spirit moves me. However, having watched the emergence of social networking systems like Facebook and Twitter over the last few years, I have begun to think again about broader, but related topics. In a way, social networking - "distributed people" - is like distributed computing and it shares many of the same challenges and opportunities. Both fields ask essentially the same question: How can we build systems in which autonomous, distributed entities collaborate with one another in order to accomplish goals?

So I am going to expand the focus of this blog to include some of the fascinating (at least to me) ideas I've been exploring over the past few months. We will touch on issues such as distributed collaboration, online voting, reputation, and identity and discuss them from both technical and social viewpoints.

Given that we're talking about people now, and not just computer hardware, I expect some of the topics will be more controversial. And that's good! Feel free to comment on any post if you disagree or want to correct my assumptions. Part of the point of this blog for me is to learn from my readers (assuming there are any) and test some theories of mine that so far only my dog has vetted.

This should be fun.

Visualizing Replication

Here's the second in my video tutorial series.  This one explains how CAStor replicates objects in order to protect against hardware failures and ensure data integrity.

Satnam and Other Dangers

The idea of a True Name for something or someone is very old. A true name captures the essence, the intrinsic identity of something in a short moniker that is distinguished from every other name. For centuries, mankind has recognized the fascinating duality that one's true name is both a treasure and a vulnerability.

Religion has long been obsessed with the true name of God. The ancient Jews revered it and believed it had such power they forbade its utterance by ordinary people and spoke it officially once every seven years. Sikhs have a word for the concept, satnam. The true name of true names I guess.

The concept of true name is ancient and pervasive in the secular world too. Rumplestiltskin cherished his so much he sang songs about it, then tore himself in half when it was discovered. One of my favorite science fiction stories is actually titled True Names. Written by the mathematician Vernor Vinge in 1981, the novella explored the promise and threat of one's true name in cyberspace, and incidentally invented the cyberpunk genre which was later fleshed out by William Gibson, Neal Stephenson, Bruce Sterling and others. The title of this post is borrowed from Vinge's first anthology.

Back here in the cyberpresent, names for persistent objects in computer technology have an unfortunately muddled story. Traditional file systems conflate the notions of name and containment for files. We say that a file is "in a directory" or "contained in a folder" when really we're just speaking about a prefix of its name. This leads to some weird, but by now familiar, holes in the metaphor. When you "move" a file from one folder to another, usually the file's contents aren't moved at all; the file is simply renamed. In Unix-based file systems, the "hard link" mechanism allows a single file to have more than one name. This metaphorical blemish of having to explain that an object can be in two places at once is often gotten around by pretending the hard links are distinctly different kinds of names from the originals, so a file has one definite location and perhaps some other, lesser references to it from other locations. This notion is patently false; all names are created equal in this case and if you delete the "original" hard link the others will continue to work as usual. The fact is, files can have different names in different contexts. But do they have a satnam that is the same in every context?

Sort of. In traditional Unix/Linux file systems, a file's inode number is its true name. All other names are mapped to the inode by the file system's directory mechanism. The inode data structure itself contains information about where to find the various parts and pieces (blocks) that make up the file's data content. An inode number is a 32-bit or, in more recent releases, 64-bit binary persistent name for a file. Ideally, a satnam does not depend on context; it refers to the same thing everywhere and everywhen. But a 32-bit inode is not long enough to allow that since it accommodates only about 4 billion files. This may seem like a big number, but it isn't even close to being big enough to uniquely identify every computer file in existence. So the Unixen came up with the concept of a file system, which effectively scopes inodes so they make sense only within the limited context of a single file system, usually hosted on one server. In other words, inodes do not have global scope. Nor is 4 billion inodes enough even to uniquely identify all the files in a single file system, if we remember that files may be created and then deleted. Again, ideally each instance of a file would have a satnam that's different from every other instance that ever existed. But inodes do not have such universal scope either, since they must be reused. The newer 64-bit inodes do allow up to about 18 X 10¹⁸ distinct inodes, which helps us build larger file systems that span several servers, but the namespace is still not large enough to support universally scoped true names.

Distributed storage systems that aspire to scale without limit, must support an essentially infinite (that is, a very, very large finite) number of distinct objects, over the entire lifetime of, well, everything. Further, the degree of cooperation and agreement required to implement a coordinated distributed namespace is, to say the least, exorbitant, even impossible in most cases. Conventional, hierarchical naming schemes always require a centralized naming authority somewhere along the way (that's why the IANA exists). These types of distributed storage systems really do need a satnam, a universally-scoped name for each stored object.

My colleagues here at Caringo, Paul Carpentier, Jan Van Riel, and Tom Teugels, invented a process (US Patent 7,793,112) by which an intrinsic satnam can be derived from any binary object. This technique, the basis for Content Addressable Storage, or CAS, uses a cryptographic hash to digest the bits and spit out a 128-bit name. Depending on the strength of the hash algorithm, this can produce a universally unique identifier, a true name. The drawback is, smart hackers keep finding ways to defeat the crypto algorithms to produce completely different objects that have the same names.

At Caringo, we built a clustered, scalable storage system called Swarm using a different technique that doesn't suffer this drawback. We assign a satnam to an object when it is initially created, a 128-bit name that, with very high probability is different from any other satnam being used anywhere in the universe at any time, past, present, or future. This universally unique identifier is stored with the object's data bits and becomes part of the object as it moves around the world, gets replicated, and so on.

The differences between these two approaches suggest a rather deep philosophical question. Is it the case that one's fundamental identity is embodied in the sum of all his traits (the data bits) or is it the fact of his creation that identifies him? If I create a data object today here in Austin, and my great-great-great-granddaughter also creates a data object on Mars using precisely the same bits in the same order, are they the same object? Should they have the same satnam? Philosophically, I have no idea, but Caringo Swarm says, no. Objects created at different times or places are different objects, even if they appear otherwise to be the same. An object's satnam is universally scoped and intractable to guess, unless you have the object itself.

Which brings us back to Rumplestiltskin. The only way to access an object stored in CAStor is to produce its satnam. If you wish to keep it confidential, then you simply do not ever divulge its true name to anyone you don't trust. Don't go singing it around the campfire.

Visualizing

A couple months ago I wrote a useful tool to help us visualize the operation of a CAStor cluster in situ. It provides a bird's eye view of the nodes and communication among them by replaying a syslog file captured during an actual execution. We plan to use this tool for a number of different things, from marketing to tech support, even design validation. As a first application, I have begun using it as the basis for a series of tutorial videos explaining the inner workings of CAStor. Here's the first installment.

Check it out!

Chocolate Empathy

One reason it's so hard to design good distributed software is that programmers must, for lack of a less anthropomorphic term, empathize with multiple processes at once. A CAStor storage node, for example, is not omniscient. It knows only about its own state and enough about the global cluster to operate. Answering even very simple questions like, "How much available storage is there in the cluster?" involves communicating and agreeing with other nodes. From the programmers' perspective, we must imagine ourselves in the place of each of the individual nodes and model, in our heads, what is known and, more importantly sometimes, what cannot possibly be known by each node at each point in the algorithm.

This capability to maintain many different models of what others know, in addition to our own knowledge store, is an amazing feat of the human mind. And we do it all the time. Every conversation you have with another person relies on a gigantic store of knowledge about what she knows, whether she knows that I know she knows it, and so on. But this ability is definitely a higher function of the brain and does not come without some mental effort.

A famous psychological experiment performed by Wimmer and Perner in the '80s shows this mental ability does not mature until fairly late, four years old or so, in a child's life. The experiment that demonstrates this is elegant and simple. Children are told the following story. A little boy named Maxi and his mother return from a shopping trip at which they purchased a bar of chocolate. The mother places the chocolate in a blue cabinet and closes it. When Maxi goes outside to play, the mother moves the chocolate bar to another, green cabinet. When Maxi returns to the kitchen, he decides to have a bite of chocolate. Which cabinet, the children are asked, will Maxi look in to find the bar?

Before the age of three or four years, almost all children will say Maxi will look in the green cabinet, because that's where the mother put it! Proving they have not yet fully developed the ability to model someone else's mind or empathize with another, albeit fictional, person's knowledge base. It may also be the case that this mental ability is lost or stunted as we become old (speaking strictly from personal experience).

So this stuff is hard. It's the difference between teaching someone to dance and choreographing a ballet. CS curricula, by and large, train us to be omniscient, sequential programmers. Perhaps that's why so many otherwise talented developers mistakenly believe every storage node should just know to look in the green cabinet.

Plan to Fail

During a particularly intense design session the other day, one of my more brilliant engineers and co-architect of CAStor asked what he thought to be a rhetorical question. If we can provide a deterministic algorithm that completely solves a problem except for failures, shouldn't we do that?

At the time, I was dumbfounded. The answer seems so obvious I had no reply. Of course we should do our best to push the failure cases into a corner, solve them separately, and keep the blue sky paths as true blue and predictable as possible. Now, after some careful and mostly sober consideration, I can revisit that moment and provide the answer I wish I had thought of at the time. That's because, I have a blog. Not just anybody can get one of these, you know.

The answer I wish I had given is, not always.

We software engineers tend to think of failures as exceptions, bad things that don't happen very often. When it does happen, a failure injects asynchrony and non-determinacy into the problem whether we like it or not. One can never be sure of when it will happen or exactly how the failure will exhibit itself. We can easily allow ourselves to believe that failures are tricks the universe plays on us. But really, a failure is just a mismatch between our imagination and reality. If something we expect to happen doesn't happen, or something we expect to happen quickly takes too long, or something we expect to behave in a certain way starts acting up, we call that a failure. But that doesn't mean reality has failed us, it just means our imaginations are limited.

Whoa! Too philosophical. Let's return to the cocktail party.

In a previous post, I described two different algorithms for answering questions like the one posed in the original scenario. We observed that the probabilistic one was better than the deterministic one in several ways, but it had a very serious drawback; it doesn't always give the correct answer! Now let's see what happens when we inject something that might be called a failure into the story. Every party I've ever attended had a bathroom for the guests' convenience. Regularly, but at unpredictable times, a guest will simply disappear for a few moments and be unavailable to send or receive messages with the other guests. This models a failure because a given guest may, at any moment, go to (sheer force of will allows me to refrain from potty humor here) the loo. We can now examine how failures impact the two algorithms previously described.

First the deterministic algorithm. If the host makes a request to look up a number while one of the guests happens to be indisposed, and if we're unlucky enough so that guest happens to hold the card for which we're searching, then the algorithm cannot possibly return the correct answer. Worse than that, since the ring has a temporary hole in it, the algorithm cannot even complete and it will hang. If there is only one water closet, we can overcome this problem by having each guest remember their nearest two neighbors on each side, allowing the algorithm to "hop over" any failure. If there are two bathrooms, raising the possibility of two simultaneous failures, there will need to be some sort of ring repair sub-algorithm that gets invoked whenever a failure is recognized. I'll leave the design of such a repair strategy to the reader, but suffice to say that the resulting overall algorithm will be even more complex in order to handle the exceptional failure cases. Even if there is only one copy of each card at the party (we'll talk about redundancy in a minute), this new algorithm will still be deterministic except for failures. Looking at things more holistically, however, it is clear that an inopportune call of nature can cause the "deterministic" algorithm to give the wrong answer, just like the probabilistic one.

Speaking of the probabilistic algorithm, what do we need to modify to accommodate the possibility of unpredictable bathroom breaks? The answer is, absolutely nothing. This algorithm is inherently potty tolerant. Assuming one copy of each card, it will still report a false negative result if we are unlucky enough that the person holding the exact card for which we are currently searching happens to be taking a break, just like the "deterministic" algorithm. But there is no disconnect between our expectations of the algorithm and its actual behavior either with or without failures. In all cases, there is an unlikely possibility of a false negative result.

There is an easy way to rescue the determinacy of the "deterministic" algorithm by making multiple copies of the cards. In general, b+1 copies are required to ensure no false negatives if there are b baños at the party. This trick works for both algorithms in fact, and for the probabilistic one, it will also reduce the probability of a missed shout, because any of the b+1 guests holding a copy of the card being searched can respond with the correct answer. In reality, it is not always easy to bound the number of simultaneous failures, so there remains, always, some possibility of a false negative being returned by either algorithm.

Thinking of failures as being exceptional, rare occurrences often leads to inefficient, and sometimes incorrect, algorithms. For those of us designing systems that are intended to scale without bounds, it is a mental convenience we cannot afford. As the number of guests at the party continues to increase, the probability of an inconvenient leak becomes completely unexceptional. Paradoxically, many of the algorithms we end up using for these sorts of problems, like the simple shout and listen algorithm at the party, feel almost too primitive to be useful, and yet, they often are the most robust. To be successful in this arena, we must view failures as a normal, expected part of the problem definition.

We must plan to fail.

Back to the Party

I recently posed the party problem while interviewing a candidate. There are many good solutions to the problem, and his approach was on target, if conventional. Typically, he pointed out, these problems are solved by forming the distributed processes, ahem, party guests, into a simple topology, like a ring. Most textbooks on distributed algorithms treat this case at some length because it lends itself nicely to inductive proofs. Of course, a fixed topology wasn't part of the original problem statement, so any algorithm that answers the original question, What word is on the card whose number is 50342?, would need to include a sub-algorithm to first organize the guests into a ring where each party-goer has exactly two neighbors.

Let's describe one such algorithm in more detail. I'd like to defer, until a later post, the part of the problem that allows guests to swap cards in any way they choose. We'll assume for now that each guest continues to hold the same deck of cards they are given when they enter the room. Our initial goal is to introduce each new guest to two others, whom we'll call the R-neighbor and the L-neighbor. A guest's R-neighbor is the one person in the room who has the smallest ID that is larger than his own. Similarly, the L-neighbor is the one who has the largest ID that is smaller than his. The only exception is where the tail of the ring joins the head, at which point the guest with the largest ID in the entire room has as his R-neighbor the guest with the smallest ID, and vice versa. Note, this is a logical ring, not a physical one. If we don't allow the guests to eat and drink, the algorithm will surely fail.

Organizing the guests into such a logical ring isn't too difficult. We could say each person, when she enters the room, chooses a four-digit ID number that is unlikely to be chosen by anyone else and writes it down. (Notice how randomness enters the story, literally, at the front door.) If the guest is the first to arrive, there's nothing more to do; she comprises a degenerate ring of one and is her own R-neighbor and L-neighbor. Subsequent guests all choose their own, probably unique, ID. Each one then chooses some other person in the room, it doesn't matter who, and hands them a message that says, My ID is XXXX. Please find my place in the ring. Upon receiving such a message, written on a slip of paper, each guest checks to see if the new guest's ID falls in between its own ID and the ID of its R-neighbor. If not, he passes the message on to his R-neighbor, who does exactly the same thing. If the new ID does fall between my own ID and that of my R-neighbor's, the new guest is inserted into the ring, which is done by sending messages to the new guest and to his original R-neighbor, introducing them to each other and informing them of the new neighborhood arrangement.

Once the logical ring is in place, the original question can be answered with each guest passing slips of paper to one of only two other guests, its neighbors in the ring. Here's one such algorithm. Upon receiving a message, each guest performs the following sequence of actions (remember, we're looking for a symmetric solution, so every guest must behave the same way) starting with whomever receives the original note from our host.

1. If there isn't already an ID at the top of the message, write my own ID there.
2. If there is already an ID, and it's mine, we're finished. Hand the answer back to the host and skip the remaining steps.
3. Search through my deck of cards looking for the number 50342.
4. If I find a card with that number on it, write the associated word on the slip of paper; this is the answer.
5. Pass the message on to my R-neighbor.

If we discount the possibility that two guests might choose the same ID at the front door, this algorithm is deterministic, both for the positive and negative cases. That is, if the card in question exists in any guest's deck, the algorithm will discover it and answer the question, and if there is no card, the algorithm will report that it doesn't exist. This particular version of the algorithm will provide both answers after sending exactly n+2 messages (counting the two in which the host is involved), where n is the total number of guests at the party. There are various ways to reduce the total number of messages required, but in all cases the number of messages needed will grow as the number of guests increases. Still, this is a pretty darn good algorithm that behaves just the way we like our computer software to behave — deterministically.

Just for grins, lets also describe a probabilistic algorithm that solves the same problem given the same constraints. This one doesn't presuppose any particular topology, so we can skip the organizational first phase. Instead, we proceed as follows. When the host hands the slip of paper with the question on it to a random guest, he shouts to everybody in the room,

"Attention! What word is on the card whose number is 50342?"

Upon receiving this message, each guest searches through his deck of cards and, if he finds the number 50342, writes the associated word on a slip of paper and hands it to the guest who shouted the question, who then passes the answer along to the host. If no one answers within some reasonable amount of time, we assume the card does not exist and send a message back to the host to that effect.

Which approach is "better?" This second algorithm is better in a number of regards. It's certainly a lot simpler. It's also more efficient, requiring only four messages in the positive case — the original question from the host, the shout, the reply from the question, and the reply to the host — and only three messages in the negative case. It also scales better, since neither of these performance metrics grows as the number of guests increases.

But the probabilistic algorithm has a major drawback that would prevent its use by most any red-blooded programmer: it is, well, probabilistic. There is some chance, however small, that the guest holding the requested card does not hear the shout and therefore fails to answer. The shouting guest, in that case, will wait a respectable period of time and then declare, the card doesn't exist. To be precise, he can only truthfully claim that he doesn't know whether it exists or not, since the negative case and the failure case are indistinguishable.

Another drawback of the latter algorithm, also related to its probabilistic nature, is in choosing the right "reasonable amount of time" to wait before declaring the card can't be found. If the chosen timeout is too short, some of the guests may not have enough time to search through their card decks to find the card. If it's too long, the nominal performance of the negative case suffers. Yes, we could have the guest repeat the shout after a short timeout in order to increase the chance that everybody hears it and to give everyone a longer period in which to search their individual card decks. However, there will always be some remaining possibility of a false negative.

Does that mean the probabilistic algorithm is fatally flawed and should be avoided in all cases? More on that later...

Impossibility Result for Asynchronous Consensus

From Fischer, Lynch, Paterson, "Impossibility of Distributed Consensus with One Faulty Process"

In this paper, we show the surprising result that no completely asynchronous consensus protocol can tolerate even a single unannounced process death. We do not consider Byzantine failures, and we assume that the message system is reliable- it delivers all messages correctly and exactly once. Nevertheless, even with these assumptions, the stopping of a single process at an inopportune time can cause any distributed commit protocol to fail to reach agreement. Thus, this important problem has no robust solution without further assumptions about the computing environment or still greater restrictions on the kind of failures to be tolerated!

Provably Probable Is Better Than Probably Provable

Randomness and distributed algorithms are often found together, like movie stars and orphans. It's not just that distributed algorithms often exhibit stochastic behavior, which they do; randomness is also an essential ingredient of many distributed solutions. I'm not speaking loosely when I use the word "essential" here. There are many problems in the distributed arena that are provably impossible to solve deterministically, but if you give processes access to a fair coin and allow them to flip it occasionally, voila!, an efficient, reliable solution emerges that yields the correct behavior. Probably.

The first time I encountered this was with a canonical problem in distributed fault tolerance, called the Byzantine Agreement problem. Don't Google it! There's been so much written and so many results about the topic over the last thirty years that you'll never return if you vector off now. Instead, let me present a concrete instance of the general problem in order to talk about why randomness is such a useful, and in some cases essential, part of the solution.

Suppose there are four computerized weather stations distributed about a certain city. Each station has, among many other sensors, a light detector, and the stations can communicate with each other via whatever protocol we wish to devise. Every hour, on the hour, each station samples its own light sensor and makes an independent judgement about whether it is "daytime" or "nighttime." At noon and at midnight, it is highly likely that all stations will make the same assessment about whether it's day or night. But at dusk and dawn, local variations in light and sensor sensitivity will probably cause the stations to arrive at different conclusions about which is the best classification. Our job is to devise an algorithm and a protocol that allows the stations to all agree on a single answer, and that has two very reasonable properties: 1) if all the stations individually come to the same conclusion about whether it's day or night, then the group must agree on that answer, and 2) even if they don't start out with the same answer initially, they must still agree on some value (it doesn't matter which).

But wait, there's no villain in this story yet. One of the stations doesn't follow the rules. It can say anything at any time to any other station without constraint. Maybe it's faulty, or maybe it's nefarious. Crazy or evil -- it doesn't matter. We may as well assume the bad guy is a malicious spy who knows everything that has happened, using that information to thwart our little plot and prevent the remaining stations from agreeing whether it's day or night. Now there's a worthy antagonist.

There is a simple, but subtly wrong, deterministic algorithm that attempts to allow the three non-faulty stations to reach agreement at all times of the day or night, even with the omniscient meddling of the faulty one. It goes like this: Each station sends its initial value to every other station. After collecting all four values (including its own), each station determines whether three of the four responses have the same value. If so, the station takes this value as its final answer. If it's a tie, the station picks a predetermined default, say "daytime," and the nodes exchange values in another round of communication. The algorithm terminates when all the correct nodes have chosen the (same) final answer.

You can see that, if it's noon or midnight and all three non-faulty stations report the same value, there is little the nefarious foe can do to confuse this algorithm; they will all see at least three identical answers and immediately choose it. There is danger at dusk or dawn, however. We're still okay if two of the non-faulty stations thinks it's day and the other one thinks it's night. In this case, there's no way the nefarious foe can influence the vote so that "nighttime" is chosen by any of the non-faulty stations. They will all pick the default value, "daytime," after the first round and confirm it as the agreed value on the second round.

The remaining case is vulnerable to attack. When two of the non-faulty stations initially think it's night and the other thinks it's day, the nefarious foe, in full omniscient glory, can whisper "nighttime" to the nighttime stations and "daytime" to the daytime station. The nighttime stations will therefore continue to vote nighttime, because they see three votes for that value, while the minority station will continue to choose the default value, "daytime." Thus, the faulty foe can ensure the stations never reach agreement on any value.

Surprisingly, this simple but incorrect deterministic algorithm can easily be converted to a simple and correct probabilistic one, just by giving each station a fair coin to flip. Instead of picking a predetermined default value (which is subject to being discovered and exploited by the evil one), each station flips its coin in the event there are not three votes for the same value. Heads, it's daytime, tails it's night. If the non-faulty stations do not unanimously agree, The Faulty One can still influence one of the two cases, as described above, but since it cannot predict the value of the coin flip (that's what random means) there's no way to tell which is the vulnerable case. There's only a 50% chance our malicious adversary will be able to thwart agreement on any given round, so if we just keep repeating the algorithm round after round, the stations will eventually reach agreement, despite the best efforts of the know-it-all evil station.

Probably. We have a choice with this probabilistic algorithm. We can either stop it after a fixed number of rounds, and accept the (tunably small) possibility that agreement has not yet been reached, or we can run it until agreement is reached, and accept the (tunably small) possibility that it takes so long we no longer care whether it's night or day. This exact trade-off is typical of distributed, probabilistic algorithms.

To be fair, there is a simple deterministic algorithm that solves this problem (see the seminal 1980 paper by Pease, Shostak, and Lamport), but it depends on a subtle condition that doesn't always exist in real-life distributed systems -- synchronous communication. Another famous result in this research area is that of Fischer, Lynch, and Paterson, which proves no deterministic agreement algorithm can exist unless we can give, with certainty, an upper bound on how long it will take messages to be delivered between processes (weather stations in this case). And yet, there are many good probabilistic solutions to this important practical problem!

Back in 1987, a fellow graduate student at the University of Texas at Austin, Russell Turpin, and I were struck by this result. So much so that we spent several months reading and analyzing the plethora of research on probabilistic agreement and writing a survey paper on the topic. Now, twenty-five years later, Dr. Turpin and I are still friends and colleagues, and we expect our interest and passion for distributed solutions to continue for many more years to come.

Probably.

A Party Game

Let's play a party game. Here are the rules. When each of us arrives at the party, the host hands us some flash cards. Each card has a single number and a single word written on it. Generally, cards have different number-word pairs, but the same pair might be repeated on more than one card. A given number is always associated with the same word, however.

Everybody gets some number of cards, from just a few to a handful or even a whole deck. We are told we may swap cards with others, in pretty much any way we want, except we cannot look at others' cards. In fact, we can communicate with others in only two limited ways: we can write a short note on a slip of paper and hand it to one other person, or we can shout a message to the entire group. The latter mechanism is somewhat error-prone since we can never be sure others are listening and can hear our shout. Also, someone else may decide to shout at the same time, in which case neither of you may be heard.

After a few drinks, the game commences. The host chooses someone at the party and hands her a slip of paper on which is written a simple question, "What word is on the card whose number is 50342?"

Staying within the rules and constraints outlined above, how would you behave, and how would you want other party goers to behave, in order to "efficiently" answer that question?

Automatons, Organisms, and Teenagers

Wouldn't it be great if you could tell your child exactly what to do in a given situation and be completely confident he or she would do just that, every time, without question? If you've ever raised a teenager, I promise you've wished for that before. But would it really be all that great?

Yes, we could, theoretically, help our kids avoid many of the mistakes that we made growing up. On the other hand, they could never be better than us. It turns out, all the pleasures and pains of child rearing stem from the unexpected, emergent behavior of our children. Thank goodness kids are organisms, not automatons.

My software team and I at Caringo, Inc. are raising our own child, named CAStor -- a symmetrically distributed, massively scalable, clustered storage system. CAStor is not quite a teenager yet, but already I'm getting questions from customers and partners.

"Why does it behave this way in that situation?" they ask. To which I'm often forced to answer simply, "I don't know."

When the behavior in question results in a positive outcome (which it frequently does), they wonder why I don't take credit for it. After all, CAStor is a computer program, a digital automaton, and we programmed the darned thing. How could we not know why it behaves the way it does?

The answer is, computers may be automatons, but computer networks are organisms.

In the past two decades, we have seen the emergence of a whole new class of application and infrastructure software. Scalable, robust, distributed solutions capable of handling hundreds of millions of users, perform billions of transactions, store and retrieve millions of gigabytes, and maintain high availability despite hardware failures, software upgrades, and malicious attacks. Those of us who design and architect such solutions understand (sometimes) there is a qualitative difference between these organic, adaptive computer networks and the "do this now" sort of programs we learned to write in school.

This blog is about the practical potential and limitations of distributed computing, the trade-offs between determinism and probability, certainty and surprise. Along the way, I hope we'll explore all kinds of topics, from space photography to train tracks, thermodynamics to wine glasses, the meaning of knowledge, randomness, and time.