Anecdote: In 2022, while visiting San Francisco, I had the chance to explore the campus. Wandering through the quiet, empty halls of the summer buildings, I was just about to leave when I unexpectedly came across Knuth's office [1]. I had to do a double take—it was surprisingly small for someone of his stature. Yet, in a way, it felt perfectly fitting, a reflection of his unassuming nature.
It's public knowledge that he's a prof at stanford and publicly available directories can lead you to his office. Not to mention that he's famous enough that this is almost certainly not the first time someone shares a photo like this.
If it was a photo of his home I'd understand but this is essentially public knowledge.
On my off hours, I’ve been working through volumes 4A and 4B. They are really wonderful, I highly recommend them. They’re not practical for the vast majority of programmers, but the way he designs and writes about algorithms is remarkable, truly unique. The Dancing Links implementation in 4B in particular (updated significantly from his famous paper) is like a work of art, it’s such an intricate and gorgeous data structure, and blazing fast as well. Man still got it, in his 80s.
Back in 2010 when we were building Amazon Route 53, we had a really big problem to solve. DDOS attacks. DNS is critical, and it uses UDP, which is a protocol that allows attackers to spoof their source IP address. We knew that DNS services are a common target for attacks from botnets; and our research at the time showed that our established competitors used large and expensive "packet scrubbers" to handle this.
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.
These are the kinds of stories I love from HN! Stories of theory meeting practice are my absolute favorite.
My dad got me a set of TAoCP a few years back as a birthday gift (before 4b) and I realized that I do not have the background to even begin on 1 (at least not without some daily devotion of time). Maybe I'll have to take some more time and try again.
Utterly unrelated to Knuth, and probably not useful for picking DNS servers because of their more static nature, but you might enjoy Ceph's CRUSH load distribution algorithm. Very rough gist: you can use it to e.g. set policy to avoid two replicas in the same rack, and ensure third replica goes on a different floor. And you can express server overload to migrate data off of one gradually, etc. Ceph uses that, with servers gossiping about failures & overload, to have clients directly contact the right servers.
> 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...
It's frankly unbelievable how frequently this happens. "Swimming around" in these concepts inspires solutions that otherwise seem to come from nowhere.
Hehe, I also got the box set at a huge discount when 4B came out. Amazon took their sweet time (and I had to confirm I didn't want to cancel the order), but they came through and I got my box set. It will be my son's graduation present.
I was not aware of an update to this algorithm, I'll have to look it out.
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).
I cannot recommend checking out Volume 4B enough, then. He goes much deeper, improves the algorithm, adapts it to different constraint problems, and provides hundreds of really cool exercises (including word problems like crosswords, I think). It's the best.
Yes that's the one ! I found it when I was trying to solve the tetraminos in The Talos Principle without looking for a game guide... I agree with OskarS it is a rewarding algorithm to implement.
I have made an implementation of the original Dancing Links algorithm, but for some large problem, more than a million rows and 104 columns with an average of about sixteen positions per row, it is killed because it takes too much memory.
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.
It does improve memory usage! In the version in the paper, each item has four links, in the book version they only have two. So memory usage is roughly cut in half.
From a rough estimation, it should not run out of memory with these constraints. The matrix should be about 1m rows * 16 cells/row * (4 pointers/cell + overhead?) * 8 bytes/pointer = approx 1 GB. That's quite little.
The dynamic memory is negligible with 104 cols, avg search depth should only be around 104/16.
How did Dancing Links change from the paper? When I implemented it I could not see anything that could possibly be changed, so any improvement would be surprising and wonderful to me.
You know in the sparse matrix, every item has four links (left, right, up and down)? In the version in the book, each item only has two links, up and down. The left/right links become implicit, because he stores the items contiguously in an array (so right of item 14 is item 15), and inserts "spacers" so you know when a row ends and the next one begins. This doesn't algorithmically improve the runtime, but it uses half the memory and gives it much better cache behaviour (btw: this is sometimes a charge levied at Knuth, he only cares about algorithms and not practical runtime when it comes to things like cache coherency. This is ludicrous, as this example shows.)
That's the change to the "basic" algorithm, but he then goes on to add a bunch of new features to basic Dancing Links, modifying it so that it's suitable for different kinds of constraint solving (adding required rows, things like that).
If you've implemented Dancing Links in the past, you owe it to yourself to check out the book version! He also has hundreds of really great exercises about it.
I feel that there is no good answer to this. For me It is more about the parts of the solution than the big problems. Some of the big solutions stay but it is mostly how you fit things together that stays with me. Everyone works differently here, e.g. I tend to reuse lots of things other people reimplement them there are drawbacks with both types of learning. I read a lot of code.
I was in San Francisco a few years back and I was amazed to learn that Donald Knuth not only still lives, but it still giving these once a year lectures in Stanford. Going there, finding the right building in the university, and then seeing this man speak about things I could only barely follow gave me such a memorable evening. What a legend Donald Knuth is.
Knuth is also still reviewing TAOCP-related email and issuing reward checks. A teammate received a reward check for 1 hex dollar last month after finding an error in Seminumerical Algorithms. Along with the check, there was a printout of the original email with hand-written annotations.
Some of the checks added up to quite a bit more than that (if there's ever another error check for TeX it will be for $327.68), and one notable at a TeX User's Group conference stated that he had cashed a check for $40.96 and was grateful to DEK for it, since it put food on his table when he was a poor starving grad student.
The thing I find most inspiring about Donald Knuth is his decades long commitment and discipline. As a serial project, language, and distro hopper, I have a lot I could learn from him
He’s dressed in something very vivid and lively, which kind of looks like the sort of world/ethnic dress you had in villages back in the day, but I can’t tell whether is Iranian or Slavic or where in between…?
I can't find the source, but I remember seeing him wearing this at another talk and him explaining that it was a hand made and stitched shirt inspired by a native group he had had some interaction with. The memory is really fading, may have involved his wife too. I can't find it, but there is an explanation out there somewhere. He wears it a lot at talks he's done since mid-2010s, it seems.
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.
Donald's novel "Surreal Numbers" was written during one week of a long stay in Norway [0]. So, maybe there he got his admiration for traditional Sami clothing.
Very surprising and disappointing that nobody at Stanford could get it together on the sound recording end to give this the clarity is deserves. It sounds like it was recorded on a dictaphone in someone's pocket. I'm not talking about Knuth's old-guy voice; listen to how bad it is when he stops to take an audience question.
> During an interview, Osgood Perkins recalled a story from production where he learned Nicolas Cage has a particular skill that he says no other actor possesses: the ability to recognize how high or low he is able to speak without messing up the audio. According to Perkins: "The sound guy came over to me one day...(he) comes up to me a couple of days into Nic being on set and he's like 'Oz, I've never seen anything like it. When Nic is mic'd, I'm watching the dials, when Nic goes big, he goes right to the line. Anything more, a decibel or two over that, and it would be hard to use. Then he goes down, he goes soft and his whispering and he's barely talking, he goes right to the line. Anything past that line, you wouldn't be able to use it. He knows where the lines are. It's the craziest thing I've ever seen in my life'."
Maybe Cage can contribute to the sound design problem actually.
I'm also incredibly grateful --- I was gifted a NeXT Cube by my brother-in-law when I was in college studying graphic design, and I was incredibly put out by the paucity of nice typography features in Quark XPress and Aldus Pagemaker when I came across TeXview.app and remembered checking out the book _TeX and Metafont_ from the local college library when I was a senior in high school --- built that into a career and a series of presentations at TUG conferences where I got to meet him.
From what I understand, TAoCP is building up to that compilers book! When initially tasked with writing about compilers, he realized all the background necessary for building them and planned out these books as an overview of computational techniques that would be helpful to use.
I once met Knuth and asked him why he thinks that P = NP. He answered something about the fact that approximation solutions bridge the gap. Never meet your heroes!
God bless whoever did the subtitles. Knuth's clarity of thought is unsurpassed, but, for me at least, actually hearing him speak is like the opposite of ASMR.
https://janvandenberg.blog/wp-content/img_1813-scaled.jpg
About the checks: I have not 1 but 2 checks. Small typos, nothing big: but wonderful to have these two documents.
reply