Theory of Networked Computation

I spent two days at the workshop organized by Joan Feigenbaum and Jennifer Rexford on the Theory of Networked Computation. The total intellect they had amassed in the workshop was awesome, and the meeting was purposeful. The purpose was discussing what are suitable research directions for theoretical computer scientists in the context of the effort within NSF to in my words, do the internet over from the scratch. Some of the topics that dominated were: how to embrace economic theories in the design of networks, how to embed security and privacy within network design, the role of massive data set computing within networks, how to address nodes in the new network and is there a nice problem of combined compact routing and addressing, is there a theory of networking akin to theory of computing with impossibility or hardness framework, and how to make networks auto-administer themselves. There were some heated networking-specific discussions: should one expose network state to endhosts, should there be autonomous systems, are ISPs making money. Of course, there was some lamenting about how networking community did not seem to know the best theory results, some chest-thumping that theory results (Ashish Goel and Bruce Maggs converged to: "all three p2p protocols were directly derived from algorithmicists' work") were being useful, some soulful calls for more attempt at making theory useful by interfacing with networking in practice. A factoid: Andrei Broder has the patent on CAPTCHAs!. Cool! Another factoid: How real world breaks CAPTCHAs.

On theory vs applications, I tend to think there is a lot of good theory but there is less of good theory inspired by (or applicable to) real problems than theorists would like to believe. Most theoretical papers do not drill down deep (beyond the intro?) while making a case that their work/problem is crucial in an application. Personally, I like solving puzzles, so my heart is in theory, and at least in published work, I seem to think more theory than applications. Still, I got a referee report sometime ago for one of my papers that when paraphrased, said, "From Muthu, we expect more about applications for this result." Sigh.