Friday, February 17, 2017

Theseus: A Robust System for Preserving and Sharing Research

Suddenly, in the space of a few weeks, I discovered what appeared to be definitive answers to the problems which had baffled me for years … I went about saying to myself that now at last I had done something worth doing, and I had the feeling that I must be careful not to be run over in the street before I had written it down.
 -The Autobiography of Bertrand Russell

The Promise

Recently, American scientists have been engaged in an effort of unprecedented scope to back up as much climate data and research as they can get their hands on. In the hours surrounding the presidential inauguration, groups of hackers and activists rushed to back up this data on European servers. These groups fear censorship of climate research by the incoming administration, and rightly so. Currently, governmental censorship of science is more than a hypothetical concern.

It's inspiring to see this level of mobilization, but horrifying that it is necessary. The need for this action reveals that we have built an infrastructure that's vulnerable to attack at many levels. We have found that our top scientific institutions can be silenced if the administration dislikes their findings. We have found that certain political groups believe they can shape reality through misinformation and censorship. And we have found that we, the people, have very little in place that's equipped to push back.

It doesn't have to be this way.

Imagine a system with the reference features and massive scope of the modern scientific paper repositories -- arXiv, Embase, et al. -- but completely decentralized and peer-to-peer. The processing power required for all of the system's features, including searching for and downloading papers or data, would be shared across all the network's participants. Anyone with an internet connection could join and use a friendly web interface to immediately access anything stored in the system. They would also optionally be able to volunteer their own spare storage space, CPU power, or network bandwidth to help keep the system healthy.

This is very close to the model used by BitTorrent, and if BitTorrent's success is any indication, this model can lead not only to remarkable download speeds but also to resilience in the face of attempted censorship, even by state-level adversaries. No central server means no central point of failure.

What I'm laying out here is the outline of such a system for sharing important documents on any subject its users consider valuable. The system relies on its nodes to redundantly back up, index, enumerate, and supply the data it tracks. The system also includes support for searching for papers in a variety of ways. Every part of the system is designed with a strong, explicit focus on security and privacy.

I'm calling it Theseus.

I believe that the following promises can be made:

  1. A guarantee of robustness in the face of censorship. Decentralized services are very difficult to bring down, especially if they have nodes in multiple countries. Skeptical? Just ask the music industry.
  2. Guarantees of anonymity for users who need them. This goes for file uploads, file downloads, searches -- you name it. This is a big one, and I'll go into more detail on ways it could work below.
  3. The ability to quickly search for papers on any topic. This is also a big one. There are not very many good tools for browsing research papers, and I believe this system could provide functionality meeting or exceeding what is offered by the current gold standards.
  4. The ability to securely share your own research. You could digitally sign and upload your own research and have it immediately backed up and indexed by your peers. The digital signatures involved in this scheme also prevent any ne'er-do-wells from trying to pass off modified versions of your work as authentic. The interface would be designed to make this all as simple as possible.
  5. The (potential) ability to sidestep thorny copyright issues. I am not a lawyer. Nothing in this blog post is legal advice, because legal advice is something I am not qualified to give. However, from my lay understanding I am optimistic about this tool's potential for circumventing restrictive laws and promoting freedom of information in the sense advocated by greats like Aaron Swartz.

What follows is a broad-strokes description of what I have in mind. You'll notice it's light on things like protocol details. This is intentional. While there will certainly be posts dedicated to specifics and minutiae in the future, for now I'm trying to stay focused on the big picture in order to try and lay out the driving vision behind Theseus as clearly as possible.

The Ideas

There are several key ideas here, a couple of which have already implemented as stand-alone features in various P2P clients.


First off, it's critical to realize that a distributed peer-to-peer network can do more than just share files. You could share metadata, share file listings, and even perform operations unrelated to filesharing, like conducting searches. The only restriction is that you're running on (essentially) borrowed CPU cycles and thus should try to minimize overhead, preferably keeping it comparable to the overhead of seeding a file. This is just to avoid any impact on overall system performance as a courtesy to the user.

This is where the most prior work exists (as far as I know). There exists, for instance, a BitTorrent client with the special feature that it can conduct decentralized keyword searches for torrent files. There's another client designed to carry out approximate-match decentralized keyword searches. And by now, practically all modern BitTorrent clients are able to interface with "Mainline DHT", a distributed hash table maintained by the BitTorrent peer swarm. All of these work using overlay networks on top of the basic BitTorrent P2P network. All of them have seen great success with this approach.

Automated Seedboxing

Something important to realize is that the life of a torrent lasts only as long as its seeders do. If nobody will seed a file, then that file is effectively gone forever. This is rarely a problem for popular torrents -- you'll always be able to find people to seed TV episodes or games or porn -- but for files that might not necessarily draw interest immediately, or which interest a smaller group of people, the situation can be more dire. These files often require their original provider to seed for a long period of time -- sometimes indefinitely. The critical realization here is that while this is how things are, it is not how things need to be. What if some peers volunteered a certain amount of their own storage space to keep unpopular but important torrents alive?

There are many wrong ways to implement such a system. It's not hard to imagine attackers flooding these peers with garbage torrents, forcing the altruistic clients to try to somehow guess what to keep and what to discard. It's also easy to imagine the system getting clogged up by large files like (say) high-resolution rips of very long movies. How would the system know to prefer backing up climate research over backing up these? The best solution I have so far is to use digital signatures as a way of endorsing certain torrents, and to leverage a web of trust.

The idea is, essentially, to only acquire (and subsequently seed) torrents endorsed by people you trust. Endorsement would be indicated by signing a torrent's magnet link. Suppose you were a climate scientist. You could publish a public key and use it to sign magnet links for papers you consider significant (including, but not necessarily limited to, your own work). Then, sympathetic strangers from around the world could import your public key and offer to download and seed torrents signed by said key, with priority given to those which have low numbers of seeders and/or which have only recently been introduced to the network.

These sympathetic souls would likely want features like filesize caps, caps on number of torrents per key, etc, in order to keep storage costs manageable. All of these would be easy to implement and totally compatible with the goal of the system, since research papers do not take up much disk space at all.

You can think of these volunteers as running specialized, automatically populated seedboxes. I find it easy to imagine that there are enough generous souls with spare CPU cycles and terabyte hard drives in the world to maker this sort of scheme work.

As for how the signatures would be distributed, that is a good question and I'm not yet concretely committed to any one solution. There are a number of interesting options available here, which I'll try to explore in a future post. The problem is made slightly easier by the fact that signatures take up very little space on disk.

The web of trust could come into play if a user finishes downloading all low-seed-count torrents endorsed by anyone they trust and still has volunteered storage space left over. Rather than letting that extra space sit empty, the service could start expanding out from the set of trusted keys, identifying those keys' trusted keys and in this way finding new, slightly lower-priority files to download and seed.


Another major issue is ensuring privacy through anonymity, and some good ideas have been developed that could be useful here.

First, the bad ones. The classic solution is to use a VPN. This is fine against weak adversaries but unacceptable against nation-states. Another is to try to route your traffic through Tor. This is rightly frowned upon by the Tor community because it doesn't work very well and has a real impact on network performance.

A third solution is to do something similar to what the Tribler torrent client has done and implement a dedicated Tor-like network on top of the P2P overlay network they already have in place. This has some significant advantages: it lets you get some of the best properties of Tor without taxing the actual Tor network. It also has a disadvantage in that this network is smaller and less thoroughly tested. Traffic correlation attacks are usually more viable on smaller onion-routing networks like this one, and such networks are also more vulnerable to Sybil attacks. Nevertheless, we do know (thanks to the Snowden leaks) that Tor is one of the few things that actually gives the NSA et al. some trouble, and so it's tempting to adopt a Tor-like model if possible.

My inclination at this point would be to carry out a careful audit of Tribler's system and, if it passes muster, to try to either plug into it (if the developers are amenable) or else emulate it (if they aren't). Tribler also includes provisions for "anonymous seeding", which if effective would be very attractive, especially for authors who want to upload works of theirs whose copyright they no longer hold, perhaps due to the coercion of an academic publisher.

I do have some reservations about leaning too heavily on Tribler for this part of the design, though not due to any negative judgment of their design or code base -- in fact, so far I've been pleasantly surprised by the scope of their documentation. I'm optimistic about the possibility of drawing on some of their features. It's more that with security in mind I'm withholding endorsement until I have a chance to more thoroughly review their code and protocols. It's also worth noting that the Tribler team themselves are enough of a class act to be upfront and warn against trying to use their system to defend against "spooks and government agencies," since they claim not to currently be able to provide that level of protection.

Another possibility to consider is the use of mixnets. There are huge numbers of both advantages and disadvantages to using mixnets as opposed any of the other options proposed here. This is a hard decision that I may end up writing a future post on. For now, suffice to say that I currently favor the idea of constructing a Tor-like network a la Tribler, but that the idea of using a system based on a mixnet architecture is not completely off the table. The primary concerns motivating the final decision will be thwarting traffic analysis attacks and reducing as much as possible the potency of Sybil attacks.

Web Interface

Another idea is to present the tool through a web interface, rather than a dedicated desktop application. This idea is significantly less abstract than most of what's being outlined here, and for good reason. The motivation behind using a web interface is to make the average user feel more comfortable learning the system. If this tool is going to be useful, it has to be usable by non-specialists who might be intimidated by the prospect of learning a whole new desktop application. But a web site? At this point, most people can figure those out. So, my intuition is that a web interface would be easier for people to learn than a whole stand-alone GUI application.

Of course, the client would still run as a native stand-alone application. This application would start, immediately background itself, drop an icon in the system tray, quietly carry out its duties, and serve up the web interface over localhost.

A side benefit of using a web interface is that it would encourage the opening of downloaded files within a web browser whenever possible, rather than within a local program. Security-minded readers might be raising an eyebrow at the idea of this being a benefit. For these readers let me put it this way: which do you think has better sandboxing, Chrome or Adobe Acrobat? And let's not even mention the horde of ill-tested 3rd party PDF readers that people would use if left to their own devices.

There's not really any good choice for PDF viewing right now (which is incredible in and of itself). My suspicion is that putting all this in the browser is probably our best bet at this point in time. This is an issue I'd be particularly interested in hearing reasoned counterpoints on. It's also worth mentioning that users who strongly mistrust the browser could still configure their system to open PDFs or other file types in dedicated applications.

It's also worth noting that the average user is probably familiar and at least reasonably comfortable with their browser's PDF viewer, which slightly reinforces the usability argument made above.

The first iteration of the interface will probably use Bootstrap. That's subject to change as soon as I can rope in anyone who knows more about web design than I do. If that sounds like you and you like what you're seeing here so far, consider this your invitation to get in touch.

Chat & Other Social Features

My end-goal for this system is twofold: First, to create a way to reliably distribute critical information such as climate research which enables both its redundant storage across the world and its easy retrieval by anyone; second, to create a tool which, by referencing this distributed network, enables individuals to conduct world-class research in any field of their choosing. This applies as much to climate science as to computer science as to local housing policy. The pursuit of this second goal requires considering certain ideas which might, from the perspective of the first goal, seem frivolous. One of these is chat. If peer-to-peer communication channels are established, it seems like end-to-end encrypted chat is a natural thing to layer on top of them.

Obviously chatting with strangers is risky, and in my mind the risk of user compromise through social engineering is high enough to be prohibitive. However, since the system already involves key distribution, it's interesting to consider the possibility of users who have already established trust for each other mutually authenticating via public key and then carrying out encrypted chat. Impressive and time-tested protocols like OTR exist which could be tunneled through the native communication channels of the system's overlay network. This could facilitate secure communication between e.g. research collaborators.

Other, related ideas like the ability to tag a torrent to facilitate searching, the ability to leave comments on a document and share them with trusted peers (or with the world), or the ability to record citation lists (potentially with magnet links included), would also be worth exploring down the road. Some time soon I'll probably dedicate a blog post to discussing the possibilities here. I'm very excited by the amount of potential here.

The Ecosystem

I'm incredibly encouraged by what's already out there in the BitTorrent ecosystem. When I first conceived of this system, I spent a good deal of time coming up with ways to implement every part of it from scratch. Only later did I sit down to do some research -- and to discover that working implementations and quality publications exist for many of the components I thought I'd invented. (I have yet to find any prior work on the automated seedboxing component, though if anyone could cite some I'd be very interested to read up on it.) It's hard to describe how exciting this is, since it means there's a wealth of prior work that can be drawn upon in developing this system.

What surprises me is that these incredibly useful capabilities haven't already been synthesized and packaged into an easy-to-use, secure-by-default application for general use. It's remarkable the degree to which modern development has migrated away from inventing new algorithms or protocols and towards different methods of plugging discrete, pre-existing systems together in new and novel ways. This is where the real power of open-source software is on full display, since it both makes quality code available for this use and fosters the development of communities to support its maintenance and extension.

The Future

I'm planning to start work on Theseus immediately, and to devote as much of my free time to it as possible. If you like the sound of what you just read, please feel free to get in touch. Let's work together.

As I emphasized near the start of this post, we live in interesting and, for many people, dangerous times. Major world powers are refusing to acknowledge scientific facts backed by more than a century of consensus. The Internet has, and has always had, tremendous promise for promoting the freedom of information, but early assumptions about the specifics of its utopian nature have almost all proven to be overoptimistic.

In the '60s, Stewart Brand famously said that "information wants to be free." Cory Doctorow, in his outstanding book Information Doesn't Want to Be Free, plays with the idea of updating the slogan: "Information doesn't want to be free; people do."

In the early '90s, John Gilmore suggested that "the Net interprets censorship as damage and routes around it." Early cypherpunks, crypto-anarchists, etc., all seemed to agree -- and it is perhaps telling that the relative size and influence of these groups has dwindled as the internet has matured. The trend says, I think, less about their philosophies and more about how the easily subverted, default-insecure nature of the modern internet has failed to realize the potential they saw.

As a result, I feel about Gilmore's quote much the way Doctorow feels about Brand's: I very deeply respect the sentiment behind it, but I find it has a certain optimism which ends up leaving important things unsaid. After all, by itself the internet is fairly bad at routing around censorship, as projects like OpenNet have demonstrated. It's more that we can build technologies on top of the Internet which address and compensate for their substrate's inherent inadequacies.

Put differently: the Net doesn't "interpret censorship as damage and find ways to route around it." We, its users, do that. We do it by finding new, more resilient ways to use the internet -- ways that can repair this damage of censorship -- and by making these new technologies as widely available as we can.

The way I see it, the situation we are currently in is very simple. Some of the most valuable aspects of this sacred, world-changing space are existentially threatened. It is our civic responsibility to do everything we can to protect and strengthen them.

Saturday, January 21, 2017

If Freedom of Speech Is Your Best Defense, You Have a Problem

Let's keep this short and sweet. I love freedom of speech at least as much as the next person. Possibly more. Back in high school my civics teacher would, between classes, slip me publications on the First Amendment to study, because she'd noticed it was one of the only topics that consistently captured my interest.

Freedom of speech is still close to my heart, but lately I've been noticing that in this position I have some unpleasant company. Certain ascendant voices in our media are citing freedom of speech like it's some sort of talisman meant to protect them from criticism for the unmitigated vitriol they spew in every direction.

Let's make something very clear: Freedom of speech is necessary to any healthy modern society. It is a cornerstone. But if someone challenges you on what you're using it to say and your best response is, "I have freedom of speech!", then you're effectively saying you can't think of any better defense for what you're doing than "You can't make me stop."

This is not to say freedom of speech isn't important. It is colossally important, and it is important precisely because if you are free to say whatever you want, then in principle nothing is stopping you from saying what you feel to be most valuable. Freedom of speech gives you a chance to contribute to society's discourse just about anything can think of (with certain obvious exceptions for truly depraved shit). The hope is that given this freedom you'll try to find something positive to say and add something worthwhile to the world.

But, if in using this inalienable right you manage to get enough people mad at you that you have to defend yourself, and if when that happens all you can think of to say is, "well, it wasn't illegal", then you've got some bigger problems. To be specific: in the immortal words of the Dude,

Thursday, December 29, 2016

How to Lose at Mancala (Consistently!)

Over winter break, I spent a few days fiddling with a Mancala AI. It came together surprisingly quickly! Here's a little journaling on that project.

Background: Mancala is a fun, simple board game with a surprisingly high skill ceiling. I've never been very good at the game, but I've had fun playing it anyway. After a recent series of ruinous defeats at the hands of my own family I started thinking about what optimal game strategies might look like.

(Side note: It turns out Mancala is a solved game (i.e. it's known how to play "perfectly") for the most common numbers of stones or houses. I haven't looked at any of the relevant publications, but my impression is that they relied mostly on endgame databases and exhaustive search. That's no fun, so I'm going to ignore those results and try to build this project from the ground up. The goal is to write a program that can beat me at Mancala, and hopefully to learn a few things about the game from it.)

If you don't know the rules of the game, here's a quick overview of the variant I'll be writing about. I'll be calling the game pieces "stones", and the little areas they sit in "houses".

I opted to do this all in C because I had a feeling I'd need speed here and because I wanted more practice with the language.

You can find the Github repo here.

The Basics

My goal here was to start by writing a C framework and basic shell for playing Mancala. The idea is that if this is made modular enough, then the game logic can be tested through manual play, and down the road the code that prompts a user for a move can be swapped out for code that asks an AI the equivalent question.

Boards are represented through a struct:

typedef struct {
     char p1_store;
     char p1[6];
     char p2[6];
     char p2_store;
} board;

This struct is of course effectively just a char array, but it's still nice to have pointers into its various sections, both for convenience and for readability. The board will never have more than 4*6*2=48 stones on it, so there's no drawback to the limited range of a char. And in fact using chars rather than larger data types offers an advantage: their small size makes the struct easier to copy quickly.

There's just one gotcha: we haven't addressed the question of how to map this data structure to the physical board. There are three things we want to do with the board: print it, reference specific houses on it, and play moves on it. In printing it and referencing moves, it's convenient to think of reading off the state of the board left-to-right. But when you're playing out a move, stones progress counter-clockwise -- that is to say, left-to-right along the bottom and right-to-left along the top.

Thus, while it's possible to lay out memory so as to make either of these operations natural, the two are mutually exclusive. We have to choose which to bias the design towards.

The main consideration I used is that if we make move calculation easy but printing and indexing more difficult, then that introduces complexity to many parts of the program. Complexity just about inevitably leads to bugs.

On the other hand, if we make move calculation more difficult but printing and indexing easy, then we've encapsulated the complexity within whatever function handles playing a move -- a small function which'll be easy to rigorously test. The rest of the program avoids having to deal with this complexity as long as it trusts the validity of the move function.

The positioning of p1_store and p2_store (the "endzones" where players are trying to collect stones) was purely to simplify the logic of play_move, since nothing else really cares too much about where in the struct those elements are placed.

The "main loop" of the game is a function, play_game, which does exactly what it says on the tin. play_game takes three arguments: a pointer to a board struct, and two function pointers. These function pointers are meant to indicate two functions which, if passed the game state, will pick moves for players 1 and 2 respectively. Those moves are enacted on the board via play_move, which returns a MOVE_RESULT enum that is then used to provide helpful feedback and update the game state.

I'd never really played with function pointers before in C. They're really cool -- they feel like something that got smuggled into the standard, secretly backported from higher-order languages. If C also had a clean way to curry functions, I'm not sure I'd ever want for anything more.

The use of function pointers in play_game allowed me to start out with players 1 and 2 both played from user input. This manual operation was a good chance to verify that the basic guts of the mancala engine were working properly, and I caught a few bugs in the move function right away. Like I mentioned earlier, that was expected, and the whole setup here was designed to make those expected bugs as easy as possible to root out.

Their real utility, though, came when I decided to add my first shot at an AI to the game. All that's required to swap out a human for an AI is to write a C function with an identical signiture which implemented the AI desired and to change one line in main to pass that function instead of get_move. How's that for modularity?

The next step is to write an AI to play the game. That's where "losing consistently" comes in: playing yourself is great, but playing something else is better, and if the thing you've made to play against can beat you, then hey, that's all the better. My goal from the start is to make an AI that's good enough that it can beat me consistently.

Losing Consistently

The Idea

My first strategy is simple: a naive version of Monte Carlo tree search (MCTS). This is a solid go-to strategy for lots of kinds of games. All you need is to be able to simulate playing games out to their conclusions, logging who won as you go. If you have a working engine but don't have any real theory for the game and don't have a bulletproof way of evaluating positions mid-game, MCTS is a good way to get a basic AI working practically "for free". In spite of having such low requirements, MCTS is an incredibly effective strategy -- it's done wonders for many games, notably including Go. In fact, the AlphaGo system was built by using neural nets to provide heuristics for a (thoroughly non-naive) implementation of a similar algorithm.

In short, this is a strategy that gets results, especially in games with emergent mechanics. A full implementation of Monte Carlo tree search involves weighting different moves during the search to provide a basic heuristic for focusing on the most promising candidate moves. We'll start out without this: hence the "naive", since our heuristic will be the random function.

This naive approach probably won't work quite as well as a full MCTS implementation would, but it's much simpler to implement, so it'll make for a good starting point. Down the road, it'll also be interesting to compare this algorithm's performance to that of full MCTS.

Random Movements

Incidentally, here's something not a lot of people get right: how do you pick a random number between 0 and n in C? Most people would just use (rand() % (n+1)), but this introduces a slight amount of skew towards some numbers, which is unacceptable. Random number generation is at the heart of our algorithm. We need to avoid generator skew, or the algorithm will suffer.

I chose to encapsulate the complexity of this problem inside a function called pick_random_move. This function picks a move at random, while taking care to adjust for skew and to check that the move is legal. The function:

char pick_random_move(char side[]) {
    int divisor;
    int move;

    divisor = RAND_MAX/6;
    do {
        do {
            move = rand() / divisor;
        } while (move > 5);
    } while (side[move] == 0);

    return move;
} then polled by the NMCTS engine to get random moves. Notice that to switch from a naive heuristic to any other, all we'd have to do is swap out this function. More modularity at work. It's a pity we can't easily make this function an argument to the MCTS algorithm which could get curried in before passing the algorithm driver to play_game, but that's C for you.

Quick note about how the function works: RAND_MAX is a predefined macro giving the upper limit on the value of rand(). We want to map these values to values between 0 and 5, without skew. However this would only be possible if RAND_MAX is divisible by 6, and we have no guarantee that that is the case. So, we instead create an imperfect map from values of rand() to numbers between 0 and 6. The way we do this (integer division) guarantees that values 0-5 have the same probability of occurring, but has some skew in how often 6 shows up. We deal with that by just throwing out 6es completely -- repolling the RNG whenever we get one -- and returning on 0 through 5. And just like that, we have a reliable random number generator!

Where does this get us?

The Github repo already contains an implementation of the naive Monte Carlo tree search. It runs out a configurable number of simulations (defined by a preprocessor macro, NAIVE_MCTS_NUM_PATHS, which defaults to 200000) and picks the one which had the highest margin of wins over losses.

In each simulation, all moves are chosen randomly. That's all this thing does -- and yet it works. In aggregate, that strategy is already enough to identify which branches are promising and which are not. My suspicion is that this works because Mancala positions have an extremely low branching factor. This makes branch pruning less important than it would be in e.g. computer Go.

There's one more thing to address: how moves are chosen. There's a few different options here. You could go by the ratio of wins to losses, the ratio of wins to total games played, the integer difference between number of wins and losses observed... In full MCTS, the ratio of wins to games played is typically used, which makes sense since those ratios are also used to set the weights for the random move generation function. However, since we're using naive MCTS, complete with even move probability weighting, I opted instead to go for integer difference, just because it makes for simpler code and gives more or less the same choices on average.

The Github repo currently includes code for setting up both human and NMCTS players. It's even possible to pit the AI against itself (and it plays a pretty good game!). The code is decently well-commented, at least in my opinion, and has a bunch of optional, preprocessor-controlled debug print statements that also help to narrate what's going on.

Next Steps

The naive MCTS is not yet completely bug-free, and occasionally picks illegal moves. Hopefully I'll have that issue figured out soon. After that, my next goal is going to be to try and add a more fully-fledged version of MCTS to the program, mostly just to see if it performs tangibly better. It'll be especially fun pitting different versions of the AI against each other and seeing if one has an edge over another.

After that's done, I'm tempted to experiment a little more with different guiding heuristics. It might be interesting to use a decent AI to build up a big corpus of games, then use that corpus to train some sort of statistical model for guessing candidate moves, and use those guesses to help navigate the search space more effectively. I'm not sure how well that will work -- the original algorithm does after all work from random move choices, so as far as data derived from it goes, one is tempted to invoke 'garbage in, garbage out' -- but it'll be interesting regardless. I'm hesitant to make predictions but I think it'll work pretty well.

In any case, I've already achieved my goal of losing consistently, so I know I'm on the right track.

Saturday, December 24, 2016

Academic Computer Science Needs to Get Its Shit Together

The fact is, our beloved field of computer science has reached an embarrassing low. Among programmers in all but some collegiate circles, calling something "academic" is oblique shorthand for calling it overwrought, obscure, inflexible, and/or too fragile to be useful in the real world. And there's a good reason for this: more often than not, the products of academia in computer science meet all those criteria.

But why? Shouldn't universities be where our best and brightest gather? Isn't the whole idea of academia to draw great minds together so they can collaborate and educate?

The short answer: Well, yes, but that idea doesn't work so well when you're competing for talent against an industry that can afford to triple your salary offers. With few exceptions, industry gets who they want and academia gets stuck with the dregs -- and you can't do much with dregs.

What's the long answer? Glad you asked. Buckle up.

Once upon a time, academia really was (I am given to understand) a heavyweight player in computer science. MIT and University of Illinois have their places in the annals of Unix history right next to Bell and GE, and in fact it was academia where Unix first really gained traction. Same with the internet -- there's this map that's been floating around recently:

There's a lot that's interesting about this picture, but as far as our discussion is concerned, let's note the breakdown of who owns which nodes: there's a few gov't agencies and a few companies represented, but a solid majority of the systems are academic. Universities broke a lot of ground in both developing and implementing the technologies that underlie the internet.

Of course, hardware and networking isn't everything, and there are other areas where academia had a lot to offer. For instance, it's hard to overemphasize the eminent (and eminently quotable) Edsger Dijkstra's influence on programming language design, distributed systems, or really any number of other subjects. Or take Donald Knuth, who wrote the book on computer science, then called it "volume one" and set back to work writing volumes two through five (six and seven still pending!). Or Martin Hellman, who advised Ralph Merkel's groundbreaking PhD work on public-key cryptosystems. Hellman later recruited Whitfield Diffie to his lab and together they built on that work, eventually leading to the landmark discovery of what is now called Diffie-Hellman key exchange.

This was all real ground being broken, real problems being solved, challenging work being done well -- all by academics. If these were once academia's exports, when did it become so maligned? Where did things go wrong?

Well, there's a case to be made that in spite of all the above, things might not have gone wrong so much as stayed wrong. Knuth and Dijkstra, for instance, were both outspokenly critical of their field.

Knuth said of computer science during his time as a student that "...the standard of available publications was not that high. A lot of the papers coming out were quite simply wrong." He made it clear practically in the same breath that one of his main goals with The Art of Computer Programming "was to put straight a story that had been very badly told."

Dijkstra, for his part, held practically every language of his time in the highest contempt. COBOL and BASIC "cripple the mind" and leave students "mentally mutilated beyond hope of regeneration," respectively. FORTRAN he described as "the infantile disorder," while PL/I was "the fatal disease." He also had some critical words for those in his field who refused to acknowledge some of its more uncomfortable truths.And in an abstract moment he opined, "Write a paper promising salvation, make it a 'structured' something or a 'virtual' something, or 'abstract', 'distributed' or 'higher-order' or 'applicative' and you can almost be certain of having started a new cult." Some things, it seems, never change.

A professor of mine once commented, in one of the last meetings of his class, that the structured programming practices he'd been teaching us were important because "my generation has already written all the easy programs. The hard ones are up to you guys." He was of course talking about software development -- the bricklaying of computer science -- but I suspect that a similar quip would apply on the theoretical side of things.

Obviously the field is still new, but by and large it really does seem to be true: The easy, useful results have been discovered. The easy, useful definitions have been made. The easy, useful algorithms have been found. Having reached this point, academics now have two choices: either we take on the stuff that's not easy, or we take on the stuff that's not useful. A quick flip through arXiv suggests that most researchers have opted for the latter option.

The sad fact is, of course, that modern academic culture does nothing to discourage this -- in fact, "publish or perish" actually encourages professors to focus on cranking out useless but simple results. Meanwhile, profound guiding problems like P vs NP or even P vs PSPACE go all but untouched. The culture is such that the average academic who's fool enough to really throw themself at such a problem ends up reduced to a "cautionary tale" in a survey paper.

Make no mistake: there are major, important unsolved problems in computer science. Hell, there are enough that Wikipedia's got a whole list. Breakthroughs on any of these would instantly make the reputations of the researchers involved. But those with the expertise to take these issues on are, more often than not, actively discouraged from doing so. How is a field supposed to produce anything of value when this is its culture?

There's a quote I recall reading, but which I can't seem to dig up. It was from one of the leading researchers on the topic of proving program correctness, given some time before the turn of the millennium, and his observation was that while the field had advanced significantly in the years he'd spent studying it, he was slowly coming to realize that the problems they were trying to solve, nobody else was really all that concerned about.

I know of a few kernel programmers and security buffs who'd take issue with that claim, but aside from them and aside from a few other very specialized contexts it turns out that yeah, nobody really cares too much. In the same vein, very few people care about some equivalence result in complexity theory between two games they've never heard of. Same goes doubly for the underachieving grad student's favorite recourse: survey papers directed at the above.

That story is a pretty common one in theoretical computer science, and honestly it's understandable -- the field is new, and it's only fair to give it some time to get its bearings. Not every result is going to have immediate practical applications, and we'd be doing everyone a disservice if we expected otherwise. But while that might excuse some seemingly useless research, it's no excuse for the sheer mediocrity and apathy that pervade the field.

There are important results waiting to be found. It seems apt to compare modern complexity theory to ancient Greek mathematics -- perhaps, if we really want to push the analogy, even going far enough to equate Knuth with Euclid -- and if this comparison holds, then mind-boggling amounts of valuable theory have yet to be discovered. My own background leaves me tempted to bring up the influence these results could have on computer security, but really, it's hard to think of a subject they wouldn't influence. In fact, there are enough connections between computer science and advanced mathematics that results found here could easily filter back and offer unexpected insights on long-standing problems in that domain as well. John Conway's work gives a number of examples of what that might look like.

Speaking of computer security: one exciting thing we learned post-Snowden that, while we've massively dropped the ball on endpoint security, we've managed to build cryptosystems that actually work. Modern cryptography is one of the few things our clearance-sporting buddies in Fort Meade don't seem to be able to crack. And yet we don't have solid proofs for such basic questions as: do one-way functions really exist? Or, are public-key cryptosystems really possible? On the more practical side, we also have a tremendous amount of work to do as far as post-quantum cryptography and cryptanalysis are concerned.

In short, there's important work to be done, and (since abstract arguments are notoriously hard to monetize) you can bet industry isn't going to do it.

If academic computer science wants to be taken seriously, it needs to get its priorities straight. It needs to stop discouraging work on problems that matter, stop encouraging work on problems that don't, and make an honest effort to equal the landmark achievements of previous decades. There's still plenty of room in the history books.

Monday, October 17, 2016

Virtualizing a Raspberry Pi with QEMU

A while ago, I wrote about building a rack for a Raspberry Pi cluster. If you have a rack, at some point you'll want to put some Pis on it. Virtualization can make the process of imaging these Pis relatively painless. You can generate custom images from the comfort of your desktop and even automate the whole process. Here's a quick crash course in virtualizing the Pi using QEMU.

All the guides I could find on this were at least a couple years old and were missing various important parts of the process. None of them quite worked out-of-the-box. It's hard to blame them, though, since a hardware platform like the Pi is of course a moving target. For what it's worth, this guide should be complete and up-to-date as of October 2016.

The first thing to do is to get a base disk image to work from. It shouldn't make too much of a difference what you choose (unless you opt for something absurd and masochistic like Arch Linux). For this guide, I'll be using Raspbian Lite. My focus will be on emulating images compatible with the Pi 2, though I don't see why they wouldn't work on the Pi 3 as well.

Once you've chosen a distro, download or torrent a .iso file for it. As soon as you have that, you can get started. I like to start by making a working copy of this .iso file right off the bat so that if I make a mistake I can just be throw it away and start over again from a fresh copy, without having to re-download the image.

mkdir -p ~/workspace/raspberry
cp ~/Downloads/2016-09-23-raspbian-jessie-lite.img ~/workspace/raspberry/raspbian.img

raspbian.img will serve as our base image. If you ever want to copy the current state of the virtualized Pi to an SD card, you can do that using dd from this file.

We'll need a custom kernel to get QEMU to boot this Pi image. Currently this github repo maintains up-to-date kernel files for this purpose. Source code and a build script are included, if you're interested in those.

cd ~/workspace
git clone
cp qemu-rpi-kernel/kernel-qemu-4.4.13-jessie raspberry/kernel-qemu

Now we have everything we need to boot up the Pi -- but if we do, it'll hit a kernel panic and dump core. That's no good. If you want to see this happen, then feel free to copy the qemu command from later on, but I'll warn you: it's not very exciting. What we're going to do now is make a couple fixes to different config files so we can get things working.

Before we apply these fixes, we need to be able to mount the Pi image's root partition. There's a hard way and an easy way to do this. The hard way involves reading the image's partition table, multiplying one of the fields in it by 512, and making a huge "mount" invocation. The easy way is this:

cd ~/workspace/raspberry
sudo kpartx -va raspbian.img
# note the name of the loop device chosen by kpartx, then...
sudo mount /dev/mapper/loop0p2 /mnt  # assuming kpartx chose loop0

kpartx does all the work for us, reading the image's partition table and creating loop devices for its partitions. The first one is the Pi's boot partition and the second one is its root filesystem. So following this process gives us the Pi's root filesystem mounted to /mnt. No mess no stress!

Now, here's what we've got to change. First, edit /mnt/etc/ and comment out its first and only line by prepending a # to it:


This prevents the kernel panic. I have no idea why.

Next, create a new file: /mnt/etc/udev/rules.d/90-qemu.rules
and put the following lines into it:

KERNEL=="sda", SYMLINK+="mmcblk0"
KERNEL=="sda?", SYMLINK+="mmcblk0p%n",

These are necessary because (/mnt)/etc/fstab specifies partitions under /dev/mmcblk0 for critical parts of the filesystem. That would make sense for Raspbian under normal circumstances because it boots from an SD card, but since we're exposing our disk image to the system as /dev/sda, we need to add these mappings if we want to keep everyone happy. You could of course also edit /etc/fstab to specify sda instead of mmcblk0, but that would break compatibility between the image and actual Pis.

These two fixes should be enough to get Raspbian to boot cleanly. If you want to use SSH to access the Pi from the host machine, you can optionally set that up as well by disabling password login (which actually is good to do anyway) and adding your public key to authorized_keys. If you don't already have a public key, you will of course need to run rsa-keygen first. Then,

echo "PasswordAuthentication no" >> /mnt/etc/ssh/sshd_config
mkdir -p /mnt/home/pi/.ssh
cat ~/.ssh/ >> /mnt/home/pi/.ssh/authorized_keys

And you'll be good to go. This disables password authentication but grants passwordless access to anyone in possession of your private key.

You should also unmount /mnt at this point:
sudo umount /mnt
This may not be strictly necessary but it seems like common sense given that /mnt is mounted from a partition on the image file we're about to give to QEMU. Under certain circumstances, leaving a partition mounted while also using it with QEMU runs the risk of corrupting the filesystem.

Now, the moment has arrived -- we're going to actually boot up our virtual Pi! Here's the invocation:

qemu-system-arm -kernel kernel-qemu -cpu arm1176 -m 256 -M versatilepb -no-reboot -serial stdio -append "root=/dev/sda2 panic=1" -hda raspbian.img -redir tcp:5022::22

That should work to boot to a login prompt. The default login is:
Username - pi
Password - raspberry
If you didn't disable password authentication for SSH earlier then you should change this password as soon as you log in.

For education's sake, let's break down the different parts of that QEMU invocation:
  • Since the Pi is an ARM system, you naturally invoke QEMU's ARM emulator.
  • We pass it the kernel image we obtained from Github earlier. 
  • We specify the CPU model as arm1176, and we give the device 256M of RAM.
  • The ARM board type we specify as VersatilePB.
  • -no-reboot is necessary because without it, running commands such as sudo shutdown -h now in the guest would not in fact shut down the virtual system but would instead reboot it. Not sure why.
  • We specify -serial stdio to allow stdin/stdout to be used for a serial connection. This isn't strictly necessary as far as I know but it's widely included in examples, and it would certainly be useful for scripting interactions with the guest OS.
  • -append allows us to pass kernel parameters to the guest. We specify the "disk" partition it should mount as root, and we tell the system to reboot after 1 second on kernel panic. You can replace this with a larger integer to wait longer, with 0 to hang on panic, or with a negative number to make kernel panics cause an instant reboot.
  • We also of course specify our working copy of the Raspbian image file as the system's primary hard drive.
  • Lastly, we set up some port forwarding to allow us to connect over SSH from the host. Port 5022 on the host will be redirected to port 22 on the Pi. That lets you ssh to the guest from the host like this: ssh -p 5022 pi@localhost

If you want to copy your configured Pi image to a SD card, you can simply plug in the card, use dmesg to find the name of its block device (we'll assume here that it's /dev/mmcblk0), and then write from the image file to this block device using dd:

sudo dd if=raspbian.img of=/dev/mmcblk0 bs=4M status=progress

And once that completes, your SD card should be all set! Note that you'll probably want to expand the filesystem once you've finished writing to the Pi, since the SD card's max size is likely a fair bit larger than this disk image. On Raspbian, the raspi-config utility provides a helper tool for doing that.

So, that just about does it for using QEMU to virtualize a Raspberry Pi and create custom SD card images! If there's anything you'd like to add, feel free to leave a comment below.

Thursday, May 12, 2016

On Ceasing to Be Exceptional

Somewhere just north of a decade ago -- so when I was 10 or so -- I was helping strangers in online forums troubleshoot games they were making. It was crazy fun. I still remember this one guy: He had a 3D FPS he was building in Game Maker, a tool that (for this use case) gives you a graphics engine and not much else. He had mouselook set up (no trivial feat) and had a bare-bones firing system, but it only worked when the camera was leveled out flat. You couldn't shoot up or down. That's a big problem, but the game was still pretty fun in spite of it, so in the spirit of trying to make a good thing better I offered to help.

With the right background knowledge, the solution is pretty clear. The mouselook system gives us an angle for how far up or down we're looking. What we want is for bullets to rise or fall at a steady rate determined by this angle. So we need a value to determine that rate, and that value will end up being a slope. You can turn angles into slopes using trig: slope = rise/run = sin(θ)/cos(θ) = tan(θ). So you take this slope, scale it based on horizontal speed, and periodically add that to the Z coordinate.

This is easy to figure this out if you know the concepts involved, but take it from me: it's a lot trickier when you've never heard of a slope and all you know about trig is what Wikipedia tells you. But with a few days' work I figured it out, sent the guy a patched version of his game, and went back to playing it. All this work, and yet for the life of me I can't remember his reaction.

About a year or two later, I joined a game making group. They already had programmers, so I told them I made music. They couldn't let me in fast enough when they heard that. I did make some music, but I also pitched in whenever anyone asked for troubleshooting help. Pretty soon I was the go-to guy for figuring out the really pathological stuff.

After a while I started working on my own project, a turn-based strategy game (tragically never completed, but surprisingly close to completion, and sporting a totally bonkers implementation of A*). I got hung up on the AI, lost steam, and turned to other projects. I wrote my own FPS, which (to my astonishment) people actually played. I wrote a couple RPGs from the ground up. I wrote a 2D, team-based multiplayer game inspired by laser tag. In fact, writing the login system for that game sparked my interest in security.

In my free time, I was pushing my limits by working with a fantastic math tutor (Naomi, whose debt I am deeply and eternally in). She taught me everything up to calculus, past which point I taught myself. By the time I started high school, I'd built up a working knowledge of multivariable calculus.

And now, here I am: 22 going on 23, and not feeling too different now than I did then. What happened?

The answer, it feels like, is "not much." People learn at different rates, and I happened to luck out by being someone who learns certain abstract subjects really quickly. That doesn't make me inherently better at them. It just means I got a sort of head start. And I'm coming to suspect that the same is true of many if not most talented young people (including many who were/are way above my level).

I've had the great pleasure in my life of knowing some real capital-G Geniuses -- people who, when you see them at work, it's hard to believe they aren't in touch with something beyond our understanding of the world. It's sublime. But these people are rare. They're literally one-in-a-million. And so, inspiring as they are, they don't change the fact that most talented young people seem to be exceptional not so much in the degree of their abilities as in how quickly those abilities develop.

It's a little bizarre that so many of us hold precocity in such high regard. Think about it: when you compliment a young person by calling them precocious, you're giving them praise that comes with an expiration date.

Say you have a ten-year-old who's reading at the level of someone twice their age. You might call that person talented, exceptional, precocious. If you have a twenty-year-old reading at the level of someone twice their age... well, that's just called being literate. Past a certain age, being pretty good at something ceases, by itself, to be exceptional. You have to find something more.

I was tempted to end here, because that "something more" is different for every person, so it's hard to imagine how to follow up on it. I'd actually left this post as a draft for about a week, dissatisfied but lacking any better idea for how to end, until a remark from my old, excellent friend Henry sparked my interest again. He observed, casually and offhand, that 'you're always making progress, just maybe not in the direction you thought.' To me, this really cuts to the core of what I'm trying to get at. Since I've put so many words into explaining my background, let me carry that a little further to try and show what I mean.

There's an incredible gap between being good at something and being good at explaining that thing. To find evidence of this, one need look no further than the average research university lecture hall. In fact, it's often the case that the better you get in your area of specialty, the harder it gets to explain it. As you learn more, you end up with more and more levels of abstraction separating you from your audience, and so the gap gets ever harder to bridge.

This was something I experienced trying to implement a secure login system -- I'd be going on to one of my game-making buddies about, say, secure key exchange, and after describing how this lets us lock down the login protocol, I'd get back a reply like "ok, but wait, wouldn't it be easier to just send everything in plaintext?" I was so far down the security rabbit hole that it was almost inconceivable to me that anyone would even suggest such a thing. When you focus on a problem for long enough, it's easy to lose touch with outside perspectives.

Now, it's easy to blame awkward exchanges like that one on ignorance. 'Oh, man, how could this guy not even know about sniffing passwords?' There's a certain selfish satisfaction in knowing stuff, especially stuff that other people don't know. But if you know something that the person you're talking to doesn't, and their ignorance is impacting the conversation, whose fault is that? You could fault them for their ignorance, or yourself for failing to be a better communicator. The latter option tends to be more productive.

It can be really difficult, though, to communicate well about difficult topics. Maybe that's obvious, but it's something a lot of people seem to underestimate, to their own detriment. I certainly see that underestimation in myself as I was around the time I outlined earlier. I may have been good at math, but how good was I at explaining it? I may have been interested in security and committed to personally getting it right, but how good was I at showing other people why security is important? Not very, and I think this is somewhere I've grown, practically without meaning to or even being aware of it.

I think this experience generalizes. Suppose for example that you're someone early on in their college career who's always been really good with literature -- reading well above your level, laughing at reading comp questions, writing insightful analyses -- and you come to feel, in college, like somehow you've plateaued. The best is behind you, it feels like. In high school you were hot shit, but now you're just another 20-something with a notebook and some colored pens. You might feel like you're stuck in a rut, like you're not going anywhere, maybe even like being in college is a mistake.

But what if, while you aren't learning anything new about (say) literary theory, you are learning about how to communicate what you know? After all, odds are that if you were hot shit in high school, there was a pretty short list of people with whom you could have a really good back-and-forth about this stuff. Not so with college (though this is not unique to college). Learning how to have a productive discussion without arguing or talking down, learning how to explain something without patronizing, learning how to ask good questions -- all these are valuable skills, and also skills that it's hard to realize you're even working on. That is, until you've made enough progress that you can look back and see how far you've come. When it comes to math, I don't feel like I know a whole lot more now than I did then, but I do feel much more qualified to share what I know.

There's an absolutely beautiful moment in this 1950 movie, Harvey. The movie (adapted from a play) is about this super sweet, middle-aged, heavy-drinking dude, Elwood, whose best friend is a giant rabbit that no one else can see. The whole film is magnificent, but especially one moment near the end, after Elwood's family tries to have him committed to an asylum. The plan backfires when Elwood's simple charm wins over the asylum staff.

The chief analyst tries to explain to Elwood just how awful his sister's plans for him are -- "She's trying to persuade me to lock you up!" -- and can't understand why Elwood isn't more upset. By way of explanation for his good-naturedness in the face of all this, Elwood replies that he's come to understand that in life, "you must be oh so smart, or oh so pleasant. Well, for years I was smart. I recommend pleasant."

There's also this great story about Richard Feynman -- who was, above almost all else, famously good at talking clearly about complex subjects. About a year before his death, when it was clear that cancer would kill him but unclear just how long it would take, he was out on a walk with a good friend. This hardly made for cheerful conversation, it seems, and so his friend was kind of down. Feynman asked him what was wrong, and his friend said, "I'm sad because you're going to die."

Feynman replied that he was sad about that too. It wasn't so bad, though -- he'd come to a realization, you see. "When you get as old as I am, you start to realize that you've told most of the good stuff you know to other people anyway."

May we all be so fortunate.

Wednesday, April 13, 2016

Book Notes

Over this past couple years I've been lucky enough to find time in between classes and research for a bit of pleasure-reading. I thought it might be fun to write a little on different books that've left strong impressions on me. It's nice to keep a record, but maybe I can also share some of the enjoyment I've gotten from them.

It was tempting to put the word "Reviews" somewhere in this headline, but I'm not really trying to just share ratings and little terse blurbs here. Ratings are subjective and reductive, so it's hard to see much point in cooking them up in this context. I'd rather just share a few thoughts and impressions for each book with the hope that you'll find them interesting.

Pnin (Vladimir Nabokov): It's been a year or two since I finished this book, but it's stuck with me. The book takes the form of a sequence of tiny, self-contained episodes, in fact almost -- but not quite! -- a set of short stories. Their unifying thread is Pnin, the tragic hero, a Russian émigré to America fleeing "the Hitler war". Pnin is the absent-minded professor made full, the epitome of stereotype somehow rendered authentic. Nabokov, in creating him, has managed somehow to both epitomize and transcend the archetype. He starts out as someone absurd, someone to be laughed at -- when we first meet him, he is travelling to give a guest lecture, fussing over details while unwittingly boarding the wrong train -- but the longer we spend with him, the more we realize that Pnin himself is not to be ridiculed. Rather, people's reactions to him are.

The fact (we come to see) is that poor eccentric Pnin is a kind soul in an unkind world, and as you read more and more, you find yourself almost involuntarily rooting for him to do well, to score some small victory. These victories are rare, though, and almost always inconsequential. Far more common are tragic mistakes and misunderstandings (which Nabokov somehow manages to render both heartbreaking and incredibly witty). Throughout the book Pnin is put through progressively greater indignities, and yet he refuses to let them break him, refuses to grow jaded and cynical towards this world, which has given him little more than pain. Witnessing this, we are slowly brought around to a sort of awed respect for this strange little man, so naive, so awkward, and yet somehow utterly indomitable. Rare is the character whose failures are so inspiring. I found the book's final chapter deeply moving, and this is a book that I'm very much looking forward to someday reading again.

Something Like an Autobiography (Akira Kurosawa): I'm actually only halfway through this one, but I've come to  like it so much that I can't resist including it. Kurosawa, for those who don't know, is almost certainly the most internationally famous Japanese film director. Some of my favorite movies (Kagemusha and Throne of Blood, to name two) are his. But on top of his talents as director, he also turns out to be a really witty -- and disarmingly honest -- storyteller. The introduction lets you know that his autobiography only extends to around the time he started work on Rashomon, because everything else would be too recent for him to engage in full disclosure. At first I was disappointed by this, but the anecdoes he does provide are so engaging, and offer such an unexpectedly great level of insight into his character, that the book ends up being brilliant in spite of this restricted scope.

It's a bit funny to list this book below Pnin and above The Pale King, since all three follow roughly similar episodic formats. Something Like an Autobiography is composed of a long series of short anecdotes, most just a few pages long, recounting different moments from Kurosawa's life. Some are poignant, like his reflections on the "lost sounds" of his childhood. Others are funny, like when he recalls his "rebellious phase" in middle school. And some are utterly harrowing, like his description the Great Kanto Earthquake and his subsequent exploration, with his brother, of neighborhoods flattened and burnt to the ground, where they found piles of charred corpses and rivers so full of bloated death that they were running red-brown. But even in this passage, Kurosawa's account of what he saw, and (implicitly) of his relationship with his brother, is so compelling that it's impossible to stop reading. Notably, Kurosawa turns out to be a master of brief but vivid descriptions, of almost effortlessly calling up the spirit and image of a place, and so his stories serve not only as an account of his life but also as an account of the times in which he lived. I'd recommend this book to just about anyone, even if they couldn't care less about movies.

The Pale King (David Foster Wallace): Published posthumously, there is something suffocatingly sad about the very existence of this book. I've read all of Wallace's published fiction, and a lot of it is very powerful, but nothing else hit me in quite the same way as this. Some context: Wallace only ever published two other novels, The Broom of the System and Infinite Jest. Reading The Broom of the System, there are the occasional dull moments, and I'd have a hard time identifying anything I'd call the novel's emotional center -- and yet even so, the writing is so charismatic that it's hard to escape the impression that here is someone who, on the page, can do literally anything. Next up, Infinite Jest manages to be incredibly emotionally powerful through its wrestling with themes of addiction, alienation, and the deep human need to find something to give ourselves away to. Infinite Jest was written as a critique of its times, a narrative account thereof, a catalog of insanities (among other things), and yet it tries very hard to convince you that things don't have to be this way, that there is still good in the world.

After Infinite Jest's publication, though, Wallace seemed to decide (perhaps based in part on the book's popular reception) that what he had provided was diagnosis without cure. The Pale King was to be the book in which he corrected this mistake. His struggles to complete it are legendary, and a serious case of writer's block led (at least in part) to his decision to stop taking Nardil, since he suspected that it was numbing him emotionally in a way that prevented him from realizing his vision for The Pale King. He later went back on Nardil, but found that it had stopped working. This seems to have directly led to his suicide in 2008.

This background necessarily colors how we see The Pale King. It stands unfinished; the cure couldn't come soon enough. The novel is still rough around the edges, yet even so you can tell that it could have stood on par with -- or even surpassed -- his other work, had Wallace lived to finish it. It feels kind of gross to tie the author's real life into the novel's narrative, but in this case it's also nigh irresistible, and the (involuntarily obtained) result is one of the most profound, crushing tragedies imaginable. This is probably not the novel I'd recommend to someone who wants an introduction to Wallace (for these readers, Good Old Neon and a few other titles come to mind). However, as a great admirer of Wallace's work, I personally found The Pale King transfixing.

Information Doesn't Want to Be Free (Cory Doctorow) (previously): This is one of the best nontechnical books about the internet I've ever read. Doctorow's overarching theme here is to put forward his "Three Laws", namely:

1) Any time someone puts a lock on something and won't give you the key, that lock isn't there for your benefit.
2) Fame won't make you rich, but you can't get paid without it.
3) Information doesn't want to be free, people do.

Each law is meant as a statement on an issue he takes very seriously, and so it might seem at first like the book is forced into a sort of limited scope. This suspicion is natural, but completely mistaken. In expanding upon his chosen issues, Doctorow manages to draw connections to a head-spinning number of topics -- in fact, he pulls in so many different issues that it would feel disingenuous to try to give any list. There are chapters in here about the history of the music industry. There are chapters about how to find an audience and (hopefully!) make a living as an artist. There are chapters about digital rights management (or "digital locks"), and how these technologies lead to no-win situations. There are chapters about the TPP and the very serious dangers its copyright provisions pose. The list goes on. In everything he discusses, a common theme one begins to pick up on is that problems arise when we fail to put people at the center of our designs.

Every topic Doctorow touches on fits into the overall flow of his discussion almost effortlessly, and his arguments are invariably lucid and well-reasoned. I'd already heard of pretty much every issue he discusses, and yet I felt like I learned so much just by studying how he lays out his cases and picks examples. Doctorow's talent lies not just in his capacity to care deeply and passionately about these issues, but in his capacity to make you see why you should care, too. The world needs more people who can do that.

Another nice thing about Information Doesn't Want to Be Free: it's published through McSweeney's! You can buy it direct from their website, which is a nice break from the usual Amazon-induced guilt many of us associate with buying hard-to-find titles. I don't have a list of my favorite companies to give money to, but if I did, I'd probably put McSweeney's pretty close to the top.