Dave Andersen's Blog

Just returned from a few days in Switzerland for HotOS XII (the workshop on Hot Topics in Operating Systems). Good workshop, good hiking, horrible airplane experience - really, who could ask for more? :)

link to all photos if you just read blogs for the pictures.

The workshop: Matt Welsh covered a lot of the technical meat in his blog already, so I won't repeat it here. Had a great continuation of the yummy-extravagant-dinners-at-conferences theme. Very enjoyable technical content and discussions. Keeping in mind that this list reflects my technical interests more than anything else (you'll note a strong multicore flavor in here), I'd particularly recommend taking a gander at:

• Hierarchical File Systems Are Dead
• Your computer is already a distributed system. Why isn't your OS?
• Hera-JVM: Abstracting Processor Heterogeneity Behind a Virtual Machine
• Reinventing Scheduling for Multicore Systems

I may be a bit biased on the last one, because I chatted about the broader work at length with Silas while hiking after the workshop. Still, it was nice work. And that brings us to...

The hiking: On Wednesday after the workshop, Silas and I wandered west from Monte Verita to a little mountain called Corona Dei Pinci and then to Alpe di Naccio. Great little afternoon hike.

On the following day, I decided to stubbornly forget that any form of transit other than foot existed, so I wandered to the nearby city of Locarno, and from there, went up an impressively steep staircase to a small hamlet called Monte Bre. It was staircases all the way up - about 900 meters of elevation gain.

From Mte. Bre, I found the wrong staircase that ended in prickly bushes and an intimidating electric fence that wrapped entirely around an impressive looking estate---which I decided to not photograph on the grounds that the occupants seemed to be zealously protective of their privacy already. And most Swiss houses are well-armed. But after that, the mountains opened up, I even found some snow, and got to the top of a rather nice mountain, Cima della Trosa (1900m) . Which, like every easily reachable peak in the area, seems to be decorated with an impressive crucifix.

I then wandered down the mountain and found that other people had figured out a better way down. Drawing inspiration from them, and already having experienced the joy of walking up the huge staircase, I hopped on the tram from 1300m to 400m to the upper reaches of Locarno.

Of course, there were still plenty of stairways , all of which were full of lizards.

Very cool trip overall. And, fodder for another post some time, I even made it back to the states a mere 5-ish hours late, despite a canceled flight from Zurich.

I figured I'd follow Michael Mitzenmacher's sigcomm PC post-analysis with a few ruminations of my own. Michael noted that the quality of submissions seemed down, and I'm one of the other PC members who agreed with this. I'm also on the SOSP 2009 program committee, and the quality gap is surprising, even compared to previous years. Comparing the papers I reviewed in sigcomm 2008 and 2009, where the scale is roughly logarithmic and "1" is bottom 50% and 5 is "accept or i will scream":

2008:
1:  1  2  3  4  5  6  7                (28%)
2:  1  2  3  4  5  6  7  8  9  10 11   (44%)
3:  1  2  3  4                         (16%)
4:  1  2  3                            (12%)

2009:
1:  1  2  3  4  5                      (31%)
2:  1  2  3  4  5  6  7                (44%)
3:  1  2  3                            (18%)
4:  1                                  (6%)

The total number of submissions was down slightly (288 in 2008, ~275 in 2009). There's a small bias because the number of later-round papers I reviewed was lower than in the previous year (reviews in round 2 omitted some of the lowest-ranked papers from round 1, which were "quick rejected"). In comparison, in my first round of SOSP reviews, I've already assigned one 5-equivalent.

Every PC is an experiment in how to run a PC, and this year's SIGCOMM was no exception. For background on this ongoing dialogue, it's worth peeking at some of the papers in last year's Workshop on Organizing Workshops, Conferences, and Symposia for Computer Systems -- we continue the debate about how to organize reviewing, double vs. single (or non)-blind review, accept papers, etc. Like last year, the PC was split into "light" and "heavy", where only "heavy" attended the PC meeting. The 2009 PC was larger (25 heavy, 35 light) than the 2008 PC (22 heavy, 24 light), and the per-reviewer workload was lighter (16 vs 25 papers). This is a useful experiment - one common complaint about serving on PCs is the time commitment. Unfortunately, I don't think this one worked out: my impression was that the room was a bit too full and individual PC members hadn't read enough of the papers to get as good a sense for the overall ordering of papers. Unfortunately, it seems there's some good that comes from a painful reviewing load in terms of having a good feel for the papers. I definitely like the way this and last year's PC structured things with heavy and light---those with more workload read a greater proportion of good papers, because the bottom 25% were rejected after the first round. This is a great way to preserve the sanity of your program committee.

There was (apparently; I didn't hear too much of it) some grumbling last year about the number of PC papers accepted. As a result, out-of-band papers were handled using a different website, along with some number of randomly selected additional papers. While this is a pretty sensible way to try things, it turned out to be really awkward - I couldn't login to the OOB website for weeks, and my guess is that the "randomly selected" papers took a hit by being reviewed separately from the main papers. It's clear that we need ACM (or some third party) to run a hosted instance of the HotCRP conference management software where the sysadmin and conference chairs are separate, so that the reviews are integrated but the chairs can't see who's reviewing their own papers, perhaps with some small tweaks to HotCRP to allow reviews to be assigned by an "OOB Chair". I note that USENIX has already started heading down this path.

Finally, I strongly encourage the next local host of the Sigcomm PC meeting to follow Brad Karp's lead and have an expert barista with a good espresso machine parked oustide of the meeting room. Simply awesome!

A while ago, I blogged about my Seattle espresso exploration, and lamented that I couldn't find such beasties in Pittsburgh. Charlie mentioned 21st Street Coffee and Tea.

Yum!

They've got the best espresso I've had in Pittsburgh, and it was the equal of the best espressos I had in Seattle. Rich and creamy, with a thick crema and a tingly acidity, and not a hint of bitterness. They use intelligentsia's Black Cat espresso blend, and it comes out very tasty. For the brewed coffee fanatics out there, they've also got a Clover machine. I highly recommend this place. Now we just need to convince them to open a copy of themselves near or at Carnegie Mellon.

I've extended the grow-lights to try to keep some plants going over the winter a bit better. Last year, my indoor plants stayed alive, but were never really happy. Theory: Not enough light, and they didn't like my 45 degree living room. No guarantees this will work. I'm using both the LEDs and the previous year's CFL, and have wrapped the ensemble in plastic. (Odd as it sounds, a combination of plastic wrap, of which I have oodles from a costco trip three and a half years ago, and some non-sticky window sealer plastic I haven't put up inside yet.) The bottom is wrapped in a mylar space blanket to reflect some of the light, and there's a mirror and some aluminum on top for the same reason.

---

You're in Calgary at the (quite fun) HotNets 2008 workshop. Your flight leaves at 10:45pm, promising to be a brain-draining three-flight red-eye back home. You want some exercise before the flight, but you've checked out of your hotel already. Combine with a bit of a habit of enjoying going places under your own power, and the solution seems obvious:

Walk to the airport.

It turns out that, in Calgary, it's possible. You might even take this route. The first 6 miles are great. Through Nose Hill park on trails through knee-high grass, with a great view of the city and lots of friendly people walking happy puppies. After that, though...

Advice 1: Don't try to cut through the under-development extension to the airport blvd. Climbing through a (stationary) train is a bit nervous. Getting stopped by a river afterwords just sucks, because you know that you then have to climb through the train again. And before you ask, the river was too wide to jump, and it smelled like cow poop. I met the cows a bit later when I went around the area to the north. They looked very surprised to see a human walking past on the freeway, as about fifteen pairs of cow eyes swiveled to intently track my progress.

Advice 2: Just ... stop at the 6 mile spot and call a taxi. The rest of the route gets very freeway-like. The overpass over highway 2 is particularly noteworthy, with its knee-high guardrail and rushing traffic inspiring mild vertigo even in a climber.

Advice 3: Ignore the above. You'll be chuckling about the time you walked to the airport in Canada for years to come...

A few other photos.

(Many thanks to Carey Williamson for suggesting a much better route than the one I'd initially picked!)

The trailing end of Hurricane Ike knocked out power for 85,000 people. As the old saying goes - no power, no crepes. (September 15th)

I was in Seattle a while ago for Sigcomm 2008. While there, I decided to go on a personal tour de seattle coffee shops. What I found were four excellent places to grab an espresso. Most serve double ristretto shots, rich, with a deep red crema and a surprising acidity. Forgive the lack of detail - they're all very good and I'd go to any of them again. You can't get espresso like this in Pittsburgh, alas, though I'm perfecting my technique on the machine at the Intel lab. :)

• Stumptown Coffee Roasters
• Vivace
• Victrola Coffee Roasters - not only very good espresso, but they offer cuppings on Wednesdays, which was quite fun. Nice selection of coffees to try.
• Stickman Coffee - Yelpers complain about the service, but the espresso was the thickest I've had and quite tasty. My biggest complaint was that they allow smoking in the attached courtyard, which would otherwise be a great place to hang out with a laptop for an afternoon.

http://twitter.com/dave_andersen.
Do you tweet? Post/link!

Brighten Godfrey gave a great outrageous opinions talk at sigcomm this year. [Warning: May only be funny to networking geeks.]

The naive reader will conclude that conjunctions went out of fashion in the mid 80's, and came back after the dot com crash. However, the inappropriately perspicacious reader realizes that this conclusion is subtly flawed, because the word "that" might be a pronoun, adjective, or adverb: not just a conjunction.

Our team did quite well overall at hood to coast. My legs:

leg 1:  46:19  6.56 miles (6:43)
leg 2:  34:50  5.00 miles (6:58)
leg 3:  57:02  7.79 miles (7:19)

overall:  2:18:11  19.68 miles  (7:01).

*just* missed my goal of doing sub-7 for the average. Ahh well, happy anyway. I blame it on one too many brownies at sigcomm. (Sigcomm update later.)

Team results:

18. 	Team Wildfire 	Pittsburgh, PA   Team #716
        25:07:24 	 7:39 	 18 / 283

Our time of 25:07:24 put us at 120th overall and 18th in the male mixed open. I'm not sure why we're listed there instead of male open, though, since we should have lost our "mixed"ness. We'd have been #26 / 214 in plain male open - not a huge difference.

For comparison, the winning team ran it in 16:58 (5:10 chip pace).

As hoped, however, we did beat the North American Distance Sprinters (the acronym was accompanied by matching van decorations...), at 36 / 283 (26:21:39, 8:01 pace), but we got whipped by a very fast women's team we played tag with for a while, the Pink Ladies (24:08:21, 7:21 pace). Very nice run overall. Now to proceed with two days of walking funny...

It's been a good running month. I decided to train a little bit for the upcoming Hood to Coast relay (two weeks from now). Each team has 12 members; each person runs 3 legs of about 6 miles. I'll be running legs 9, 21, and 33 (6.89 mi, 5mi, 7.79mi), for a total of 19.68 miles. Sadly, that's the longest leg and I'm not the fastest guy on our team, but I was greedy - it had the least punishing downhill section and the most time spent running on trail instead of road.

So, I did a quick ramp-up back to 14 milers on weekends and have been running about 37 miles per week for the last three weeks. Taking it easier this week before my knees start twitching, but it's felt suprisingly good - my last week was roughly three 8 milers and one 14 miler, plus a bit of cycling and swimming. I did sleep through cycling on Thursday, though - lack of sleep and lots of running finally caught up. I'm a fair bit over what I'd like to weigh for the race, but at least the distance feels good.

On the bright side of all of this, the BBC reports that running can slow the effects of ageing:

Running not only appeared to slow the rate of heart and artery related deaths, but was also associated with fewer early deaths from cancer, neurological disease, infections and other causes.

And there was no evidence that runners were more likely to suffer osteoarthritis or need total knee replacements than non-runners - something scientists have feared.

Bring on the miles!

My students found a shop at CMU where they could slice and dice the new FAWN rack. The results are awesome (and much more stable than the previous one):

Our FAWN (Fast Array of Wimpy Nodes) cluster is coming together. We've purchased 20 alix3c2 embedded boards, and have them netbooting and racked in our new home-brewed cluster rack:



The alix3c2s are larger than we think the nodes would be if we built them to purpose, but they're a great way to prototype the cluster. We've also found that you can power two alixes per power supply, and operating the power supplies at a higher load makes them run more efficiently, saving about half a watt per node.

(The goal of FAWN is to build a highly power-efficient cluster for doing key-value lookups, of the sort that Amazon and Facebook do when serving catalog requests -- fetch a picture of a book, an entry in someone's facebook page, etc.)

Erm - we took a lot of photos. Now online, courtesy of newly purchased space at Google:

• Rae Lakes Photos (242 photos)
• Hawaii Photos (246 photos)

And a new look for the blog, along with more prominent links to the RSS and Atom feeds.

I hosted Arvind Krishnamurthy for an SDI seminar talk today. Some notes from his very fun talk, which is based on two of his recent research projects, BitTyrant and One-Hop Reputations for P2P [pdf link].

• 20% of users use P2P systems. Enormously popular; 50-85% of Internet traffic.
• Youtube: 1,000 TB of data per day. BitTorrent: 10,000 TB of data per day.
• Prior P2P systems had very poor incentives: 1% of Gnutella users satisfied 50% of queries, and most Gnutella users didn't share anything.

Enter BitTorrent...

• Tit-for-tat: Send data to the top k people who send you data. Split your upload capacity equally between these k peers.
• Each round, pick one other peer to send data to "optimistically"
• Trust is pairwise, which is robust: Peers trust only what they see directly.

Observation: This system results in considerable amounts of altruistic uploads by fast peers. If a peer has a lot of upload capacity, it splits all of its capacity among the top-k peers. If those peers are relatively slow, it may upload much more than it's able to download.

• Low-capacity peers are altruistic: They're not fast enough to convince other people to upload to them, so they mostly make altruistic uploads.
• Many high-capacity peers are matched with sets of lower-capacity peers, and so make altrustic uploads.

BitTyrant:

1. Determine the exact (minimum) rate that you have to upload to a peer in order to convince it to upload back to you.
2. Figure out return on investment: How much they upload to you vs. how much you have to upload to them.
3. Upload to the peers that have the best return on investment.

Result: 25% of the downloads go at least twice as fast.

• Also uses less upload bandwidth to achieve same or faster download rate.
• If everyone uses BitTyrant: Overall performance is better, too.
• But: If BitTyrant stops uploading at point of diminishing returns (doesn't upload more than it must), system-wide throughput is lower. This behavior is closer to block-based tit-for-tat (you give me one chunk, I give you one). BitTorrent by default is like progressive taxation: High-capacity people upload disproportionately more.

Overall BitTorrent system performance is poor:

• 74% of swarms provide less than 50KB/sec.
• 100-fold increase in upload contribution provides only a 2.7x improvement.
• Problems: Lack of incentive to upload lots of data; lack of incentive to stick around after you finish downloading.

One-hop reputations can get most incentive bang for buck, in a way that is still scalable and decentralized:

• Most popular 2,000 peers interact with 97% of all peers.
• Use these popular peers as trust intermediates. Each peer remembers how much excess other peers sent to it. If A and B both send data to C, then each accrues a "credit" at C. Later, A can "spend" that credit at C in order to download from B, or vise-versa.
• Robust to cheating intermediaries as long as some are honest. (handwavy, pointed to details in paper.)

(Lava hitting the ocean at Volcano National Park)

Evening settling in on the Na Pali Coast, Kaua'i.

+ + = :)

I just got back from the ACM awards ceremony. I was there because Bindu was one of the finalists for the student research competition for her work on Similarity-Enhanced Transfer. Awesomely, she received first place. Needless to say, I'm happy as a clam for her, and very glad that Michael and I had the chance to advise her on this research.

The awards ceremony was lots of things--very cool, a bit too long, and a nice reminder of how cool computer science can be. In that regard, it was really energizing; I left thinking "damn! gotta work harder!" A few that really jumped out:

• Daphne Koller received a cool $150,000 with the Infosys Foundation award for her work on machine learning techniques.
• Vern Paxson received the Grace Murray Hopper Award for his work in the late '90s that set the standards for Internet measurement; a lot of my own subsequent Internet measurement work was directly inspired by Vern's techniques and insistence on taking a careful and scientific approach to network measurement.
• Randy Wang was recognized for starting the Digital Study Hall Project at MSR India, which is trying to revolutionize teaching materials in the developing world. Interestingly, it's been a great year for MSR India -- the gossip vine has it that Bill Thies, one of the hot job market candidates this year, turned down both Berkeley and Stanford to go work there, presumably to focus on his interests in creating technology for the developing world.(Note: This really is gossip; I haven't heard it from any party involved, so don't quote me!)

Finally, it was almost an embarassment of riches for Carnegie Mellon at the ceremony this year, which I've got to admit was really cool, if perhaps mildly awe-inspiring. It makes you remember that those really nice, unassuming folks I bump into every day in the hallway and in faculty meetings are also, if you'll forgive the phrasing, bomb-ass, famous researchers. Ed Clarke, of course, received the Turing Award; Randy Pausch received the outsanding educator award, Bindu's first place finish was mentioned above, two of the three dissertation award honorable mentions were to CMU people, and Avrim Blum, Randy Pausch, and Donald E. Thomas were all inducted as fellows.

And on that note, I leave for two weeks in the wilderness. A few days hiking the Rae Lakes Loop in the Sierra, and a week in Hawaii (hiking the Na Pali Coast on Kauai, then flying to the Big Island for adventures TBD).

Hpricot is a frighteningly useful HTML parser. USENIX requires HTML versions of papers at their conferences, so we're creating versions of Dan's Perspectives and Bindu's Dsync papers. Amar and Vijay started an automated framework based on the Hevea LaTeX-to-HTML translator a while ago, which we've now improved further.

(For some reason, automated TeX-to-HTML translators mostly suck, particularly if you want clean, XHTML-strict output. Hevea appears to be the best of the batch, but its output is still pretty awful.)

Enter Hpricot. Our cleanup.rb script uses it to automatically de-gunk most of the Hevea output. It's awesome for manipulating most any HTML, though. You can write things like:

doc = Hpricot(open("index.html"))
# Nuke credits and comments
doc.search("//meta[@name='GENERATOR']").remove
doc.search("//comment()").remove

and more complicated things, like removing extraneous "font" tags from the bibliography list:

doc.search("//dl[@class='refs']/dt/font").each { |f|
    f.parent.inner_html = f.inner_html
}

(That reads "for every font tag that appears inside a DT item that is inside a DL of class refs, replace the font tag and everything it contains with the stuff it contains.)

The downside is that since I can make Ruby about as functional as I want (minus the static typechecking. argh), and it has awesome libraries like Hpricot, it makes it a little harder to make myself do more serious work in Ocaml...