Exponential Backoff

Exponential Backoff: The Algorithm of Forgiveness

The world’s most difficult word to translate has been identified as “ilunga,” from the Tshiluba language spoken in south-eastern DR Congo.… Ilunga means “a person who is ready to forgive any abuse for the first time, to tolerate it a second time, but never a third time.”

—BBC NEWS

If at first you don’t succeed, / Try, try again.

—T. H. PALMER

Today we expect our devices to communicate wirelessly even when wires would be easy—our keyboard and mouse, for instance, talking wirelessly with a computer sitting inches away. But wireless networking began as a matter of necessity, in a place where no wires could do the job: Hawaii. In the late ’60s and early ’70s, Norman Abramson at the University of Hawaii in Honolulu was trying to link together the university’s seven campuses and many research institutes, spread across four islands and hundreds of miles. He hit upon the idea of implementing packet switching via radio rather than the phone system, connecting the islands with a loose chain of transmitters and receivers. This system would come to be known as the ALOHAnet.

The biggest hurdle that the ALOHAnet had to overcome was interference. Sometimes two stations would transmit at the same moment, inadvertently jamming one another’s signals. (This is, of course, a familiar feature in human conversation as well.) If both stations simply retransmitted right away to try to get their message across, they’d run the risk of getting stuck in perpetual interference forever. Clearly the ALOHAnet protocol was going to need to tell competing signals how to give each other space, how to yield and make way for one another.

The first thing that the senders need to do here is what’s called “breaking symmetry.” As any sidewalk pedestrian knows, dodging right as an oncoming walker dodges left, and then having both of you simultaneously dodge back the other way, doesn’t solve anything. It’s the same story when two speakers both pause, make gestures of deference to the other, and then start to speak again at the same time; or when two cars at an intersection, each having stopped to yield to the other, try to accelerate in sync. Randomness gives these senders a way to break their synchronized pattern of retries.

One straightforward solution is to have each station flip a coin. Heads, it retransmits; tails, it waits a turn, then retransmits. Surely one of them will get through uncontested before long. This works well enough when there are only two senders. But what if there are three simultaneous signals? Or four? It would take a one-in-four chance for the network to get even a single packet through at that point (after which you’d still have three conflicting stations left, and perhaps even more competing signals arriving meanwhile). As the number of conflicts increases further, the network’s throughput could simply fall off a cliff. A 1970 report on the ALOHAnet said that above a mere 18.6% average utilization of the airwaves, “the channel becomes unstable … and the average number of retransmissions becomes unbounded.” Not good.

The breakthrough turned out to be increasing the average delay after every successive failure—specifically, doubling the potential delay before trying to transmit again. So after an initial failure, a sender would randomly retransmit either one or two turns later; after a second failure, it would try again anywhere from one to four turns later; a third failure in a row would mean waiting somewhere between one and eight turns, and so on. Spreading retries over a growing interval reduces repeated collisions, though it does not remove the channel’s capacity limit. Since the maximum delay length (2, 4, 8, 16…) forms an exponential progression, it’s become known as Exponential Backoff.

The account traces Exponential Backoff through the ALOHAnet beginning in 1971 and its incorporation into TCP in the 1980s. As one influential paper puts it, “For a transport endpoint embedded in a network of unknown topology and with an unknown, unknowable and constantly changing population of competing conversations, only one scheme has any hope of working—exponential backoff.”

The same pattern can be used for failures beyond collisions. A client retrying an unavailable service, for example, can wait progressively longer between attempts. This is good for everyone: it prevents a host server that’s down from getting slammed with requests as soon as it comes back online, and it prevents your own machine from wasting too much effort trying to get blood from a stone. The backoff rule sets the delay; a separate retry limit or deadline determines whether the client gives up.

Increasing delays after failed login attempts can slow a “dictionary attack” that cycles through possible passwords. The delay rule alone does not guarantee account security or determine whether a legitimate user can recover access. Lockout limits and recovery procedures are separate design choices.

In human society, we tend to adopt a policy of giving people some finite number of chances in a row, then giving up entirely. Three strikes, you’re out. The authors suggest considering an alternative: space out further attempts instead of choosing immediately between constant retries and stopping forever.

A friend of ours recently mused about a childhood companion who had a disconcerting habit of flaking on social plans. What to do? Deciding once and for all that she’d finally had enough and giving up entirely on the relationship seemed arbitrary and severe, but continuing to persist in perpetual rescheduling seemed naïve, liable to lead to an endless amount of disappointment and wasted time. Solution: Exponential Backoff on the invitation rate. Try to reschedule in a week, then two, then four, then eight. The rate of “retransmission” goes toward zero—yet you never have to completely give up.

Another friend of ours agonized about whether to offer shelter and financial assistance to a family member with a history of drug addiction. She couldn’t bear to give up hope that he would turn things around, and couldn’t bear the thought of turning her back on him for good. But she also couldn’t bring herself to do all that it required to have him in her house—buying him clothes and cooking for him, reopening bank accounts for him, and driving him to work each morning—when at some mysterious and abrupt moment he would take all the money and disappear, only to call again several weeks later and ask to be forgiven and taken back in. It seemed like a paradox, a cruel and impossible choice.

The authors propose increasing the period of sobriety required before offering another stay. That is their suggested boundary for this example, not a result established by the networking algorithm. The host’s willingness to remain in contact and the conditions for sharing a home are separate decisions.

The book also draws an analogy with HOPE, a probation program that began in Honolulu, where the ALOHAnet originated. Its discussion concerns the program as described at the time of writing.

Shortly after being sworn in to Hawaii’s First Circuit Court, Judge Steven Alm noticed a remarkable pattern. Probationers would repeatedly violate their probation terms, and circuit judges would routinely use their discretion to let them off with a warning. But at some point, perhaps after a dozen or more violations, the judge would decide to be strict, and assign the violator a prison sentence measured in years. Says Alm, “I thought, what a crazy way to try to change anybody’s behavior.” So Alm proposed almost exactly the opposite. In place of violation hearings scheduled a long time into the future, requiring uncertain judgment calls, and occasionally producing huge penalties, HOPE is based on immediate, predefined punishments that begin with just one day in jail and increase after each incident. The source cites a five-year Department of Justice study reporting that HOPE probationers were half as likely as regular probationers to be arrested for a new crime or have their probation revoked. And they were 72% less likely to use drugs. At the time described, seventeen states had launched versions of HOPE. The escalating penalties in this account are not shown to follow an exponential schedule.