SIGCOMM 2009

For readers interested in networking, I note that the SIGCOMM 2009 program is now available.

Also available is Pathlet Routing, our paper with Igor Ganichev, Scott Shenker, and Ion Stoica. Pathlet routing is a new Internet routing architecture which can improve scalability by enabling very small forwarding tables, and can allow senders to choose between multiple paths for improved reliability and path quality. The idea is basically to do source routing over a virtual topology whose nodes are arbitrary virtual nodes (vnodes) and whose links are sequences of vnodes (pathlets). Intuitively, this architecture is highly flexible because vnodes can represent arbitrary granularities, and because pathlets can represent policy constraints on routing while simultaneously enabling a large number of path choices. This is because sources can stitch together pathlets to form an end-to-end route in potentially exponentially many ways.

An interesting property of the design is that it doesn't impose a global requirement on what "style" of routing policy is used, but rather allows multiple styles to coexist. One router could choose to have routes like in today's Internet, with a giant forwarding table specifying only a single allowed route to each destination. And the next router could have a tiny forwarding table that still gives the network owner some control, but provides a high degree of path choice for the senders. I think of this as being very much in the spirit of the principle of designing for variation in outcome advocated by Clark et al. in their Tussle in Cyberspace paper.

Progress

Gallup has asked, "If your party nominated a generally well-qualified person for president who happened to be X, would you vote for that person?" for X = {Catholic, black, Jewish, female, hispanic, Mormon, homosexual, atheist}. Here is a plot of the results over time.

Angel Island fire

Happening right now, a large fire on Angel Island visible around the San Francisco Bay. For size comparison, the island peaks at 788 feet; in the third picture is what I think is a three-story ferry. See also SFGate photos.

How Berkeley Can You Be?

A few photos from the Thirteenth Annual "How Berkeley Can You Be!?" Parade, Sunday, September 28, 2008.

An arbitrage opportunity

Nate Silver noted a discrepancy between the market prices for bets on who will win the presidential election at Intrade vs. other markets like the Iowa Electronic Market, with strange bidding patterns at Intrade. More discussion over at Computational Complexity. To help visualize it, here is a graph of the closing prices of PRESIDENT.DEM2008 at Intrade and PRES08_WTA at IEM. Update: CQpolitics: Trader Drove Up Price of McCain ‘Stock’ in Online Market It certainly looks as though there's been an unusually large difference in prices lately.

Recent results in nonlinear peer-to-peer reviewing algorithms

On Monday I received spam, as many periodically do, from the World Multi-Conference on Systemics, Cybernetics and Informatics, WMSCI '09. Their peer review process having been previously demonstrated by Stribling et al. to be susceptible to random paper generation, they have a new strategy:

Submitted papers or extended abstracts will have three kinds of reviews: double-blind (by at least three reviewers), non-blind, and participative peer-to-peer reviews.

(Emphasis mine.) The conference web site further describes the peer-to-peer review process as

Informal, nonlinear, systemically interactive methods, for the achievement of what is called bottom-up quality[.]

This is great news; as a sometime peer-to-peer researcher myself, I'm eager to see nonlinear peer-to-peer reviewing technology adopted.

I understand that as future work WMSCI is developing an oblivious algorithm for ad-hoc low-power reviewing.

Computer Science Research Trends

Computer science is a fast-changing field of research. Can we track some of its changes in the past? To answer this or any other question, experimental computer science researchers have essentially three options:

1. Write a program.
2. Search the Internet.
3. Write a program that searches the Internet.

We'll take the last approach in this post. We can pick a term and look at term frequency, that is the fraction of abstracts containing the term, as a function of time. Conveniently the ACM Digital Library and Guide have an advanced search that we can exploit to analyze term frequency across decades of abstracts. We'll start with a generic term, performance:

Let me say now, in case it becomes unclear later, that all the data presented here is actually derived from the ACM's database; it is not made up. (As for the interpretation of the data, well, ...) Moving on, we can plot a couple other terms, which and that:

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. Fortunately the astute reader realizes we can look at relative instead of absolute frequencies to help clean up the data set.

The next group of figures are normalized by the term performance. For example, the blue line in the first plot below shows freq(mobile) / freq(performance).

Select plot: performance, interactive, mobile, ad hoc proof, simulation, experiment TCP, RAID, BGP, DHT supercomputer, cluster, data center simple, efficient, correct, reliable system, algorithm, network, database Click on the image below for a larger version.

Now some "matchups", where x v. y = freq(x) / freq(y). Click on an image to enlarge.

distributed v. centralized
flat v. hierarchical
Berkeley v. Stanford
Us v. Them

They're winning, but we're gaining on Them.

Now our final, and perhaps most important, plot.

Good v. Evil

While computer science is solidly on the side of good, several abstracts in this search were disturbingly megalomaniacal, such as J. R. Landry's "Can computing professionals be the unintentional architects of evil information systems?", in ACM SIGMIS-CPR, 2008. The author "discusses how the technical rational paradigm supports the creation of systems that embody administrative evil" and aims to "determine if information systems can harm or be evil, the frequency of harm, and response to harm by designers and users."

We can be thankful that according to its abstract, the paper is only "a research-in-progress".

This post was originally an Outrageous Opinion at SIGCOMM'08. Here's a PDF of the original presentation.