Machinations


Great Ideas in Distributed Computing
April 29, 2011, 10:46 pm
Filed under: Uncategorized | Tags: , ,

You’ve got 3 hours to cover the most interesting and important results in distributed computing.  Your audience is eager, young scientists in diverse disciplines: biology, economics, physics, sociology, chemistry, math, computer science.  What do you cover? [1]

Below is my list.  It’s definitely biased to theory.  I hope I’m not making anyone mad by excluding something important.  Well actually, I hope I am making you mad enough to leave a comment below 🙂

  • Form impacts Function.  Network structure can have significant effect on algorithms running over the network.  There are two problems I’m thinking of covering here: 1) routing (i.e. Kleinberg’s small world paper); and 2) graph coloring.  I like both of these problems because they are easily motivated and have ties to human experiments (Milgram’s experiment for routing, and this experimental paper in Science for graph coloring).  Kleinberg’s result is easy and fun to teach.  I need to do more research on distributed graph coloring to determine which results are most elegant and easiest to present.
  • Anarchy is Inefficient.  This segment will cover algorithmic game theory.  “Inefficient” has two meanings: 1) computational inefficiency of computing a Nash equilbrium, and 2) social welfare inefficiency in terms of price of anarchy.  I’ll also take about ways to get around this inefficiency: cheap talk, the billboard model, mediators and general mechanism design.
  • Solidarity enables Resilience.  Distributed systems can be robust to both internal and external perturbations.  I plan to start with Von Neumann’s seminal paper and follow up work (by Nick Pippenger, among others), and follow with work on consensus and secure multiparty computation.  Finally, I’ll tie back to game theory by discussing connections between game theory and secure multiparty computation (of course I’ll mention the Beet Farmers).

[1] Full disclosure: this problem is not completely hypothetical.  I’m doing some lectures at the Santa Fe Institute summer school this summer.



A Trip to Iowa
April 18, 2011, 9:56 pm
Filed under: Uncategorized | Tags: , ,

Last week, I visited Iowa City to give an invited talk at U. of Iowa. Iowa City is a surprisingly hip place with amazing food (after all they’re close to lots of farmland). It’s a town where you can get a matcha&blueberry waffle, a pretty decent machiatto and a t-shirt reading “I was into Iowa before Iowa was cool”.

Sriram Pemmaraju was my host there. We talked a bit about his PODC  ’11 paper “Distributed Coloring in Few Rounds”, which describes a distributed algorithm that quickly colors graphs with small arboricity, and some of his recent work on epidemiology. The other theoretician I talked to in the department is Kasturi Varadarajan who told me a bit about his work on planar sensor cover – a STOC ’09 paper describes some of his older results on this problem.

My talk (new slides at this link) surveyed recent work on scalable Byzantine agreement, along with some new work on a game theoretic analysis of  conflict on a communication channel.  The questions from the audience were interesting and seemed to divide equally between making the work more practical (reducing constants, relaxing assumptions about the adversary), and making the work more theoretical (finding matching lower bounds).