Thoughts on Systems

Emil Sit

Jun 1, 2006 - 4 minute read - Research conferences

NSDI 2006, Day 3

Finally, closing out my NSDI 2006 summaries: sessions from the last day. I hope you’ve found these useful; maybe they’ll inspire some interesting NSDI 2007 submissions. Get started today!

Wireless and Sensor Networks

Ming Li had the unenviable position of giving the first talk on the last day; much like my post lunch talk on the first day, people drifted in during his talk. (On a personal note, Ming also had the unenviable position of having to take a red-eye to Newark, NJ, followed by a connection to Hartford, CT and a drive back to Amherst.)

Sensor network research usually focuses on getting data transferred using minimal power while trading off the least amount of accuracy and freshness. Ming’s talk on PRESTO showed his contribution to the area: instead of putting intelligence about what to send or request solely at the collection sites or in the sensors themselves, PRESTO splits that intelligence. Both the collection proxy and the sensors maintain a (simple) model to predict what is expected: the sensor needs only send data to the proxy when it is anomalous. When anomalies are detected, both the proxy and the sensor can update their model if necessary; the proxy can also back-interpolate old data to increase accuracy based on the new data point. As a result, PRESTO is able to provide better accuracy using fewer transmissions and thus less power.

Cheng Tien Ee spoke next about an algorithm called PathDCS. It’s also designed for efficiency in sensor networks in a model where data about specific types of observations (e.g., presence of elephants or tanks) are forwarded to a well-known rendezvous sensor-node for aggregation. Queries can then be sent directly to the rendezvous node. PathDCS makes use of reference points called beacons; data is forwarded towards beacons along existing paths. The details of the work are in how these paths are able to minimize the stretch (number of hops required relative to a direct path, which would be hard to calculate and disseminate).

The third talk focused on geographic routing, where each node attempts to route packets greedily to a node closer to its destination based on the known physical/geographic coordinates of its neighbors and the destination. Ben Leong, soon to be a professor at the National University of Singapore, described an algorithm for getting around the problem of dead-ends in the topology. In a greedy algorithm, you might try to cross a lake by going to the end of a pier, but at that point, you can not get any closer without backtracking. Ben showed an algorithm for figuring out the shorter path around the outside of the lake, without having to do an expensive technique called graph planarization. Instead, two opposing spanning trees are constructed; from the dead-end, you walk towards the root of closer spanning tree until you can see your destination. When you are close enough, you can revert to greedy forwarding. This has worked extremely well in simulation and he hopes to validate it on real networks soon.

File and Storage Systems

The theme of the last session was revision trees for managing multiple versions of filesystems, disk images and directory trees.

Ben Pfaff gave the talk about Ventana, a Virtualization Aware File System. Ventana provides an NFS interface to multiple versions of filesystems in order to support the versioning across virtual machines. The connection seems a little tenuous; however, the paper does explore to some extent the question of how to protect different versions of filesystems by introducing a number of different access control lists.

Olive is the latest extension to FAB, a system for building high-performance disk storage without using RAID. Olive allows administrators to branch disk volumes easily, allowing them to play with changes without worrying about messing up known-good volumes. By operating at the volume level, Olive can be filesystem agnostic. Volumes can be cloned into read-write copies or frozen into read-only snapshots. The cloning mechanism winds up being cheap and provides linearizable crash-consistency (probably the best you can do at the volume level, without knowledge of what FS is running over the volume).

Alex Yip closed the conference by introducing Pastwatch; Pastwatch is a system that provides distributed version control, much like Mercurial, git, and a cast of dozens more. Pastwatch uses revtrees, which are essentially tree snapshots, to automatically track and manage simultaneous writes and conflicts. It’s my understanding that the ideas used in Pastwatch are similar to those used in Mercurial; I suspect that Mercurial is significantly better tested, given that it has been adopted by OpenSolaris. However, a small group of researchers at PDOS do use Pastwatch regularly for production work. I can’t really keep up with all the different features and benefits of the different systems to do a better comparison. An interesting aspect of Pastwatch is Aqua, a system for highly-available hosting of Pastwatch projects. This area might be ultimately more relevant than the version control aspects of Pastwatch.