Donald Knuth's 2024 Christmas Lecture: Strong and Weak Components [video]

Not that anyone would, but I would be creeped out if I learned that people were posting pictures of my office without my knowledge.

(asking as someone who only recently started reading cs-related literature)

I wonder if the updated algorithm is using less memory.

My guess is that this large problem has about a hundred million solutions. So, even if it finds a hundred solutions per second, it still would require about ten days to finish.

The problem, I am working on, is the number of solutions to the 'Fancy Tetris Houten Puzzel' where all pieces of the same color touch are connected by at least one side touching another side of a piece with the same color.

I have been thinking about other algorithms for solving this Exact Cover problem that are less memory sensitive.

The original dancing link is one of my favorite papers, you can really see Knuth's love for algorithms (it's not in every paper you see sentences like "This process causes the pointer variables inside the global data structure to execute an exquisitely choreographed dance"). I'm using it to generate crosswords (the horizontal and vertical words forming an exact cover of the grid).

Does these make the material clearer or more hard to understand at this point of time?

We budgeted out what we think it would cost to handle our scale and the price tag came to tens of millions of dollars. You might think that would be no problem for a big company like Amazon, but our total infrastructure budget for Route 53 was something like tens of thousands of dollars. At the edge, we were re-using CloudFront servers that had failed hard drives for our name servers; since we wouldn't need much storage, and our API servers were pretty modest. We had a team of about ~6 people. That's what "scrappy" looks like at AWS; spend nothing, minimize downside risk, get things done quickly. There was no way I was going to ask for tens of millions of dollars for packet scrubbers. Besides, they would take too long to arrive, and would make us too reliant on a vendor.

Early on we had decided to run Route 53 name servers on its own dedicated IP range to give some measure of isolation. We could use dedicated network links to make sure that Amazon's other infrastructure wouldn't be impacted. But that wouldn't help Route 53's customers from sharing fate with each other. We didn't have a real plan beyond "When it happens, get really good filtering using our existing network and system tools".

Early that summer, I was reading one of Knuth's recent fascicles for 4A and was swimming in combinatorial algorithms. One night it just "clicked" that by creating many virtual name servers, we could easily assign every customer to a unique combination of four of those virtual name servers. We could even control the amount of overlap; some quick math showed that we about two thousand name servers, we could guarantee that no two customer would share more than two name servers. That number is important because our experiments showed that domains resolve just fine even when two name servers are unreachable, but beyond that it starts to be a problem.

The recursive search algorithm to assign the IPs was inspired directly by the algorithms in 4A; it gives customer domains two more independent dimensions of isolation. They also get 4 name servers from 4 independent "stripes", which correspond to the different TLDs we use for the name server names (co.uk, com, net, org). This guarantees that if one of those TLDs has an issue (like a DNSSEC mistake), only one of the name servers is impacted. They also come from 4 independent "braids", which can be used to ensure that no two name servers share certain network paths or physical hardware. I just wouldn't have known how to do any of this without reading 4A. And I even have a background in combinatorials; from statistics and cryptography.

I've never been more excited by a solution; this approach gave us provable network IP level isolation between customer domains while costing basically nothing in real infrastructure. It's math. It wasn't completely free; we had to use 2,000 anycast IP addresses, and it turns out that we also had to register 512 domains for them because of how many TLDs require name servers to be registered and to have glue records; so that was a fun process working with our registrar. But we got it done.

I named the approach "Shuffle Sharding", and it's more discovery than invention. Many multi-tenant systems that use some kind of random placement get a kind of shuffle sharding, and network filtering techniques like Stochastic Fair Blue use time-seeded hashing to similar effect. But I've never seen anything quite the same, or with the level of control that we could apply; I could even extend it to a kind of recursive nested shuffle shading that isolates at even more levels. For example if you want to isolate not just a caller, but a caller's callers when they are in some kind of "on behalf of" call pattern.

Years later, I made a personal pilgrimage of gratitude to see a Knuth Christmas lecture in person, and sat in the front row. I still read every scrap of material that Knuth puts out (including the Organ pieces!) because I never know what it might inspire. All of this to say ... I do think his volumes are surprisingly practical for programmers; they broaden your mind as well as deepen your understanding. What more could you want.

Incidentally I was next to him as he was trying to stand on a window ledge to get sight of the Olympic torch coming into the square in front of Manchester Town Hall in 2012. I spoke to him, and reached out for him for a moment as I thought he was about to fall through the window, but he was all good. He came across as a very curious man, bright with questions and intelligence and younger than his years.

We were both attending an event celebrating the centenary of Alan Turing, and I was surprised to find myself in a room with him, Gary Kasparov, Fred Brooks, Vint Cerf and many other luminaries of computer science. The Olympic torch came into the square outside during a lunch break, and he just couldn't help but take a look - he was the only there who seemed excited about it. He gave a talk at the dinner that night, and I saw him again in Manchester on another date when 4B had just been published, and he vaguely recognised me from the previous event when I asked him to sign it.

I recount this story, because I think his shirt hints at a much more eclectic and curious mind - I definitely have seen evidence of it in other places.

[0]: https://youtu.be/jB0aeePskBg

https://www.youtube.com/playlist?list=PLoROMvodv4rOAvKVR_dyC...