Simple Algorithms and Exponents

What do Bitcoin, TCP, and retries have in common?

They all employ some simple form of exponential growth (or decay) in their operations.

Bitcoin

There are a ton of fun little algorithms hidden within Bitcoin.

• Proof of work - the act of mining is simply taking the contents of a block, hashing it against a random number, and hoping that the result of this hash is smaller than some target number. This takes a lot of work, and on average, only one computer finds such a number every 10 minutes across the globe
• The difficulty adjustment - an ingeniously simple way of making sure mining continues to take 10 minutes on average, even in the face of additional mining power. After each block, the Bitcoin protocol looks at the time it took to mine the previous 2016 blocks (2 weeks), and if this trailing average drops, it decreases the target number proportionally, such that it becomes even less likely that any random number generate a valid hash. Or if mining power has left the network, it would relax the difficulty by increasing the target number.
• Merkle Proofs - a data-light way to validate membership of a transaction in a particular block.

But probably the simplest one is the algorithm that governs Bitcoin's scarcity. Every 210,000 blocks (just a shade under 4 years), Bitcoin's mining reward gets cut in half.

This exponential decay in the increase of Bitcoin's supply means that there is an asymptote. The maximum number of  Bitcoin that can ever exist ist 21 million. All thanks to a dead simple "let's divide by 2 every 4 years".

TCP

TCP uses both exponential growth and exponential decay to find a globally acceptable rate of transmission. I find TCP to be an amazing protocol - it somehow avoids the tragedy of the commons (our computers don't overwhelm the underlying infrastructure) - but here's the kicker - without central coordination. It is a distributed algorithm that works!

A little backstory. Early on in the development of TCP, the original researchers were focused on producing a protocol that made sure that the two sides of a TCP connection didn't overwhelm each other. Well, more specifically, that the sender didn't overwhelm the receiver. This was (and is) done by agreeing on a "recieve window", which is the buffer size of the recipient.

Things worked well on the individual level and during inital tests, things looked great. Time to deploy!

But when they released this version of TCP, they noticed that as soon as lots of computers joined the network, the experience degraded for everyone. The early Internet became almost unusable.

In thinking only of themselves, the two sides of a TCP connection had failed to consider the shared resource: the underlying network that powers the Internet. Our researchers had to figure out a way to bake in awareness of the underlying network, without expensive central coordination.

They did that with two primary tools: packet loss detection and exponents.

They came up with "slow start" and "congestion avoidance":

• Start transmission at some slow rate. Double that rate of transmission if everything goes through. (exponential growth)
• Keep on doubling until packet loss is detected
• Now that packet loss is detected, cut the rate of transmission in half, and increase the rate linearly. Any time packet loss is detected again, cut the transmission again in half (sort of like exponential decay) and again linearly increase the rate

What's awesome about this is you get globally optimal behavior without sacrificing much on the local level. By making rational self limitations (cutting your usage in half only when you notice you've pushed the network beyond its limit), you maintain the health of the system.

This level of algorithmic contientiousness is beautiful to me. By focusing on yourself, but thoughtfully adjusting behavior the moment you sense that you're negatively impacting the larger community, TCP has allowed the Internet to flourish.

If only humans could be made aware the moment they've created negative externalities and be forced to adjust their behavior - then maybe selfishness could work 🤔

Retries

Despite the brilliance of TCP, when computers communicate with each other, there is no guarantee that the transmission will be successful. Sometimes, the underlying network will break down. Other times, the other party will simply fail.

In these cases, we need to reattempt our communication requests. Should we wait a minute? Maybe a random amount?

As a developer community, we've converged on utilizing exponential backoff. The reason is again contientiousness - an aggressive retry strategy can overwhelm the service under load, making a bad situation worse. Exponential backoff straddles the line between "giving them space", but "not giving up".

Conclusion

Hope you found these observations interesting. Perhaps it'll trigger you to think more about:

• Globally optimal, locally suboptimal scenarios
• Exponential growth and asymptotes

Whether you can apply them to your own life is beyond the scope of what I wanted to say. However, I do believe there is wisdom in simple algorithms.

Until next time.