Previous Entry Share Next Entry
10:21 pm, 18 Nov 04

UW industrial affiliates

A while back I went to the University of Washington for recruiting and got to catch a bunch of student presentations as well as see some posters. I have some notes on a few that especially caught my attention, but please keep in mind that I'm only summarizing my understanding of the ideas and could very well have it wrong.

One presentation was on an "atomic" extension for programming languages. The semantics of the construction are a different approach to locking: the idea was that code within an "atomic" block could execute atomically, without other threads having any knowledge of the atomic code. The trick was that this can be implemented particularly efficiently on a rather common setup: uniprocessor systems with VM- (that is, not OS-) level threads. The approach they took was to basically execute the atomic code directly without any special handling, except that if a thread was interrupted within an atomic block, its effects would need to be "rolled back" to be attempted later. I think the approach to rolling back was to buffer effects and then execute them (with interruptions suspended, I imagine) at the end of the atomic block. I had an interesting discussion with Michael afterwards about what exactly that means (I have here in my notes "what about multiple dependent effects?" but not the resolution). Oh, but it looks like they have a website now, so maybe that'll better any questions.

Another was on a client implementation for a database that detects unauthorized modifications on the server. The approach used Merkle trees--as I understood it, you'd compute a tree of hashes of subsets of the data (you store a hash for each fact, a hash for each pair of hashes, a hash for each pair of pairs, etc.), and store the topmost hash on the client. Requests would ask for the hashes not along the tree on the path to the data, allowing the client to verify the data as long as as you have normal hashing properties. (That is: if the attacker modifies something on the left branch of the tree, they can't produce a hash for the right branch of the tree such that the hash across both branches will match what the client expect at the node itself.)
The idea seemed rather clever, but there were plenty of limitations: for example, you can only detect that tampering happened, and not what the tampering was; even valid clients can't insert data (because it changes the tree's layout), only modify data; and you can't have multiple clients. It deserves more thought but I'm not really familiar with the problem space.

Finally, some people working on PlanetLab had an nifty approach for monitoring outgoing node bandwidth. (Briefly, PlanetLab is a network of computers that allow researchers to perform experiments that need sources in multiple locations across the planet; for example, attempts at mapping the Internet using traceroute can use traceroutes from multiple sources to better see the topology.) The problem is preventing DoS-style attacks while still allowing researchers to perform tests using the entire network; by sending only 1k/sec from 1000 nodes, a malicious user could push 1mb/sec on a victim. Their approach had nodes send warning/status updates to each other with probability inversely proportional to the sending rate of the user: so the probabilities work out that sending half as much traffic through twice as many nodes is equally likely to trigger a node requesting a check.
However, it wasn't quite clear what sort of checking was going on; if the nodes all have to check with each other to compare flow rates, there's still an N^2 communication going on.

Following these talks (and many others), there were also a lot of posters, and in particular some interesting graphics projects. Unfortunately I didn't take any notes so they'll have to just remain in my memory. There was one project in particular that had many interesting and useful applications, and the girl presenting it said they were going to open-source it. If I dig it up I'll be sure to post about it.