Yes, you can have exactly-once delivery

Introduction

This post is ostensibly about an obscure technical issue in distributed systems, but it's really about human communications, and how disagreements that on the surface appear to be about technical issues can sometimes turn out to actually be disagreements about the meanings of words.  I'm taking the time to write a fairly extensive post about this for two reasons.  First, I'm hoping it will be helpful to provide a case-study about what appears on the surface to be a technical dispute that turns out to be a mere quibble over terminology.  Learning to recognize such situations can help defuse tense situations.  And second, this might provide some cover for someone early in their career who comes to the same conclusion I did about a certain emperor having no clothes.

The dispute

I was reading Hacker News a few days ago and stumbled on a comment posted by /u/solatic in response to an article entitled "Falsehoods programmers believe about TCP".  I quote that comment here in its entirety:

Related: you can get at most once delivery or at least once delivery; you cannot get exactly once delivery. If I had a dollar for every junior who thought that a lack of exactly once delivery guarantees was a bug...

This struck me as odd because I could see a straightforward way to implement exactly-once delivery on top of at-least-once delivery.  But solatic seemed sufficiently confident that I thought I might be missing something, so I posted what I thought was a cautious response:

If you can get at-least-once delivery, why can you not build exactly-once on top of that?

I won't go into detail about what happened after that.  You can go read the resulting thread if you like, but the TL;DR is that the discussion spun wildly out of control, which ultimately motivated me to write this post.

Before I dive into the details, I want to give my credentials because I am about to challenge what is apparently some pretty deeply entrenched conventional wisdom.  Unfortunately, many of the people who hold these mistaken views seem to subscribe to arguments from authority.  I got a lot of admonitions that were tantamount to, "You obviously need some remedial training in basic computer science."  That's possible, but I want to provide some information about my background so you can adjust your Bayesian prior regarding that particular hypothesis.

I have a Ph.D. in Computer Science.  My specialty is (or at least was) AI and not distributed systems, but I nonetheless know my way around a network stack.  My first startup, about 30 years ago now, was an (unsuccessful) attempt to launch a new network architecture.  We built our own hardware.  I wrote the Linux device drivers for our custom NIC.  I currently work part-time as a consultant for a hardware design team that builds network routing chips.  I know how a modern network works literally from the transistors on up.  And I know about the two generals and the muddy children.

So with that, let's look at the claim that I found questionable: "You can get at most once delivery or at least once delivery; you cannot get exactly once delivery."

What does "delivery" mean here?  The entire kerfuffle turns on the ambiguity of the meaning of this word, which none of my interlocutors ever defined.  But whatever it means, my puzzlement stemmed from the fact that I could see a trivial way to build exactly-once delivery from at-least-once delivery, under any reasonable definition of "delivery".  Specifically, if you could get at-least-once delivery, then turning that into exactly-once delivery should be (it seemed to me) a simple matter of keeping track of all the delivered messages and removing duplicates.  Doesn't that seem plausible to you?  If so, congratulations, your intuitions are serving you well because that will in fact work.  It's not a particularly good solution from an engineering point of view, and it is absolutely not how you would do it in practice (at least not without a lot more refinement) but it does refute the claim that you "cannot get exactly-once delivery".  You can.

So why do so many people deny this obvious truth?  Well, that's a good question.  I'm not 100% sure because no one in that HN thread ever presented a cogent argument or even a reference.  But one common theme that ran through the responses was that I needed to brush up on the two-generals problem.  So let's do that.

The two-generals problem

The Two Generals problem is a classic problem in theoretical computer science first studied by Leslie Lamport in 1983.  It was the first time ever someone proved that a particular problem in computer science had no solution.  Some people claim that if you could get exactly-once delivery you could solve the two-generals problem, but this is false.  The two problems have nothing to do with each other, despite having some superficial resemblance.

The two-generals problem is this: there are two generals (imagine that) leading two armies against a common enemy.  They can defeat their enemy only if they successfully join forces and coordinate a simultaneous attack.  But they are geographically separated in an era before modern telecommunications.  The only way they can communicate is by sending messages via courier thorough enemy territory, where they risk being captured and never heard from again.

It turns out that it is impossible for the generals to coordinate their attack under these conditions.  In order to coordinate the attack, each general needs to know that the other general has received and agreed to the same attack plan that they intend to undertake.  The technical term is that they need to achieve common knowledge, which turns out to be impossible using an unreliable communications channel.  The proof is easy to understand: if there were such a protocol, then that protocol must have a termination condition, some point at which consensus has been reached, after which no further messages need to be sent.  But the protocol must still work even if the last message in the protocol fails to arrive, and so sending the last message must not be necessary -- the protocol has to still work without it.  By induction, the protocol must work even if no messages are sent at all.  That is clearly impossible, and so our assumption that there exists such a protocol must be false, QED.

But achieving common knowledge has absolutely nothing to do with the question of whether exactly-once delivery is possible -- it is.  As I've already described above, the easiest way to do it is to keep track of all delivered messages and remove duplicates.  (Exercise: why does this strategy not succumb to the same proof of impossibility as the two-generals problem?)

Exactly-once delivery

Now, this is where things get tricky, because no one ever actually responded to this very straightforward suggestion.  So at this point I need to extrapolate the replies I did receive and guess what the response would be if I really put someone's feet to the fire.  My guess is that they would say that what I've provided is not exactly-once delivery but exactly once processing.  I've made the processing of incoming messages idempotent, so that it doesn't matter if I get duplicate delivery, but I have not actually eliminated duplicate delivery, or something like that.

It is possible to define "delivery" makes the claim that exactly-once delivery is impossible true.  The problem is that such a definition only serves to advance pedantry and ignores important subtleties in human communication.  Let's go back to the original claim: "You can get at most once delivery, or at least once delivery; you cannot get exactly once delivery."  There are some things implied here that are not explicitly mentioned.  Specifically, there is an implication that the two things that you (supposedly) *can* have -- at-most-once and at-least-once -- are actually things that one might choose under realistic circumstances.  Consider:

You can get at most once delivery, or at least once delivery, or you can hit yourself in the head with a hammer.

That statement is true -- hitting yourself in the head with a hammer is an option.  But I hope I don't have to persuade you that this is not very useful, and the only thing you're likely to accomplish by pointing it out is to annoy people.  When you provide a list of options, there is an implied social contract that the items on the list have at least some plausible utility.

In a similar vein, one way to get at-most-once delivery is simply to disconnect the communications channel.  That will absolutely guarantee that no message is ever delivered more than once, because every message will in fact be delivered exactly zero times.  Like hitting yourself in the head with a hammer, this is an option you can undertake, but it's not very useful, and so asking someone to actually spend brain cycles considering it can't be anything more than a deliberate attempt to waste their time or insult their intelligence.

Because of this, someone hearing you say "You can get at most once delivery, or at least once delivery; you cannot get exactly once delivery" is entitled to assume that disconnecting the network is not what you meant with regards to the first option.  That assumption is reinforced by the inclusion of at-least-once delivery as a viable option, because that is actually not possible unless the odds of a message being delivered are greater than zero.  Likewise, your interlocutor is entitled to assume that the reliability of the network is less than 100%, not because you explicitly said so, but because networks are unreliable in point of actual fact, and also because that is the only thing that makes this topic worth discussing at all, and the only thing that makes the impossibility of exactly-once delivery even remotely plausible.  In a 100% reliable network you can insure exactly-once delivery by (wait for it!) ... sending each message exactly once!

Likewise, "you cannot have exactly-once-delivery, but you can have exactly-once processing" implies that there is a meaningful distinction to be drawn between "delivery" and "processing".  There isn't.  Processing is ubiquitous in modern networks.  Every router does it, and obviously every end-point does it.  Any distinction between "delivery" and "processing" that would make exactly-once delivery impossible would necessarily beg the question by stipulating that discarding duplicate messages is "processing".  You can't make this distinction in any other way because discarding duplicates can happen anywhere in the abstraction stack, including the device driver, or even in the NIC hardware.  No one does it that way, but only because it's easier and more convenient to discard duplicates in the network stack or the application, not because it's impossible to do it anywhere else.

So yes, you can have exactly-once delivery.  That may not be what you want.  In fact, it is almost certainly not what you want for anything that is actually mission-critical, because a lot can go wrong downstream of message delivery.  But that is a different question.  If you want it, you can absolutely have it.

Just for the sake of completeness I should point out that removing duplicates at the receiver is a pretty extreme oversimplification of what you would do in practice to provide exactly-once delivery.  A complete solution would almost certainly be an example of Greenspun's Tenth Law applied to the TCP protocol rather than Common Lisp.

Final Thoughts

This post was intended to be about human communication more than distributed systems or network protocols, so I want to address one last question: How did this myth of the impossibility of exactly-once delivery get so firmly established?  This is a genuine mystery to me.  I can find no academic citation anywhere, only a few blog posts, none of which have any references.  So I can only speculate.  My guess is that it stems from the fact that distributed systems are monstrously complicated both in theory and in practice, and there are some things that you really cannot guarantee in the face of certain kinds of failures.  But that is true of non-distributed systems too.  Distributed systems just amplify the problems, they don't introduce them.  Even in a non-distributed system you always have the possibility that a cosmic ray will flip a bit somewhere.  Yes, you can have ECC, but you can also have two cosmic rays, or a manufacturing defect, or sabotage, or a bug.  In the real world you can never eliminate all risks.  The best you can hope for is to reduce them to the point where you like the odds.  That's usually good enough.

That is even the case for human endeavors like this blog post.  It's possible that I've overlooked something and that my argument is wrong.  But I've thought about it, and I've done some research, and I'm able to account for all the data, so I'm casting my lot and publishing this, fully aware of the possibility that someone might point something out in the comments that will make me slap myself on the forehead and go "duh".  But even then I will count that as a good outcome because I will learn something.

That's how the scientific method works.

Information, Data, and Knowledge

(This is part 10 in a series on the scientific method.)

In 1966, well within living memory as I write this in 2024, Digital Equipment Corporation released the PDP-10, later rebranded as the DECsystem-10 or, more colloquially, the DEC-10.  The base model cost over $100,000 in 1966 dollars, well over a million dollars today.  For that price you got 8,192 words of memory, each being 36 bits wide, or just a hair over 32 kilobytes by modern reckoning.  A top-of-the-line model gave you about 144 kilobytes (32,768 36-bit words) of memory and cost three times the base model price.  At the time, the DEC-10 was considered a "low cost" computer.  Nowadays a computer with vastly superior specifications fits on a board the size of your little finger and can be purchased at retail for less than less than one 1966 dollar.  If you buy just the chip in modest volume, you can get them for less than one 2024 dollar.

Notice that despite decades of technological improvement, the specifications of a computer's capabilities were given in essentially the same terms in 1966 as they are today, namely, by specifying the amount of memory it contains, and this will always be the case.  Memory has a utility that transcends technology and culture and the whims of fashion: it can store information.

Information is both ubiquitous and ineffable.  We live in an "information age", inundated by information around the clock, but almost no one understands what it actually is.  It's challenging to find a definition that is accessible and not circular.  Wikipedia says, "Information is an abstract concept that refers to something which has the power to inform," which doesn't seem particularly helpful or enlightening to me.

So let's set this as our Problem: there is this thing, information, that everyone talks about, that permeates our modern existence, but that no one seems to actually understand.  Why?  Is information real, an essential part of objective reality, or is it just a social construct like the law or the value of fiat currency?  What is information made of?  Can it be created and destroyed like computers and chairs, or is it conserved like mass and energy?

Let's start by taking stock of some of the (apparent) properties of this thing we're trying to explain.

Information does not exist by itself.  It is always contained in in or bound to something, like a sheet of paper or a computer memory or a DNA molecule or a brain.  This container doesn't necessarily need to be a material object made of atoms, it can be an electromagnetic wave.  But it has to be something.  There is no such thing as information in isolation, not bound to any material thing.

Despite the fact that this containment is essential, the identity of a piece of information is independent of its binding.  The document you are reading right now is in some sense "made of" information.  Most likely, you are reading it on a computer, so that information is contained in a computer memory.  It is transferred into your brain -- i.e. the information is copied -- through the act of reading.  You could likewise copy the information in this document onto a sheet of paper by printing it, or into sound waves in the atmosphere by reading it aloud.  But regardless of whether the information in this document is contained in a computer memory or a sheet of paper or your brain or the air around you, it is, at least in some sense, the same information in all four cases.

How much can information be changed and still be "the same information"?  If this document is translated into a different language, is it still "the same information"?  What about if it is compressed or encrypted?  When information is compressed or encrypted, the result bears virtually no resemblance to the original.  (In the case of encryption, that is the whole point!)  But in each case, there is still some sense in which the result is "the same" as the original.  A compressed or encrypted version of this document is still unambiguously (it would seem) a version of this document and not a version of any other document.

I'm going to put a pin in that for now and invite you to consider a different question, which will eventually lead us to the answers to the preceding ones: what is the difference between information and data?  To persuade you that there is indeed a difference, here is an example of some data:

77 72 17 56 75 22 50 76 20 49 29 16 4 61 33 71 87 65 56 92

The difference between that and all of the surrounding text should be obvious: the text conveys some sort of "meaning" while the data is "just a bunch of numbers".  There might be some meaning there, but it's not readily apparent the way it is with the surrounding text.

So the difference between "information" and "data" is that information has "meaning" and data doesn't.  But what is "meaning"?  That word seems at least as troublesome to define as "information", and so reducing "information" to "meaning" doesn't represent a lot of progress.  But in this case looks are deceiving because the meaning of "meaning" can actually be made precise.  To see how, consider another example:

55 83 56 74 55 70 55 73 56 75 54 77 54 72 55 68 54 66 52 70

At first glance, this too looks like "just a bunch of numbers" but if you look closer you might start to notice some patterns in the second list that weren't there in the first.  For example, if you consider the list as pairs of numbers, the first number is always smaller than the second.  If you look at the first number in the pair, they all fall in a fairly narrow range: 52-56.  The second number in the pairs also fall in a narrow range: 66-83.  That might be enough for you to figure out what these numbers actually are without my telling you: they are the low and high temperature forecasts for a particular location (Redwood City, California) on a particular date (September 8, 2024) according to the Apple Weather app on my iPhone.  So those numbers contain information.

The difference between data and information is that information has a referent -- it is about something.  In the case of the second example, the referent is a weather forecast.  Notice that in order to make sense of that information, to extract its meaning, requires that you know something about what numbers are, how they are represented as marks on a page (or a computer screen), and how those numbers relate to temperatures and geography and time.  But the essential feature, the thing that confers information-ness to those numbers, is that they have a referent, that they correspond to something, in this case, temperatures.

It is this correspondence that is the defining characteristic of information.  Information is a correspondence between two physical things, like marks on a page and current events, or the reading on a thermometer and the temperature of the surrounding material, or the order of base pairs in a DNA molecule and the shape of a protein.

Notice that recognizing this correspondence can require quite a bit of effort.  There is nothing at all obvious about the relationship between the shapes of numerals and temperatures, nothing about the visual appearance of "23" that corresponds to "cold", or the visual appearance of "98" that corresponds to "hot".  To see the correspondence requires going through a lot of intermediate steps, like learning what numbers are, understanding what "hot" and "cold" are, what a temperature is, and so on.  There is nothing at all obvious about the relationship of base pairs in a DNA molecule and the shapes of proteins.  That correspondence goes through a relatively straightforward mapping of base pairs to amino acids, and then a much more complicated mapping of sequences of amino acids to shapes in three-dimensional space.  There are similar processes at work in compressed and encrypted data.  To see the correspondence between compressed and uncompressed data you have to know the compression algorithm.  To see the correspondence between encrypted and unencrypted data you have to know both the algorithm and the encryption key.

There is one additional requirement for data to qualify as information: the correspondence between the information and its referent must be causal.  It can't be simply due to chance.  I could produce a plausible-looking weather forecast simply by picking numbers at random.  That forecast might even be correct if I got lucky, but it would not contain any information.  The correspondence between the forecast and the actual future temperatures has to be the result of some repeatable process, and the correlation between the information and its referent has to be better than what could be produced by picking numbers at random.

How can you be sure that some candidate information is actually information and not just a coincidence?  You can't!  The best you can do is calculate the probability that a correlation is a coincidence and decide if those odds are small enough that you are willing to ignore them.  Calculating those odds can be tricky, and it's actually quite easy to fool yourself into thinking that something is information when it's not.  For example, there is a classic scam where a stock broker will send out market predictions to (say) 1024 people.  512 of the predictions say a a stock will go up, and 512 say it will go down.  For the group that got the correct predictions he sends out a second set of predictions.  256 people get an "up" prediction, and 256 get "down".  This process gets repeated eight more times.  At the end, there will be one person who has seen the broker make correct predictions ten times in a row.  The odds of that happening by chance is 1 in 1024.  Of course it did not happen by chance, but neither did it happen because the broker actually has a way of predicting which way a stock will move.  The existence of information depends on the assumption that the universe is not trying to scam us, which seems like a reasonable assumption, but we can't actually know it for certain.

The existence of information depends on another assumption as well.  Information is a correlation of the states of two (or more) systems, but what counts as a "system"?  There are some choices that seem "natural", but only because of our particular human perspective.  A bit in a computer memory, for example, only looks like a binary system because that is how it is intended to be viewed.  In actual fact, computer memories are analog systems.  When a 0 changes to a 1, that change does not happen instantaneously.  It takes time for the electrons to move around, and while that is happening the state of that bit is neither 0 nor 1 but somewhere in between.  We generally sweep that detail under the rug when we think about computer memory, but that doesn't change the fact that the underlying reality is actually much more complicated.

Some aspects of the apparent behavior of information actually depend on this.  It appears that information can be created and destroyed.  Human creativity appears to create information, and human carelessness or malice appears to destroy it.  There's a reason that backups are a thing.  But if we view the universe as a whole, and if our current understanding of the laws of physics is correct, then information can neither be created nor destroyed.  The currently known laws of physics are deterministic and time-symmetric.  If you knew the current state of the universe, you could in theory project that forward and backward in time with perfect fidelity.  When you "destroy" information, that information isn't actually destroyed, it is merely "swept under the rug" by some simplifying assumption or other.  When you "create" new information, it is not really new, it is pre-existing information being changed into a form that we can recognize under a certain set of simplifying assumptions.

It is tempting then to say that information is in some sense not real but rather a figment of our imagination, an artifact of some arbitrary set of simplifying assumptions that we have chosen for purely economic reasons, or maybe for political or social reasons.  Choosing a different set of simplifying assumptions would lead us to completely different conclusions about what constitutes information.  And that is true.

But our simplifying assumptions are not arbitrary.  The reality of information is grounded in the fact that everything you know is bound to one particular physical system: your brain.  You can imagine taking a "God's-eye view" of the universe, but you cannot actually do it!  In order to take the God's-eye view you would need a brain capable of containing all of the information in the universe, including the information contained in your own brain.  God might be able to pull that trick off, but you can't.

Could we perhaps build a machine that can take the God's-eye view?  At first glance that would seem impossible too for the same reason: that machine would have to contain all of the information in the universe.  But the machine would itself be part of the universe, and so it would have to contain a copy of all of the information contained within the machine, including a copy of that copy, and a copy of the copy of the copy, and so on forever.

There is a clever trick we can do to get around this problem.  See if you can figure out what it is.  Here is a hint: suppose you wanted to make a backup of your hard drive, but you didn't have any extra storage.  If your drive is less than 50% full this is easy: just copy the data on the used part of the drive onto the unused portion.  But can you think of a way to do it if your drive is full?)

Notwithstanding that it might be possible in principle to build a God's-eye-view machine, there are two problems that make it impossible in practice.  First, the engineering challenges of actually collecting all of the information in the universe are pretty daunting.  You would need to know at the very least the position of every subatomic particle, including those inside planets and stars in galaxies billions of light years away.  We can't even access that information for our own planet, let alone the countless trillions of others in the universe.  And second, throughout this entire discussion I've assumed that the universe is classical, that is, that it is made of particles that exist in specific locations at specific times.  It isn't.  At root, our universe is quantum, and that changes everything in profound ways.  Quantum information has a fundamentally different character from classical information, and the biggest difference is that quantum information is impossible to copy.  If you could do it, you could build a time machine.  But that's a story for another day.

The takeaway for today is that ignorance is a fundamental part of the human condition.  Indeed, as we will see when we finally get around to talking about quantum mechanics, ignorance is actually the mechanism by which the classical world emerges from the underlying quantum reality.  (Note that this is a controversial statement, so take it with a big grain of salt for now.)  But even in a classical world, taking the God's-eye view, while possible in principle, is impossible in practice, at least for us mortals.

Can we mere mortals ever actually know anything?  No, we can't, not with absolute certainty.  We are finite beings with finite life spans and finite brains.  We can only ever be in possession of a finite amount of data, and that data will always be consistent with an infinite number of potential theories.   We can never be 100% certain of anything.  It is always possible that tomorrow we will discover that our entire existence is some kind of long con -- a simulation, maybe, running in a tiny corner of a vast data center built by some unfathomably advanced alien civilization, and the only reason that the laws of physics appear to be the same from day to day is that no one has bothered to update our software.  But who knows what tomorrow may bring?  Maybe you or I will live to see the upgrade to laws-of-physics 2.0.

But I'll give long odds against.