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.
Filed under: Uncategorized | Tags: algorithms, cryptography, game theory, PODC, security, theory
Decisions for PODC 2011 (in San Jose) have just been mailed out this morning. In a later post, I’ll talk about some of the interesting accepted papers this year – there are many. For now I wanted to mention two of my own papers that were accepted and are now up on my web page.
Conflict on a Communication Channel. This is a paper that I had previously blogged about here. I’m still very excited about the idea of maintaining security invariants while spending asymptotically less than an adversary that is trying to break them. In this paper, we were able to do this for a few problems related to jamming in sensor networks and denial of service attacks. However, the application of this kind of game theoretic analysis to security problems is still wide open. Many interesting problems remain.
Scalable Mechanisms for Rational Secret Sharing. This is a paper that I had not previously talked about in this blog. The paper considers the problem of secret sharing when each player is rational. In particular, we assume that each player prefers to learn the secret over not learning it, but prefers to be the only player learning the secret over being one of many players learning it. Much interesting work has been done on this problem in the last few years, with the main goal being to design a mechanism that ensures that ensures that all players learn the secret (thereby maximizing social welfare). The new problem we focus on in this paper is designing mechanisms that both reveal the secret to all players and are scalable in the sense that they require each player to send just a constant number of messages in expectation. Secret sharing is a subroutine for many cryptographic protocols, so one motivation is to develop a scalable tool for problems like rational multiparty computation and implementation of a mediator.
Filed under: Uncategorized | Tags: funding, game theory, grants, security, theory
Dear blog, please forgive me for my neglect these many, long weeks!
About this time last year, I blogged about some tips that I found useful for writing NSF proposals. It turns out that the NSF proposal I submitted last year was funded! Let’s hope that things go as well again this year. I sometimes get requests for full proposals I’ve submitted that have been funded, and like many researchers, I’m a bit uncomfortable posting an entire proposal. However, this time, in the spirit of recommitting myself to interesting and reasonably frequent blogging, I’m going to post the one page project summary for my funded proposal, and I will post it right here. I hope that some readers will find it useful.
attacker-defender-games-summary
Filed under: Uncategorized | Tags: algorithms, game theory, security, theory
Imagine that Alice wants to send a message to Bob, and that Carol wants to prevent this. Assume there is a communication channel between Alice and Bob, but that Carol is periodically able to block this channel. Further, it costs Alice $a dollars each time she sends on the channel, Bob $b dollars each time he listens on the channel, and Carol $c dollars each time she blocks the channel. If Alice, Bob and Carol all play this game optimally, how much more will Carol need to spend than Alice and Bob in order to block the message?
This problem abstracts many types of conflict on information networks including: web censorship by nation-states, denial of service attacks on the Internet, and jamming attacks on wireless networks, where the costs to Alice, Bob and Carol can represent expenditure of both computational and human resources. The problem allows us to quantitatively ask: Does information really “want” to be free?
In a new result, Max Young, Valerie King and I answer this question in the affirmative by showing that under optimal play, it is significantly harder for Carol to block the message than for Alice to communicate it to Bob. Specifically, if a,b and c are fixed constants, and Carol spends $X dollars to try to block the message, then Alice and Bob need spend only proportional to $X^{phi – 1} or about $X^{.62} dollars to transmit the message, where phi = (1+ sqrt(5))/2 is the golden ratio. Surprisingly, this result holds even if Alice and Bob do not know the value X, and there are no cryptographic assumptions.
Filed under: Uncategorized | Tags: algorithms, game theory, networks, security, theory
This is the final post of a two part series. Guest post by Navin Rustagi.
If a faulty detector node misfires a false alert, it will end up propagating this false alert through the whole network, thus unnecessarily congesting the network. In our recent paper we address this issue to some extent. We do it by implementing a Time To Live(ttl) field in the alert messages and the nodes. We have a parameter for the system called τ, which is used to initialize the value of the ttl field of the detector nodes, when they get alerted for the first time. After that each node which gets alerted decrements its ttl field by one in each successive time step and sends out its alert messages with that value. New nodes which get alerted get initialized with the value of the ttl field in the alert message which alerts them. If they get an alert message with a higher ttl value than their existing one, they update their ttl value to reflect the new value. Once the ttl value goes to zero, the alerted nodes stop propagating but remain alerted throughout. Observe that this ttl mechanism ensures that if τ =O(loglogn), the influence of false alerts is limited to at most poly logarithmic number of nodes.
In the paper which we have submitted to SSS, we show that for worms which are designed to last for at most O(log n) time steps, there are certain conditions on the parameters which ensure that with the alert strategy adapted slightly from our paper in OPODIS, all but o(n) nodes in the network will be alerted w.h.p.
We call the lower bound on the expected rate of growth of alerts as p and the upper bound on the expected rate of growth of worms as q. We choose the values of α, β and γ s.t p ≥ 2q². For these values of the parameters, we show that w.h.p all but o(n) nodes would be alerted if the worms are constrained to spread in at most O(log n) time steps. In this paper, we assume that the overlay network has degree O(log n)(as opposed to a constant degree in the previous paper) so that we can make use of the resulting high vertex and edge expansion in our analysis. The rate of growth of alerts as characterized by p only provably holds true till O(n/log n) nodes are alerted. After that, the lower bound on the expected rate of growth of alerts till the number of alerted nodes exceed n/3, is called p1=(1+e-α /4).
In our paper in OPODIS, so far as p was greater than q we gained significant advantage over the worms in terms of the number of nodes alerted. Since once a node gets alerted, it continues to send alert messages throughout the game, the worm is not really successfully in gaining any ground by slowing down the infection process. But in this paper, due to the constraints imposed by the ttl mechanism, alerted nodes have to stop propagating once their ttl field expires. So the worms can wait for the ttl to expire before starting the infection again. We show in our analysis that we can avoid worrying about the number of nodes which stop propagating alerts by alerting enough number of detector nodes in one round which in τ more rounds would alert all but o(n) nodes in the network. To do that we define a small step round to be a round when the number of virgin(neither infected nor alerted) nodes that receive worm messages is no more than 1/(logp1n) times the number of infected nodes at the end of the previous round. A round
which is not a small step round is called a large step round.
We observe that for a worm to take over the network in O(log n) rounds, there has to be a large step round after n/(logp12r+1n) nodes have been infected and before κ0 n/(logp12r+1n) nodes have been infected, where κ0 is a fixed constant. We make use of the high edge and vertex expansion of the underlying network, coupled with the fact that p ≥ 2q² to show that the detector nodes alerted at the end of this large step round are good enough to alert all but o(n) nodes in τ more rounds.
A simulation implementing our algorithm on a network of 500 nodes with degree 10 and α=4, γ=0.15, β=1 and τ=3 is given here.
