Highlights from EWSN 2010

I was invited to give the keynote speech at the European Wireless Sensor Networks conference in Coimbra, Portugal. This was a fantastic location for a conference -- Coimbra has one of the oldest universities in Europe, over 700 years old. It's a beautiful city. EWSN is the European counterpart to conferences such as SenSys and IPSN. It is a very different crowd than typically attends those events. I learned a lot about a couple of the big EU-sponsored sensor nets projects including CoNet and GINSENG. Interestingly, the Contiki OS seems to be pretty popular amongst the European research groups, in contrast to the TinyOS-dominated US landscape.

My keynote was entitled "The Next Decade of Sensor Networking" and I tried to argue that the field is running the risk of becoming stagnant unless we define some big research challenges that will carry us for the next decade. I've blogged about these themes here before. I delivered the talk in "Larry Lessig" style -- having written the "script" as an essay and then making slides to highlight the key points, rather than starting with the slides and ad libbing the voiceover as I usually do. I'll post a video here soon - the slides are more than 50 MB and don't really go well on their own.

A couple of highlights from the conference, though I had to miss the last day.

Jayant Gupchup from Johns Hopkins gave a talk on Phoenix, an approach to reconstructing the timestamps for sensor data after the fact. The idea is to not use a time synchronization protocol, but rather have nodes log enough data that can be used for post-hoc time correction. This is an interesting problem that was motivated by their experiences running sensor nets for more than a year, in which they observed a lot of node reboots (which throw off simple timing approaches) and extended periods when there was no suitable global timebase. The Phoenix approach collects information on nodes' local timestamps and beacons from GPS-enabled nodes at the base station, and performs a time rectification technique, similar to the one we developed for correcting our volcano sensor network data. Phoenix achieves around a 1 sec data accuracy (which is acceptable for environmental monitoring) even when the GPS clock source is offline for a significant period of time.

Raghu Ganti from UIUC gave a talk on "Privacy Preserving Reconstruction of Multidimensional Data Maps in Vehicular Participatory Sensing." The title is a bit unwieldy, but the idea is to reconstruct aggregate statistics from a large number of users reporting individual sensor data, such as their vehicle speed and location. The problem is that users don't want to report their true speed and location, but we still want the ability to generate aggregate statistics such as the mean speed on a given road. Their approach is to add noise to each user's data according to a model that would make it difficult for an attacker to recover the user's original data. They make use of the E-M algorithm to estimate the density distribution of the data in aggregate.

Although the paper considered a number of attacks against the scheme, I was left wondering about a simple binary revelation of whether a user had recently left their home (similar to PleaseRobMe.com). One solution is to delay the data reporting, although one would be able to learn the approximate time that an individual was likely to leave home each day. The other approach is to perturb the timing data as well, but this would seem to interfere with the ability to ask questions about, say, traffic levels at certain times of day.

Finally, Christos Koninis from the University of Patras gave a talk on federating sensor network testbeds over the Internet, allowing one to run testbed experiments across multiple testbeds simultaneously, with "virtual" radio links between nodes on different testbeds. So you could combine a run on our MoteLab testbed (around 190 nodes) with the TWIST testbed (220 nodes) to get a virtual testbed of more than 400 nodes. This is a very cool idea and potentially extremely useful for doing larger-scale sensor net experiments. Their approach involves routing data over a node's serial port through a gateway server to the other end where it is injected into the destination testbed at the appropriate point. They can emulate a given packet loss across each virtual link, not unlike Emulab. Unfortunately they did not really consider making the cross-testbed packet transmission timings realistic, so it would be difficult to use this approach to evaluate a MAC protocol or time sync protocol. It also does not properly emulate RF interference, but I think this is still a very interesting and useful ideas. Another cool aspect of this project is that they can add virtual simulated nodes to the test
bed, allowing one to run mixed-mode experiments.

David Shaw's Anton Supercomputer

Today, David Shaw of D. E. Shaw Research delivered a Distinguished Lecture in Computational Science here at Harvard (this is a new seminar series that Ros Reid and I cooked up to bring in a few high-profile speakers each semester). Of course, prior to forming D. E. Shaw Research, David founded D. E. Shaw and Co., a hedge fund which was one of the most successful quantitative analysis shops. Since 2001, David has been doing research full time -- D. E. Shaw Research develops both algorithms and customized machine architectures for molecular dynamic simulations, such as protein folding and macromolecule interactions. The result is the Anton supercomputer, a heavily customized machine with 512 specialized computing cores specifically designed for particle interaction simulations. It was a great talk and was very well attended -- I'll post the video once it's available.

David presented the algorithms and architecture behind the Anton machine. The goal is to run molecular dynamic simulations of molecules on the order of 50,000 atoms for 1 millsecond of simulated time. The performance target for Anton is 10,000 simulated nanoseconds for each day of compute time. To put this in perspective, the fastest codes on conventional parallel machines can muster around 100 ns of simulated time a day, meaning that 1 ms of simulated time would take more than 27 years to run. Anton can do the same in around 3 months. Prior to Anton, the longest simulations of these macromolecules that have been done to date are on the order of a few microseconds, which is not long enough to see some of the interesting structural changes that occur over longer time scales. (1 ms may not seem like a lot but it's amazing how much happens to these proteins during that time.)

Basically, each of the 512 nodes consists of a heavily pipelined special-purpose ASIC that is designed to compute the particle force interactions (using an algorithm called the NT method), along with a general-purpose processor that supports a limited instruction set. Communication is heavily optimized to reduce the amount of data exchanged between nodes. The processors are connected into a 3D toroidal hypercube and each processor "owns" a set of particles corresponding to a particular cube of space. They have built eight 512-node machines with a 1024-node machine coming online in March. They are working to make one of these available free to the research community to be hosted at the Pittsburgh Supercomputing Center.

The best part of the talk was the animations showing visualizations of a protein structure evolving over time. A movie showing just 230 usec of gpW showed substantial structural changes including partial unfoldings of the manifold. Apparently these dynamics have never been observed in other simulations and it's incredible how much insight the longer time scales can reveal.

David was very cool to talk with -- over lunch the conversation ran the gamut from computer architecture to quantum chromodynamics. I never got a sense of whether D.E. Shaw Research has any plans to commercialize this -- they really seem to be in it for the research value, and consider Anton just a tool to make discoveries. (Of course, I can imagine such a "tool" would be pretty lucrative to the drug-discovery industry.) This is a project is a great example of what's possible when computer scientists and domain scientists work closely together.

The dumbing down of operating systems

Yesterday's announcement of the Apple iPad -- basically an iPhone with a larger screen and no camera -- ushered in a new era for OS design. That is, an OS that was originally designed for a phone (the "iPhone OS", which is itself a stripped down version of Mac OS X), is now being ported over to larger, much more capable devices. I have no doubt that the iPhone OS will be very successful on the iPad. It would not surprise me to see it running on laptops and desktops in the near future. This simplified OS eliminates most of the complexity that makes people hate computers: the quagmire of configuration options, keeping up with upgrades, and of course the constant battle against viruses and malware. When I first saw the iPad, I immediately recognized that this is going to be the perfect computer for "non-computer users", like my dear mother-in-law, who pretty much only uses her Windows PC to read email and surf the web. (I'm not sure she's ever saved a file to the hard drive.) But it's also going to be the perfect computer for those of us who just want something that works. Like the original Macintosh, the iPad raises the bar of user-centric computer system design. It is elegant in its minimalism and simplicity.

Still, this trend of dumbing down the OS raises some interesting questions. The iPad OS lacks many features that operating systems have had for decades: multitasking, an open application API and development tools, multiple protection domains -- heck, it doesn't even have a proper filesystem. Arguably, it is this lack of features that makes the iPhone and iPad platforms so attractive to application developers and users alike. This trend suggests very strongly that the feature-rich, complex OSs that we love so much are going to look too baroque, top-heavy, and expensive to survive in a field where the "OS" is little more than GUI gloss over a pretty basic system. (Something tells me that in a few years we're going to get iPad OS v2.0 which builds in some of these "advanced" features that date back to the 1960's.)

Basically, what I'm saying is that the iPad would appear to make most current OS research irrelevant. Discuss.

(Update: Check out this petition that claims that the iPad's DRM is "endangering freedom." I'm not sure I'd go that far, but an interesting perspective nonetheless.)

The coming e-book armageddon

I may be jumping the gun a bit here, but with this WSJ article on the potential pricing models for e-books on the Apple Tablet, I am very worried about the future of e-books. Books used to be these paper things that you could get just about anywhere, not require a specialized device to read, lend to your friends, borrow from a library, scribble in, or use to prop a door open. It seems clear that paper books are about to go the same route as the compact disc, but the e-book industry is getting it all wrong by tying themselves to proprietary, closed formats that only work on certain devices from certain vendors. It seems like I hear about a new e-book reader every day on sites like Engadget, but every vendor has the same problem: getting content and agreements with the publishers to support their device. Amazon has done a great job establishing those relationships for the Kindle, and now it seems Apple is going to have to do the same legwork for their tablet. It seems inevitable that we're going to end up with a VHS-versus-Betamax style format war between the two platforms. This does not bode well for the e-book industry.

Let me make it clear that I love e-books. I've been doing a ton of reading on the Kindle App for the iPhone, having recently read Dennis Johnson's Tree of Smoke and Cormac McCarthy's The Road (and a few other not-so-great books that don't need my endorsement here) exclusively on the iPhone. (Yes, the tiny screen works - I can actually read faster with a narrower horizontal view of the text.) I particularly like having a half-dozen or so full-length books in my pocket at all times: if I weren't so busy reviewing papers for program committees I'd probably do more "fun" reading this way. But I really don't know if the Kindle e-books have any staying power. I certainly won't be able to hand them down to my son when he's old enough to read them. And will I have to buy them again, in a different format, for a different device, ten (or five or two) years from now when the next hot e-reader device comes on the market? What a pain.

Publishers should have learned their lesson from the music industry. Anybody remember the early digital Walkman that required you to encode your music in a DRM format and "check out" music from your library on the PC to the portable device? It was a total failure. Although Apple's AAC format is closed, iPods are quite happy to play MP3s, and arguably MP3 won the format war. I know full well that MP3 is far from the "best" format from a technical perspective, but pretty much every device I own knows how to play it, and it seems likely that it will stick around for a while. Better yet there are plenty of open source implementations that can encode and decode the format, so my music library is not locked down.

My final worry is what closed e-book format mean for accessibility of books and (to risk hyperbole) the wealth of human knowledge. In a decade, maybe only the rich kids with fancy Kindles or iSlates will be able to read the good stuff like Harry Potter, while the poor kids with only access to crummy public libraries will have to make do with yellowing, dog-eared paper (!) copies of Encyclopedia Brown novels. If books are really going all electronic, I think we need to think now about how to avoid creating a technology gap that closes certain people off from getting access.

Sensor networks, circa 1967

What was the first sensor network? Thinking back, I bet most people would guess the early demos by Berkeley and UCLA at places like the Intel Developer's Forum; the Twentynine Palms air-dropped mote demo; and Great Duck Island. These were all around 2002 or so. It turns out this is off by about 35 years -- the first bona fide wireless sensor network was actually deployed in Vietnam, along the Ho Chi Minh Trail, in 1967. It was called Igloo White.

I've been doing a lot of reading about Igloo White lately, and while most of the information on the program is still classified, there are a bunch of articles, books, and a few websites that provide some useful details. Igloo White was a system designed to use seismic and acoustic sensors to detect PAVN movements along the Ho Chi Minh Trail from North Vietnam, through Laos, and into South Vietnam (thereby skirting the DMZ). It consisted of wireless sensors, typically dropped from helicopters and aircraft. In all nearly 30,000 sensors were deployed during the war. (The image above shows an airman about to drop an Igloo White sensor from a helicopter.)

You can read much more about Igloo White elsewhere, but some juicy tidbits that caught my attention. The sensors themselves were shaped like large artillery shells and buried themselves in the ground, with a radio antenna designed to look like the surrounding jungle foliage. They used lithium batteries with an expected lifetime of 30 days. Each sensor performed simple local thresholding and triggered a movement alarm when a certain level of activity was detected. (All of this was done with analog circuity: at the time a digital computer was the kind of thing that filled a good portion of a room.)

The sensors would transmit a 2W signal on the UHF band which would be picked up by orbiting EC-121R aircraft that flew 24/7 on rotating 18-hour missions over various parts of the sensor field. The personnel on board would listen to the transmitted acoustic signals, and attempt to classify the targets. They could even identify specific trucks based on the acoustic signature of the engine. Detections were relayed to a top-secret SIGINT center at Nakhon Phanom, Thailand, where the data was stored by IBM 360 computers and processed largely by human analysts. The analysts would then call in air strikes against the targets. Note that in many cases the bombing runs occurred at night, using ground-based RADAR for bomb guidance, so the pilots never even saw what they were hitting. Presumably they could go from target to detection to, ahem, interdiction, in less than five minutes.

The most incredible thing about Igloo White was the sheer amount of resources that were poured into the program: the whole thing went from concept to reality in little more than a year, and cost more than a billion dollars. The system relied entirely on human analysts to interpret the sensor data, which was often noisy; later in the program the North Vietnamese became adept at spoofing the sensors. The number of people involved in deploying the sensors, monitoring the signals, and interpreting the data was almost inconceivable; the operations center in Thailand was the largest building in Southeast Asia at the time, complete with air conditioning, positive pressure, and airlocks to prevent contaminants from damaging the computers inside. This is not the kind of thing you're going to do with two grad students and a half-million in NSF funding!

The I-REMBASS system from L3 Communications represents the state-of-the-art in (deployed) military sensor networks. And, of course, much of the modern work on sensor nets came out of DARPA programs such as NEST. Still, it's fascinating to see the history behind this technology.

The Paper Formatting Gestapo

I've recently had two conference submissions "rejected with prejudice" for violating the formatting requirements. In both cases, it was because the lead grad student on the paper didn't read the call for papers carefully enough. (I'll take my share of the blame for not checking it, but sometimes it's pretty hard to check without pulling out a ruler and counting lines of text by hand.) Now, I totally agree with those papers being rejected: it's essential that papers adhere to the formatting requirements. On the other hand, it certainly does not help that every conference uses slightly different guidelines. Here's a typical formatting convention:

Submitted papers must be no longer than 14 single-spaced pages, including figures, tables, and references. Papers should be formatted in 2 columns, using 10 point type on 12 point leading, in a text block of 6.5" by 9".

Another one:

Submissions must be full papers, at most 14 single-spaced 8.5" x 11" pages, including figures, tables, and references, two-column format, using 10-point type on 12-point (single-spaced) leading, with a maximum text block of 6.5" wide x 9" deep with 0.25" intercolumn space.

Yet another (from SIGCOMM 2009):

• Submissions MUST be no more than fourteen (14) pages in 10 point Times Roman (or equivalent font). This length includes everything: figures, tables, references, appendices and so forth.
• Submissions MUST follow ACM guidelines: double column, with each column 9.25" by 3.33", 0.33" space between columns.
• Each column MUST contain no more than 55 lines of text.
• NOTE: For the submission, you may use the following LaTeX template to ensure compliance.
• The final copy will be 12 pages using the SIGCOMM standard 9 pt format; this is less than what you might be able to fit in 14 pages at 10pt, and so there is no value in pushing the envelope.
• Provide an abstract of fewer than 200 words.
• Number the pages.
• Do not identify the papers' authors, per the Anonymity Guidelines.
• On the front page, in place of the authors' names, the paper MUST indicate: the paper ID number assigned during the paper registration process and the total number of pages in the submission.
• The paper MUST be submitted in PDF format. Other formats (including Postscript) will not be accepted. We must be able to display and print your submission exactly as we receive it, using only standard tools (Adobe Acrobat Reader), with no loading of special fonts.
• Make sure that the paper prints well on black-and-white printers, not color printers. This is especially true for plots and graphs in the paper.
• Make sure that the output has been formatted for printing on LETTER (8.5" by 11") size paper.
• Make sure that symbols and labels used in the graphs are readable as printed, and not only with a 20x on-screen magnification.
• Try to limit the file size to less than 15 MB.

This is getting silly. Even conferences sponsored by the same organization (say, USENIX or ACM) have different formatting guidelines. In one case, our paper was rejected because it was a resubmission from a previous conference that used an oh-so-slightly different format.

Now, I am all for having a consistent, and firm, formatting requirement for conference submissions. It's really unfair to authors that take pains to adhere to the guidelines when someone violates them by squeezing too much text into the paper. But isn't it time that we define a single standard for conference paper formatting that everyone uses?

Yes, I know there are various templates out there, but most of these are for the final proceedings, which can vary substantially from the submission format. Even worse, many of the "standard" templates floating around out there don't adhere to the submission guidelines anyway. What would help tremendously would be to have a canonical standard template (in various formats, e.g., LaTeX and Word) that everyone uses. Then it would be trivial to tell if someone had tweaked the formatting since their paper wouldn't look the same as the rest. This is the model used by EWSN 2010 (which required submissions to be in the Springer LNCS format) and it worked very well -- all of the submissions had consistent formatting.

A word on automatic format checkers. Both of the conferences we submitted to were supposed to be using an automated format checker that should have flagged the paper as violating the requirements when we submitted it. In both cases, this failed, and the program chairs (quite rightly!) rejected the paper once they discovered that the formatting was wrong. Unfortunately we were not careful enough and assumed that passing the automated check meant that we had done everything correctly. I like Geoff Voelker's Banal system, but it doesn't always work (mostly the fault of the underlying Ghostscript tool that it's based on). Even doing this kind of thing manually is a big pain -- Adobe Acrobat Pro lets you measure things like text blocks and font sizes, but it's a lot of manual effort.

Finally, as a TPC chair I have been on both sides of this, and I always hate rejecting papers due to formatting violations, especially when I know the authors have done good work. Dealing with formatting problems is a huge time sink when you're running a conference, and a standard format would save everyone -- authors, program chairs, reviewers, publication chairs -- a lot of trouble. I think it's time for the systems and networking community to simply define a single standard and get all conferences to use it.

The CS Grad Student Lab Manual

Should CS grad students be required to receive formal training in lab technique?

In most scientific disciplines, a great deal of attention is paid to proper experimental design, data collection, and analysis. A grad student in chemistry or biology learns to adhere to a fairly rigid set of procedures for running an experiment (and documenting the procedure). In CS, we largely assume that grad students (not to mention professors and undergrads) somehow magically know how to do these things properly.

When I was a grad student, I more or less figured out how to run benchmarks, collect and record data, document experimental setup, analyze the raw data, and produce meaningful figures on my own. Sure, I had some mentorship from the more senior grad students in my group (and no small amount of pushback from my advisor when a graph would not make sense to him). But in reality, there was very little oversight in terms of how I ran my experiments and collected results. I logged benchmark output to various homebrew ASCII file formats and cobbled together Perl scripts to churn the output. This evolved considerably over time, adding support for gzipped log files (when they got too big), automatic generation of gnuplot scripts to graph the results, and elaborate use of Makefiles to automate the benchmark runs. Needless to say, I am absolutely certain that all of my scripts were free of bugs and that the results published in my papers are 100% accurate.

In my experience, grad students tend to come up with their own procedures, and few of them are directly verifiable. Sometimes I find myself digging into scripts written by one of my students to understand how the statistics were generated. As an extreme example, at one point Sean Rhea (whom I went to grad school with) logged all of his benchmark results directly to a MySQL database and used a set of complex SQL queries to crunch the numbers. For our volcano sensor network deployments, we opted to log everything using XML and wrote some fairly hairy Python code to parse the logs and generate statistics. The advantage of XML is that the data is self-describing and can be manipulated programmatically (your code walks the document tree). It also decouples the logic of reading and writing the logs from the code that manipulates the data. More recently, students in my group have made heavy use of Python pickle files for data logging, which have the advantage of being absolutely trivial to use, but the disadvantage that changes to the Python data structures can make old log files unusable.

Of course, all of these data management approaches assume sound experimental technique. Obvious things include running benchmarks on an "unloaded" machine, doing multiple runs to eliminate measurement error, and using high-resolution timers (such as CPU cycle counters) when possible. However, some of these things are more subtle. I'll never forget my first benchmarking experience as an undergrad at Cornell -- measuring round-trip latency of the U-Net interface that I implemented on top of Fast Ethernet. My initial set of runs said that the RTT was around 6 microseconds -- below the fabled Culler Constant! -- beating the pants off of the previous implementation over ATM. I was ecstatic. Turns out my benchmark code had a small bug and was not doing round-trip ping-pongs but rather having both ends transmit simultaneously, thereby measuring the packet transmission overhead only. Duh. Fortunately, the results were too good to be true, and we caught the bug well before going to press, but what if we hadn't noticed?

Should the CS systems community come up with a set of established procedures for running benchmarks and analyzing results? Maybe we need a "lab manual" for new CS grad students, laying out the best practices. What do people think?