My First Distributed System

I can show you a picture of the first distributed system I ever used:

(Not entirely accurate, I had a Game Boy Color.)

When I was a kid, we'd spend summers up at "the lake," where all kinds of fun stuff like swimming and boating would go on. Although I would mostly want to play video games.

A lot of the time, when I'd ask my friends up there to play video games with me, there would be a "let's go swimming." That was a good way to avoid doing pretty much anything you didn't want to do, or having conversations you didn't want to have. "Let's go swimming."

As it was in 2000, while not everyone was into video games, you know, abstractly, but everyone was into Pokemon.

"Do you have any cool Pokemon?" Asked the oldest of my friends. A boy a couple years older than me.

"Yeah." I said, with an upward inflection and my chin stuck out.

"Let's clone it," he said.

"You can't clone Pokemon," I said. I knew you couldn't clone Pokemon. I knew this because I had the Prima official strategy guide for Pokemon Red & Blue. I literally learned to read from this thing before I knew the games actually existed. It's still in my Mom's basement, barely held together. This was my bible. If you could clone Pokemon, I'd know about it, buddy.

"There's a trick," he told me. A "trick" was tantalizing. The sort of thing you learn on the playground after school from seedy ten-year-olds. The street smarts they won't teach you in Prima's official strategy guide.

"You have to turn off your Game Boy in the middle of the trade," he said. "Then you wind up with two copies of the Pokemon."

He wanted a copy of my Mewtwo. I had known where to get Mewtwo because I had read Prima's official strategy guide, and he hadn't heard of Mewtwo at all. I guess that's the difference between street smarts and book smarts.

We started a trade, for my Mewtwo and for his, I don't know, crappy Caterpie or something. We traded, and when the message came up that the game was saving and that if there was one thing we shouldn't do, it was turn the game off, I turned off my game. When I turned it back on, I still had my Mewtwo and he, rather than having his Caterpie, also had my Mewtwo.

I was pretty surprised that this worked, because it's sort of hard as a child to imagine that people who could create something as incomprehensible and mysterious as a Game Boy couldn't also stop a child like me from exploiting it. It was my first exposure to seeing some of the cracks in the system. Not to mention I still had an emotional attachment to my Pokemon like they were real pets, and cloning them raised some kind of ethical dilemma that I, at seven, didn't have the tools to reason about.

An interesting thing about having some theoretical knowledge about distributed systems as an adult is that I now see how this is one of only a rather small handful of ways that trading Pokemon could work.

Two Game Boys connected by a link cable is fundamentally a distributed system, working off the definition that a distributed system is one that has to deal with partial failure. More precisely, the two Game Boys are trying to solve atomic commitment, where they both want to agree whether or not the trade has happened, and Game Boy A should now have Game Boy B's Pokemon instead of their own, and vice versa.

Going directly from the state of trade has not happened to trade has happened, atomically, on both Game Boys, is, in fact, impossible, since doing so would require a solution to the Two General's Problem.

Because of this, it's possible to find a point in time where a failure in communication causes one Game Boy to advance through the state machine of the trade and the other doesn't, meaning that for one Game Boy, the trade has occurred, and for the other, it hasn't.

Does this mean that cloning Pokemon is inevitable? No, actually! We can borrow other techniques from distributed computing to find other choices in the solution space that could be used here.

The way I think about the restrictions on atomic commitment implied by Two Generals is that as the participants in a system move through a state machine together, they can never move through it at exactly the same pace. But that doesn't mean we can't have some restrictions on how they move through it. We can ensure for example, that they can be at most one state away from each other. This is easy to enforce: in a state machine with three states 1 -> 2 -> 3, we can prevent participant A from moving to state 3 until it receives confirmation that participant B has made it to state 2, and vice versa. This means that we prevent the state where there are participants in states 1 and 3 at the same time.

The way this can be used to prevent Pokemon cloning is to add an additional state in between "trade has not happened" and "trade has happened:"

Think of this middle state as "escrow," where neither player can access either of the traded Pokemon. Now, since we can guarantee that the first and last states are mutually exclusive, no Pokemon cloning is possible.

From a design perspective, I suspect this is a better solution than the one that Game Freak actually used in the original Pokemon games. While it can result in both Pokemon being lost instead of at most one if communication fails in the middle stage (though you could add some recovery steps), it disincentivizes doing this kind of tomfoolery in the first place, probably reducing the risk of some child losing their Pokemon at all.

I lied to you, earlier, that we wound up with two copies of my Mewtwo. When I turned back on my Game Boy, I had a Caterpie. I asked my friend if he had my Mewtwo.

"Yeah," he said. "I've got it."

"Okay, trade it back, it didn't work," I said.

He put down the Game Boy. "Later. Let's go swimming."

Addendum

Last week's post received a couple of thoughtful responses.

First, Ryan Marcus noted that because SQLite does nested loop joins anyway, although the plan still makes reference to a correlated subquery, it's not really fair to say that this plan doesn't represent a decorrelation. I think this is valid!

The other objection was also about SQLite. Richard Hipp (yes, that Richard Hipp!) wrote to say the following:

There is a "documented bug" in SQLite such that a column named "INT PRIMARY KEY" is not really a PRIMARY KEY in the sense that it can contain NULL values and multiple rows can have a NULL value for that colum.  INT PRIMARY KEY is really just INT UNIQUE.  To make a true PRIMARY KEY, you have to say "INTEGER PRIMARY KEY" or "INT PRIMARY KEY NOT NULL" or "INT UNIQUE NOT NULL" or add the non-standard text "WITHOUT ROWID" after the close-parenthesis at the end of the CREATE TABLE statement.  Any of those work-arounds will do the job, but using "INTEGER" instead of "INT" is the preferred fix.

The bug is documented here:  <https://sqlite.org/quirks.html#primary_keys_can_sometimes_contain_nulls>.  The bug goes back to approximately 2002.  I decided to document it rather than fix it because by the time I discovered it (circa 2008) there were already countless applications in the wild that depended on the buggy behavior.

I wonder how SQLite would do in your "Sniff Test" if you change every instance of "INT PRIMARY KEY" into "INTEGER PRIMARY KEY"?

Sure enough, I was holding it wrong:

sqlite> create table ab (a integer primary key, b int);
sqlite> explain query plan select distinct * from ab;
QUERY PLAN
`--SCAN ab

So thank you Richard for the detailed response and history!