Blog Articles 86–90

Robot Dreams

I’ve been working through some of my backlog of started-but-not-yet-finished books and finally finished Asimov’s Robot Dreams collection.

I’ve read a fair amount of Asimov before — robot stories, novels, the Foundation trilogy (which I greatly enjoyed), the Foundation sequels (Foundation and Earth accomplished the rare feat of retroactively damaging the trilogy; I prefer to pretend it does not exist) — but this collection would stand as my recommendation for someone seeking a starting point for Asimov. At least if they don’t want to dive into the world of Foundation. It has a smattering of robot stories, Multivac stories, and other things, many of them excellent.

Some highlights:

  • ‘The Martian Way’ is a fascinating medium-length piece (nearly a novella) on the political turmoil leading to the independence of the Martian space colony.
  • ‘Eyes Do More than See’ and ‘Does a Bee Care’ are slight, haunting pieces with grand themes. Brilliant examples of what can be done in 6 pages of well-chosen sentences.
  • ‘The Feeling of Power’ is strange and fun — what happens in a future where we have computers but forgot how they work, and basic mathematics are rediscovered?
  • ‘Jokester’ — where do jokes come from? What happens when we find out?
  • ‘Franchise’ is premised on the perfection of social psychology, but in a lighter-weight fashion than Foundation. If we can thoroughly understand people, do we need elections?

The Crowd is a Monad

I had a great time this week at Computer Supported Cooperative Work and Social Computing. Met lots of interesting people, heard good talks, enjoyed Baltimore.

One of my favorite papers of the conference was AskSheet: Efficient Human Computation for Decision Making with Spreadsheets by Alex Quinn and Ben Bederson. The concept is brilliantly simple: embed crowdsourcing capabilities in a spreadsheet, allowing decision makers (and others) to use the tools they already know to solicit information via Mechanical Turk and process the responses. To make it all work, they did some very interesting work on batching queries, estimating the likelihood of actually needing a piece of data and using this to order the crowd data requests, and other things to improve the efficiency of an application’s use of the crowd.

It’s not hard to envision an extension of this work into functional programming more generally. Someone could create a Crowd monad with an API something like this:

--| Create a crowdsourced query.
ask :: String     --^ Descriptive text for this query.
    -> Schema a   --^ Schema for user responses.
    -> Crowd a
--| Run a crowdsourced query, returning the results (after processing).  Runs in
-- IO because it needs networking, etc.
crowdsource :: CrowdProvider -> Crowd a -> IO a

Academic Travel Tips

Academics — at least those actively involved in computer science research — do a fair amount of travel. Making this go smoothly is something of a learned and practiced skill. Here are some things that have helped me.

Make School Not War

This crossed my Twitter stream today, thanks to Mark Guzdial:

The original article has posted an important correction — the funds spent on the wars in Iraq and Afghanistan (not just Iraq) would fund public higher education for 52 years (not 58). The numbers are weakened a bit, but don’t really undermine the point.

Trusting Government IDs in the Web of Trust

Generally-accepted practice for verifying the identity of other cryptography users and extending your web of trust to them usually involves checking a government-issued photo ID, verifying that the picture is the person giving you the key fingerprint, and then verifying that the name on the ID matches the name on the PGP key that you are going to sign. The purpose of this is to know that, when you encrypt to that key, only the person you think is receiving the mail can read it, and that signatures from that key come from the person who claims to use it. It allows you to associate the cryptographic key with a person.

In the present era, where state-level adversaries are on the top of many security-conscious users’ minds, isn’t this a hole? Aren’t we depending, critically, on the very entity we are trying to protect ourselves from?

I don’t think this is a significant weakness, though. To understand why, let’s first consider exactly what attacks would be enabled by the government misusing its identity-certifying authority. It allows them to compromise key exchanges. That is it. Specifically, if Alice and Bob want to exchange key fingerprints, what Proconsul Eve can do by forging an identity document is to substitute her operative Albert, with government-issued documents certifying he is Alice, at the meeting. The result is that Bob will have thought he verified that Alice’s key actually belongs to Alice, when in reality the private key is held by Eve. So when he talks to Alice, he’s really talking to Eve.

Once the key exchange is done, however, Alice and Bob have no need for government-issued ID. They have securely exchanged keys, and Eve cannot fake an exchange to substitute her own keys. The only thing that can be done by issuing an invalid ID card is to compromise the initial key exchange.