Filed under: Uncategorized | Tags: distributed computing, game theory, teaching
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? 
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).
 Full disclosure: this problem is not completely hypothetical. I’m doing some lectures at the Santa Fe Institute summer school this summer.
1 Comment so far
Leave a comment