On Your Marks, Get Set, Coat!

My first journal paper was published early last week, marking a milestone in the winding forest path that is my PhD. The paper has some nice ideas and results I’m proud of, but — regrettably — the writing style and level of mathematical rigor needed for publication can make it pretty hard to decipher for anyone not familiar with our niche of computer science. I’m of the opinion that ideas are only useful if people can understand them, so to that end I’m going to explain this paper in a way that’s a bit less formal and academic. With a little effort, I think we’ll both learn something new here. (And if it’s still all Greek to you, I’ll happily answer questions you leave in the comments).

The Nickel Version (TL;DR)

The paper (whose title is mathy and unimportant) is all about programming futuristic, sci-fi materials that don’t exist yet to coat other objects in even layers as (relatively) fast as possible.

The, Uh, Dollar(?) Version

Let’s take a look at the paper’s title (emphasis added): “On the Runtime of Universal Coating for Programmable Matter.”

Runtime is a word we use to talk about how fast an algorithm is. As in many other aspects of life, faster is better and more efficient. So this paper is about how fast “Universal Coating for Programmable Matter” is.

Programmable matter broadly describes any kind of physical material that can change itself as a reaction to what’s around it without human interaction. It’s a bit sci-fi, but imagine a future in which roads fill their own potholes and cracks after wear and tear, clothes heal themselves from fraying and holes, or artificial cells isolate and neutralize malignant tumors in the human body. It sounds crazy and is definitely out there, but that’s what we’re talking about here.

Universal Coating is the action we’re trying to do. In this context, we mean “coating” like a coat of paint; we want to cover something as evenly as possible. (Nobody likes a lumpy paint job). “Universal,” as a math word, means that a technique works in many/all cases. Here, we’re talking about a single approach to coating that works no matter what the object to be coated looks like. (Which is pretty cool).

So, all together, this paper is about analyzing the speed of a particular approach to using futuristic materials for coating any kind of object in nice, even layers. (Ok, so even the one sentence wrap up is a mouthful). Also, a big thank you to Annie Carson for the great illustrations!

So How Does It Work?

I’m really glad you asked. Actually, I’m really glad you’re still here after that heavy appetizer of an overview; hopefully it didn’t spoil your appetite before our main course, which starts right now! Take a look at a simulation of the Universal Coating algorithm over on our lab site, and keep it open for the rest of this section so you can refer back to it.

We need a bit of terminology before I explain what’s going on with all those dots and colors. There are two main “things” in this algorithm. Thing 1 is the object, which is the cluster of dots with black circles in the middle. We’re keeping things nice and simple in this example by making the object a hexagon, but it can be essentially any shape you want (“universal”, remember?). Thing 2 is the particle system, which are all the other dots that move around and change color. “Particle system” is just the term we use for the programmable matter stuff we talked about before: we’re trying to coat the object with these particles.

In really broad strokes, the algorithm can be broken down into four major steps:

1. Get all the particles oriented towards the object using something like follow-the-leader. In the simulation video (0:00–0:02), this is when they all turn yellow. If you start at any yellow particle and follow its pointer to the next particle and so on, you’ll always end up at the object.
2. Coat the object’s first layer. This happens insanely fast in the video (0:01–0:02) but there are actually a couple particles that turn red and fill in the few positions on the object’s first layer that weren’t already filled. You can see them if you pause the video and drag the slider back and forth around 0:01.
3. Decide on a position to be the start/end of each layer. Choosing this marker position plays a big role in helping the particles learn when one layer is finished so they can start forming the next one. In the video (0:02–0:07), this decision process is shown with the line segments around the object changing colors. At 0:07, the particle occupying the marker position turns a light grey color.
4. Coat the object in more layers one by one until all particles have been used. The video (0:08–0:20) shows this quite clearly, with finished particles turning green. The grey line of particles growing from the object towards the bottom are the particles from Step 3 which mark the start/end of each layer.

And that’s it! Perhaps as a point of pride, I have to mention that — although simple to describe — this algorithm is really involved. One of the main difficulties is that each particle runs this algorithm individually, so instead of Steps 1–4 happening nice and sequentially, they can actually all happen at once. And… yeah, it’s as chaotic as it sounds. The good news is that, in a previous paper, our group proved this algorithm always works, no matter what. Going forward, we’ll just take the fact that it works for granted.

(Quick) Get Your Coat!

I can’t remember how many times I got in the car to go somewhere as a kid only to be sent back inside to get a jacket. Mom never said the “quick” part, but it was definitely implied!

We’re going to shift our discussion to the real work of this new paper: proving that our Universal Coating algorithm runs reasonably fast. Let’s start with a motivating example for why you might do this kind of analysis:

Pretend there’s a secret technique for earning $1,000,000. Maybe it even comes with a guarantee that it will always work. We might get excited about something like that, or at least want to know more. But what if we found out that no one knew how long it would take to work? Or even worse, what if the fine print said it would take more days than the number of atoms in the universe? Well. We might still be waiting for our payout long after inflation turns a million dollars into pocket change, the cows come home, and the sun expands to consume the earth.

The lesson to be learned here: we need to know both that an algorithm works and that it won’t take a ridiculously long time. So how do we analyze the algorithm’s runtime? There’s often more than one way to crack that coconut, but the techniques can get pretty involved. Even getting a mastery over the most fundamental techniques can take the larger part of most undergraduate Computer Science (CS) programs. (Fun fact: this side of CS doesn’t even have to involve programming, contrary to the popular belief that CS people are a bunch of tech support code monkeys. Yes, I probably can fix your iPhone. No, I didn’t learn that in school.)

To explain both why analyzing our particular algorithm was nasty and how we ended up doing it, I’ll use a quick allegory. Imagine a race between two teams: Team Red and Team Blue. Team Red works like a machine: everyone comes to practice and trains hard, they perform well in events, and — most importantly — they run in perfect lock step, starting together and finishing together. Team Blue, on the other hand, is more about the individual effort. They also perform well in events, but have a mix of sprinters, endurance runners, runners who like to stop and smell the roses, and so on. Some of Team Blue’s runners end up finishing really fast, while others take longer.

Our particle systems are, essentially, Team Blue. We don’t make any assumptions about how fast each particle works relative to the others, and it’s entirely possible that a particle can suddenly go faster or slower than usual without following a pattern. This makes it hard to figure out when the last Blue runner (or particle) will cross the finish line. So, instead of directly analyzing our system (Team Blue), we proved two things:

1. Team Red — a simpler version of our particle systems where everyone progresses through the algorithm at the same rate — runs “fast”.
2. Team Blue (our particle system) always runs faster than Team Red.

Therefore, as a nice logical result, Team Blue also runs “fast”. In fact, it’s entirely possible it even runs really fast!

Good Job Out There, Get Some Water

As a recap, we have an algorithm for programmable matter which coats objects of all shapes and sizes. We showed that this algorithm always works in an older paper, and that it runs pretty fast in this new journal paper. This runtime analysis boiled down to showing that a simplified version of our particle system runs the algorithm quickly, and that the real particle system always runs it even faster. (For my CS people out there, we showed that the Universal Coating algorithm runs in $\mathcal{O}(n)$ asynchronous rounds with high probability, where $n$ is the number of particles in the system).

Thanks for reading, and feel free to comment with your thoughts, ideas, and questions!