" /> Ezra's Research: August 2006 Archives

« July 2006 | Main | September 2006 »

August 6, 2006

Why Practitioners Don't Use Research Papers

Werner Voegels:

When selecting research technology, it is often a major exercise to discover what exact assumptions the researcher made. ...
In Control Theory, for a long time, researchers were convinced that practitioners did not want to use their research because there was too much complex math in it. It turned out however that the research was largely irrelevant in practice because it didn’t model a realistic world. The moment researchers started to produce work that explicitly took uncertainty into account, their work was rapidly adopted by engineers and architects. Ironically the math has only grown more complex…

August 1, 2006

Lambda 5: Modal Logic Inpsires a "Distributed" Programming Language

At the Oregon Summer School 2006, Robert Harper presented his Lambda 5, a modal-logic-as-distributed-programming-language. The idea here was that modal logic allows you to reason about things that are true in some "possible world"—and since, via Curry-Howard, true statements are like types of values that are known to exist, the programming-language interpretation of "proposition true at a possible world" is "data available at a possible world"; Harper et al. interpret a "possible world" as a node on a network. Thus, Lambda 5 gives you a way to write terms that are local or mobile: you create local values by publishing an address, which others can use; you create mobile values by packaging them up in a context-independent way. You consume the latter by simply "unboxing" them. The address of a local value is harder to consume—you need to use a binding construct whose body is executed in a hypothetical world where only the addressed value is available.

Harper's presentation was fast & furious, and if you weren't already adept with propositions-as-types, you were probably lost at the beginning. I held on with my toes. Afterward, I got the paper [1, 2] and have been looking at it, trying to figure out if it's going to help me with the issues of locality and distribution that I've been dealing with in the context of Links.

There's an important drawback, or at least caveat, about Lambda 5 as a theoretical approach to distributed computing. It explicitly avoids issues of concurrency. The entire multi-node network of locations is assumed to have a single thread of control. When you consider that there is a substantial bulk of research called "Distributed Computing" and that this research is almost all primarily concerned with issues of concurrency, you might consider this omission rather serious. In the second paper [2], Harper and company use letcc to make control flow explicit, arguing that this gives a way to recover concurency. But if I understand what they're doing, it amounts to a kind of explicit, cooperative multi-tasking—a poor approximation to the situation (and the problems) of distributed systems. My question for this line of research: What are you trying to accomplish?

Oregon Summer School: Further Notes

I've been putting off writing up the rest of the lectures from the Oregon Summer School because I seem to have lost my trusty notebook where all the brilliant things were intoned. But I guess it's gone on long enough; the world must know what happened at Oregon Summer School 2006.

Some of the presenters I mentioned before talked on more than one topic. Michael Hicks, after talking about futures, went on to discuss some work on "dynamic software update" or DSU. Hicks has developed a set of techniques for dynamically loading a new version of an existing program, and switching it over while it runs, with zero downtime. This includes translating old data representations to new ones. As I listened to the talk, I kept thinking, "OK, sure, we're going to design our code in this highly-restricted way, and then as long as we're willing to bend over backwards to do some tricky retrofitting, then hypothetically we might be able to update the code without downtime."

I was wrong! Hicks and his team have actually taken three years' worth of updates to sshd and vsftpd (amounting to a couple dozen updates, including some whole-number revisions) and updated running instances with each successive version, all without crashing or taking the server down. I was quite astonished that these techniques could be applied to changes that have already been made in the wild. Of course, they had to write some code to translate in-memory data structures on the fly—but they didn't have to re-architect the application to make it fit. Everyone in the seminar room woke up when Hicks showed the slide showing all the versions, with their dates, that had been dynamically loaded into these servers.

I would be interested to see whether these DSU techniques turn out to be a good software-engineering tradeoff in the long run. Most of the time, just having an extra machine to handle load while you bounce individual servers to the new version is a cheap way to get the same result. And you still have the challenge of writing your updates so that they're compatible on the wire: you can update sshd's internal structures on the fly, but updating the protocol might be more challenging. Also, to be slightly critical, sshd and vsftpd together make a pretty constrained class of software: slow-changing servers that mainly wait for connections and spawn off processes to handle them. Would this work for a more sophisticated system like a fancy real-time game system, where the gamers are actively interacting through the system?

Matthew Flatt argued for programming-language features inspired by OS features. The case was reasonably compelling: an IDE like DrScheme needs to run user programs in a special bomb-proof box, so that user programs can't impinge on the workings of DrScheme itself. This extends to lots of issues: device ownership, memory consumption, non-termination. Flatt argued for an abstraction called a "custodian" that manages all those resources together; killing the custodian frees up all the resources it manages. At the same time, he wants to enable sharing of data between programs, as an OS might allow. This makes the memory-management problem much harder, of course, since you need a policy for determining which custodian is "charged" for a block of memory, when it's shared between many. Flatt outlined a policy, whose details I didn't get, which apparently works in his setting.

Sandhya Dwarkadas talked about transactional memory from the hardware point of view. Unfortunately, her talk was pitched in the vocabulary of computer architects, so I didn't understand any of it! At a high level, what I took away was that transactional memory might be easy for processor makers to provide, by taking advantage of the cache-coherency systems that are already being included in multiprocessor machines.

Jeff Foster talked about another system for statically detecting race conditions, like Flanagan's for Java, but this time for C code. It amounts to a kind of pointer alias analysis, and the details are very complicated. A question that wasn't raised, which just occurred to me: Why was alias analysis necessary in C but not in Java? I think the answer will be that the Java system may assume that most access to data members are from within the class definition (and thus are not by reference).

Shaz Qadeer had the true misfortune of presenting last, after we'd patiently sat through 48 hours of lectures. For myself, I know I didn't follow his (or Jeff Foster's) presentation as closely as most of the others. Someone has to go last, I guess. Qadeer's presentation was on model-checking concurrent software. Some of the material he presented was basic model-checking stuff (like "What is LTL?") but he quickly jumped ahead to cover fancy techniques for state-space reduction. I'm always surprised when speakers do that. If you assume that I don't know the basics, then why do you expect me to absorb those and with some advanced material in one lecture? If you want to focus on the advanced stuff, then why not just say, "This is for people who already know X," and just give a quick refresher for X? The advanced students were probably bored while us newbies asked questions about LTL, and us newbies got bored once our intuition had been outstripped and we couldn't follow the lecture closely anymore.

All in all, the quality of the presentations at the Summer School was quite high. I was surprised that I could follow about 40 of the 48 hours of lectures, and got something out of almost every one (the previous 48 seminars I'd attended didn't have half that hit rate).

We also had a great time: Jim Allen's nightly walks around Eugene were quite nice, and we always ended up at a pub (if you like beer, they have lots of good ones in Oregon [my favorite: the Black Butte Porter, not to everyone's taste]). I met loads of people there and really enjoyed it. To PhD students in the US and abroad, I'd suggest you go to the Oregon Summer School in future years.