Filed under: Uncategorized | Tags: biology, distributed computing, game theory, theory

The Game Theory of Life is a nice writeup of a recent PNAS paper Algorithms, Games and Evolution by Chastaina, Livnatb, Papadimitriou and Vazirani. As a CS researcher with an amateur’s interest in biology, I really enjoyed this paper.

The paper shows a certain equivalence between two algorithms. The first algorithm, I’ll call “evolution”. This is an approximation (using replicator dynamics) to what happens in real Evolution in nature. The second algorithm is the multiplicative weight update algorithm (MWUA) which we all know and love in CS. MWUA is also known as weighted majority or winnow to many people in CS theory.

The paper proves that the outputs of “evolution” are equivalent to MWUA. They then show this implies that “evolution” is equivalent to a process that tries to maximize utility *plus* entropy (equation 3 in the paper). The utility part is not surprising since we’d certainly expect Evolution to be concerned with it. The “plus entropy” part is surprising, and perhaps explains the surprising diversity of life. Essentially sexual replication in the “evolution” algorithm is what gives rise to this additional entropy part.

I think it’s a pretty interesting paper. Intuitively, it proves that a simple kind of genetic algorithm (i.e. “evolution”) will give equivalent results to the MWUA (i.e. see the equivalence of Figures 1 d) and 2 d) in the paper). A nice result from the CS perspective. However, there are a few “rah rah computer science” comments in the paper that may turn off some biologists.

I think the key thing that would really impress biologists would be making the “evolution” algorithm more realistic. To do this would require improving Nagylaki’s theorem which is used in the paper for analyzing the “evolution” algorithm. The authors claim Nagylaki’s theorem can already be used to handle diploidy and partial recombination. Mutation is an area mentioned for future work. Modeling the interaction of organisms seems much harder. It’ll be interesting to see the followup work on this paper.

A nice article on how colonies of cells make decisions. Insight into how to control these decisions might help prevent bacteria from deciding their number are large enough to start an infection or create a biofilm…

[HT to Peter Robinson and Amitabh Trehan]

Some work of a recently graduated PhD student of mine, Amitabh Trehan, was mentioned in Muthu’s blog yesterday. The work is mentioned in a bullet about problems discussed at a Google research meeting at FCRC and is quoted below (btw was this meeting broadly advertised? I would have gone if I’d known about it):

*Big problems, eg., can we provide guidance on how science budget should be allocated among various disciplines, or NSF CS budget among different areas? Given a subset of researchers, say we can estimate their impact on the society when funded. Given this oracle, can we allocate funds to people to maximize social welfare? Can we model people switching teams in second round or open bid systems for reallocating funds? Q: Why doesn’t NSF give $’s to 2 teams for the same project and get them to compete? For some recent work, see the work of Shay Kutten, Ron Lavi and Amitabh Trehan.*

It’s a proud and exciting moment to see a former student embark in a research area you know nothing about. But it’s also a bit disconcerting, like when my 3 year old son beats me at Concentration.

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? [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.

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).

A quick post from Gopal Pandurangan who has 2 postdoc positions at NTU in Singapore:

*I just recently got a grant from Singapore govt. for research in* *distributed algorithms. I am looking for postdocs (2 slots are there). May I please request you to publicize in your blog the contents of the following link: http://www.ntu.edu.sg/home/gopal/postdoc.html *[quoted below]

Multiple postdoctoral positions (official title: “Research Fellows”) are available, starting April 2011, in the Division of Mathematical Sciences, Nanyang Technological University, Singapore. All recent Ph.D.s (or those close to finishing) who work in theoretical computer science with a focus on one or more of the following areas are encouraged to apply: randomized/probabilistic algorithms, distributed algorithms/computing, approximation algorithms, network algorithms, communication complexity, and other related areas in algorithms. Experience in prior work in algorithms area as evidenced by publications in top algorithms and theory conferences is desired. All candidates with strong publication record in theory and algorithms (e.g., SODA, FOCS, STOC, PODC, SPAA, DISC) are encouraged to apply.

Initial appointment will be for one year with the possibility of renewal for an additional year based on performance and availability of funds. Salaries are competitive and are determined according to the successful applicants’ accomplishments, experience and qualifications. Travel funding is available.

The Mathematical Sciences Division at NTU has a vibrant research group in theoretical computer science, with several faculty, post-doctoral research fellows, and Ph.D. students from all over the world.

The candidates should send their CV, a brief research statement, and two letters of recommendation to Prof. Gopal Pandurangan (gopalpandurangan@gmail.com).

Singapore is a highly developed country and is well situated and connected. The quality of living is very high (with per capita income among the top 5 in the world), while the cost of living compared to developed countries is relatively low.

Filed under: Uncategorized | Tags: distributed computing, game theory, PODC, security

Accepted papers for PODC 2011 are now up on the web here. There are many interesting papers – here are a few that immediately catch my eye:

*“Error-Free Multi-Valued Consensus with Byzantine Failures“*by Guanfeng Liang and Nitin Vaidya. This paper gives a deterministic algorithm for solving multi-valued consensus with Byzantine faults that has asymptotically optimal bandwidth when the number of bits in the input values are large. The cool thing about the paper is that it uses network coding and an interesting amortized analysis. Essentially there are multiple runs of a single bit consensus algorithm. The single bit consensus algorithm has lightweight checks and is 1) very efficient when the checks detect no malicious behavior; and 2) able to “kick out” a Byzantine processor whenever the checks do detect malicious behavior.*“Xheal: Localized Self-Healing Using Expanders”*by Amitabh Trehan and Gopal Pandurangan. Amitabh, my former PhD student, and periodic guest blogger on this blog, is now a postdoc at Technion working with Shay Kutten and Ron Lavi. This paper is still very secret as Amitabh won’t even send**me**a copy of the submitted version. However, we can guess that the paper describes an algorithm that ensures an overlay network 1) keeps paths between nodes short; and 2) keeps degrees of nodes small. That word “localized” is very tantalizing as it suggests that, unlike previous work, this new self-healing algorithm requires only local communication.*“Adaptively Secure Broadcast, Revisted”*by Juan Garay, Jonathan Katz, Ranjit Kumaresan and Hong-Sheng Zhou. Again this paper doesn’t seem to be up on the web and I didn’t get to read it as a member of the PC. However, the problem itself, described in the paper Adaptively Secure Broadcast by Martin Hirt and Vassilis Zikas, looks interesting: basically the goal is secure broadcast in a scenario where an adaptive adversary can corrupt up to a 1/3 fraction of the players,*including the sender*. The original paper by Hirt and Zikas shows that past results on the secure broadcast problem are not secure under composition, and they then present a new protocol that is secure under composition, along with a new simulation-basted security notion for the problem.*“Fault-Tolerant Spanners: Better and Simpler”*by Michael Dinitz and Robert Krauthgamer. This paper shows how to create spanners of general graphs that are tolerant to vertex failures. They give a transformation for k >= 3 that converts every k-spanner construction with at most f(n) edges into a k-spanner construction that can tolerate r faults and uses O(r^3 log n)*f(2n/r) edges. For the case k=2, they improve the approximation ratio from O(r log n) to O(log n). Bonus: This last result uses an LP relaxation and the Lovasz Local Lemma.- There are several papers that did not make it as regular papers that I hope to see as brief announcements. Privacy concerns keep me from mentioning anything in particular here, but there were some nice lower bound results that were invited to be resubmitted as brief announcements. I hope the authors will accept.

Question: Are there no game theory papers this year except the two that we submitted? This seems surprising.