One of my first posts on this blog was titled, “Traffic Deadlock”. Deadlock is a classic pitfall when dealing with mutual exclusion, and another pitfall is “starvation.” Starvation occurs when a process cannot acquire a shared resource (and thus cannot make progress). Typical implementations of locks (like pthread’s mutexes) do not preserve FIFO ordering of acquisition requests, so the locks are not fair. If you have three threads — A, B, and C — and they all want access to the same shared resource, B might starve as follows: A holds the lock and B blocks trying to acquire it. Right as A releases the lock, C also tries to acquire it and wins over B because the lock does not enforce fairness. Then B is still waiting on the lock while C uses it. Right as C releases the lock, A tries to acquire the lock and wins over B. This could continue indefinitely before B gets the lock. In practice B’s “bad luck” usually doesn’t happen for too long, because thread scheduling and fluctuations in computation time perturb the system enough to make this rare. So fair FIFO locks are usually only used when you need lower variance and more predictability (since there is more overhead associated with them).

But sometimes there are structural asymmetries in the system that make starvation more likely and fairness more important. For example, reader-writer locks make it easier to starve writers if more readers can always enter while the lock is in reader mode (because writers must wait until all readers are done before acquiring). This brings me to the traffic scenario below:

A popular drive-through (Chick-fil-a) gets backed up at meal times. The driveway in the picture above is the drive-through entrance. Now, once the driveway gets backed up to the road, new cars cannot enter until the line moves forward some. A car turning right into the entrance must wait if the line is backed up too far, but a car turning left across traffic must wait for both 1) no immediate oncoming traffic and 2) space in the line. Since the left turning car must yield to all right turns, you get an interesting starvation phenomenon: the line backs up so no car can enter and the left turning car waits. The line moves forward some so now there is room, but the traffic in the other lane continues to move and blocks the turn. Eventually a right turning car fills the space in the line, so when the next break in traffic occurs the left turning car still cannot complete the turn. All of the right turning cars occupy any freed space in line and starve out the left turning ones.

This was a frustration I encountered first hand, and it reminded me of an article I read a few weeks ago (on Slashfood) about increasingly unreasonable fast food drive-through wait times and the traffic problems a poorly-placed drive-through can cause.

“In Peabody, Mass., the opening of the first New England Sonic in August drew excited customers from across the region anticipating their first extra-long chili-cheese Coney hot dog. In the first month, it wasn’t unusual for customers to wait in their cars for up to four hours.”

Not exactly “fast food,” is it?

I follow Ed Felten’s blog, Freedom To Tinker (which is actually now a blog for many people at Princeton’s Center for Information Technology Policy) — it has good coverage on issues like electronic voting and intellectual property. Dan Wallach, a well known security (among other things) researcher at Rice, published an interesting post titled “Acceptance rates at security conferences” assessing the state of academic CS conferences in the area of security. He points out that the conferences are getting increasingly competitive with an ever growing field of researchers and a relatively fixed number of conference venues; he notes that this will lead to certain “structural problems” in the research community and discusses potential options.

He also points to Matt Welsh’s thoughts on similar issues in the systems community:

• “Scaling up conferences”
• “Scaling up program committees”

This is of particular interest to me since, as a PhD student, I am an academic systems researcher. Dan Wallach summarizes Matt first post as follows:

He argues that there’s a real disparity between the top programs / labs and everybody else and that it’s worthwhile to take steps to fix this. (I’ll argue that security conferences don’t seem to have this particular problem.) He also points out what I think is the deeper problem, which is that hotshot grad students must get themselves a long list of publications to have a crack at a decent faculty job. This was emphatically not the case ten years ago.

I definitely see what Matt is talking about in the systems community. For example, for a large subset of lower-level systems work*, SOSP and OSDI are a sort of gold standard in publication venues. Each conference is held every two years (alternating years between the two venues), so each year 20-30 papers will be accepted total (for reference, OSDI ‘08 accepted 26/193 and SOSP ‘07 accepted 25/131). Given the size of the systems community, that doesn’t give much leeway for up-and-coming researchers, but a publication in such a venue is virtually required to be competitive academically — as Matt describes it, a publication in these venues is “a highly prized commodity, and one that is becoming increasingly valued over time.” Matt says:

Several of us on the hiring committee were amazed at how many freshly-minted Ph.D.s were coming out with multiple papers in places like SOSP, OSDI, and NSDI. Clearly there is a lot more weight placed on getting those papers accepted than there used to be. … Somewhere along the way the ante has been upped considerably.

I notice this too. For example, Georgia Tech’s College of Computing (where I am finishing my PhD) was ranked in the top 10 graduate programs in CS (#9) by US News and World Report in 2008. For systems research specifically, we were also ranked in US News and World Report’s top 10 (#10) in 2008. Now, of course US News and World Report’s rankings are contentious and reducing the work of a whole bunch of different researchers in CS to a single dimensional ordinal representing the whole program is very subjective, but the point is only to say that our program can be considered competitive in the universe of CS graduate programs.

But if you look at our publishing track record in these two prized venues, we’re virtually unrepresented. If you look at the OSDI proceedings, you will see that a paper from Georgia Tech has never been accepted there (my 2008 submission was rejected, although it did get decently positive reviews), and we have two SOSP papers — one in 97 which was collaborative with Microsoft Research and involved only students and no Georgia Tech faculty (which makes me wonder if it was related to an internship) and one in 2007 which was a collaboration between a student in the Electrical and Computer Engineering and a professor in the College of Computing. Compare this college-wide record with that of Haryadi Gunawi, an excellent faculty candidate interviewing at Georgia Tech this year. In his career as a PhD student, he had 2 OSDI and 3 SOSP publications (plus publications in top venues in other areas, like PLDI, ISCA and FAST). As a student, he has amassed significantly more publications in these prized venues than our whole College of Computing can claim**. And other students from his advisor(s) have similarly impressive CVs. Look at the students of many other “rockstar” systems researchers and you’ll see the same pattern; we had a parade of great faculty candidates with similarly strong records.

So what am I supposed to make of this? I get a deep sense of cynicism when I see trends like this over many years. Matt says, “I don’t have hard data to back this up, but it feels that it is increasingly rare to see papers from anything other than ‘top ten’ universities and labs in the top venues.” I would go a step further and say that there’s a certain “clique” (or “cabal” if you want something sinister) of key researchers who facilitate virtually all of the publications in these venues. If you are a student of one of these researchers, or a nth-generation student (e.g. a student of a faculty member who once was a student of…), you know how to do work that appeals to the program committee and present it in the proper way — if you don’t have the right perspective on these fine points of taste, your chances are grim.*** As a student, if your advisor is a big name, you can have a paper in these top venues every year. If you don’t, you have very bleak academic job prospects. Now I’m definitely not trying to diminish Haryadi’s impressive accomplishments, and his research is very exciting. But I get the sense that there’s a very strong dis-proportionality in academic publishing in systems that is a lot worse than most other areas in computer science.

A comment to Matt’s first post and the end of Dan’s post also pointed me to another relevant article. In May’s CACM Viewpoints, Ken Birman and Fred Schneider wrote an interesting critique of the state of systems conferences titled “Program Committee Overload in Systems” (here’s a free pdf from Fred Schneider — the same content but without the fancy formatting of the CACM hardcopy). This CACM article seems like a follow-up and expansion of an earlier work of Ken’s I’ve blogged about (titled “Overcoming Challenges of Maturity”).

Anyway, I’m glad that some well-respected systems researchers are being vocal about these issues. It’s definitely good to know I’m not the only one with gripes; I’ve been somewhat cynical about this for a while, but since I have very little clout it helps to find a few senior systems researchers with some common concerns.

* Yes, I understand that “lower-level” is a matter of perspective. To my electrical and computer engineering colleagues, things like hypervisors and operating systems count as “high-level” “end-user” programming.

** If you look at DBLP, you will find a good bit more from current College of Computing faculty, but I’m counting publications where the author is at Georgia Tech when the publication is made (i.e. the author’s affiliation at the time of the publication).

*** Even presented well, good work on certain kinds of systems topics just doesn’t seem to be interesting to the PCs of these top conferences (the Europeans have been irked by this for years — leading to the establishment of EuroSys).

Slashdot is on my RSS feed, but I try not to wade into the article comments (or trust the article summaries, for that matter). Once in a while, my curiosity gets the best of me and I start reading comments. The end result is usually an increase in my blood-pressure and a decrease in my faith in the future of humanity. Whenever a technical topic comes up, I cringe. It’s amazing how much incorrect and crazy information gets modded as “insightful” or “informative.” Someone once complained to me that Slashdot is full of computer nerds who have very little knowledge in other “hard” sciences, and they get that information wrong all the time. I replied saying that they get the computer stuff wrong all the time too, but the majority of the audience simply does not have enough grounding to be able to accurately assess their own level of knowledge.

It’s not quite the “blind leading the blind,” but pretty close, and that makes the moderation a bit impotent. Certainly some knowledeable people read and post there, but the quality of the average comment is quite low and the moderation turns into “mob rule.” That’s not to say that all Internet venues will end up this way: some less popular sites have much higher quality forums (e.g. Real World Technologies). I think Ed Felten said it well in a post several years old titled “The Slashdot Effect”. He notes, “sadly, the treasures of Slashdot are often buried in a vast wasteland of speculation, misinformation, and irrelevant blathering.”

A Slashdot quote I noticed today:

“And people who sit in glass houses shouldn’t throw stones. Looking through [Vaughan] Pratt’s publication list, the first two papers I came across on a topic that I know a lot about should never have passed peer review.” [0]

Yes, this random schmo on Slashdot is criticizing the quality of Vaughan Pratt’s publications. Vaughan Pratt, who proved PRIMES is in NP, of the Knuth-Morris-Pratt string matching algorithm, fellow of the ACM, PhD student of Donald Knuth, etc. I guess Knuth didn’t teach Pratt enough rigor to satisfy this random Slashdot poster. I can’t put into words how hard I’m rolling my eyes at this comment. Of course it was modded “4, Insightful” (4 out of 5). Now, I’m not saying Vaughan Pratt is infallible or that his reputation puts him above criticism, but he has infinitely more credibility than some Slashdot poster who criticizes two unnamed papers in an unnamed area of expertise. Referring to Pratt’s publications as a “glass house” with respect to his credibility in the area of CS theory is just the kind of arrogant nonsense that I unfortunately expect from Slashdot.

BTW, for people like me who have recently read or are reading Beautiful Code, note that Chapter 9 — Top Down Operator Precedence also involves Pratt. Although he didn’t write that chapter of Beautiful Code, he did create the top down operator precedence parsing technique it describes.

Traffic was extra terrible this weekend. I’m not going to claim that Atlanta has the worst drivers in the country (practically everyone claims their city of residence deserves that title), but Atlanta is often ranked among the worst traffic cities in the country.

However, the point of this post is not to complain about Atlanta traffic in general, because that would be unoriginal and not nearly nerdy enough. To me, it is always interesting to observe CS concepts at work in real life, like a pipelined drive-through with separate payment and food windows to provide better customer throughput (the Checkers around here even has a superscalar drive-through, with two independent paths on separate sides of the building). Anyway, in that vein and continuing on the theme of parallel programming, recently I observed classic example of deadlock in traffic. Atlanta drivers seem to block intersections as standard operating procedure, which resulted in the following deadlock:

Neither car is able to turn and make progress because the cars traveling in the opposite direction are blocking the intersection (which are themselves blocked behind the turning cars). This is a good reason why people should not block intersections (or driveways), because it’s not just a matter of courtesy. This deadlock was resolved by one of the cars – the one trying to turn into the driveway – giving up and turning around a bit further up the street (after being honked at by a line of cars sitting in a major intersection after the light changed). Anyway, I’m sure Atlantans will read my blog and adjust their behavior accordingly.

As an aside, I always liked Dijkstra’s colorful “deadly embrace” terminology for referring to a two-process deadlock.

Practically every technical talk I’ve seen over the past few years starts with the same exact 5-10 minute opening. And they all have that same exact graph of Moore’s law (or sequential execution speed over time), too. Frankly, I’m getting a bit sick of hearing this explained in detail over and over again. I get it. I haven’t been in a coma for the past 4 years. I think we all understand that the transistor density increases afforded to us by Moore’s law are no longer speeding up sequential execution speed as much as in the past. So chipmakers have moved to multiple cores, hardware threads, “synergistic processing units,” etc., thus making parallel computing research more mainstream again.

Could we please dispense with the unnecessary retelling of this story already? I think, by now, a technical audience will understand and accept the premise without that graph of Moore’s law.

Note: My intent is not to offend the numerous talented researchers spending their time on these important related problems; I’d just like to see less time spent rehashing why everyone is working on parallel computing research.