Too many good talks on this last day of PODC to do them all justice. Just a smattering of what I found interesting:

*“Deterministic Distributed Vertex Coloring in Polylogarithmic Time”*by Barenboim and Elkin. This is the other vertex coloring paper at PODC (with which we shared the best paper award). The main result is a deterministic algorithm that runs in polylog time and uses only O(Delta^(1+epsilon)) colors. In face, in polylog time, O(alpha^(1+epsilon)) colors are possible where alpha is the arboricity of the graph. I won’t go into technical details of the talk here, but I do want to point to a nice primer on distributed vertex coloring with applications. It’s neat that after the question of improving the number of colors needed for polylog vertex coloring had been open for a quarter of a century, two papers at this PODC, gave significant improvement over the old O(Delta^2) result.*“Optimal Gradient Clock Synchronization in Dynamic Networks”*by Kuhn, Lenzen, Locher and Oshman studies clock synchronization in networks where communication links can appear and disappear at any time, rate of hardware clocks can vary arbitrarily, and estimates a node can get of the clock time of another node are inherently inaccurate. They are able to output a logical clock for each node such that the logical clocks of any two nodes are not too far apart, and nodes that remain close to each other in the network for a long time are better synchronized than other nodes. I know very little about this area, but I definitely enjoyed the talk and am particularly intrigued by this follow-up paper to appear in FOCS ’10. It shows how to use the PODC result to perform arbitrary computation over dynamic networks in which the network topology changes from round to round, provided that the network is T-interval connected. “A network is T-interval connected if for every T consecutive rounds, there exists a stable connected spanning subgraph. For T=1, the graph is connected in every round, but can change arbitrarily between rounds.”*“How to Meet when you Forget: Log-Space Rendezvous in Arbitrary Graphs”*by Czyzowicz, Kosowski and Pelc. This paper shows how deterministic agents with only log space can either 1) rendezvous in a graph or 2) determine that the graph is constructed in such a way that rendezvous is not possible. The assumption is that the nodes of the graph are indistinguishable and the agents, on visiting a node only become aware of the immediate neighbors of that node. It took me a while to realize that rendezvous may be impossible, this occurs when the graph is symmetric to the degree that any two deterministic agents will chase each other around indefinitely (for example, I think a cycle will cause this), and is an artifact of the lack of randomness for symmetry breaking. The paper makes use of results from the famous paper by Reingold on “Undirected Connectivity in Log-space”*“Breaking the O(n^2) Bit Barrier: Scalable Byzantine agreement with an Adaptive Adversary”*by King and Saia. I’m biased of course but I think Valerie gave a great talk on our paper! Slides are here.

Thanks to everyone for a great PODC. See you next year in San Jose!

Filed under: Uncategorized | Tags: algorithms, distributed computing, PODC, theory

In the invited talk, Pierre Fraigniaud pointed out a dichotomy in the PODC community: one community (the reds) is mostly interested in timing issues: asynchrony, link delays, crashes, etc.; the other community (the blues) is mostly interested in spatial issues: network structure, memory requirements, local computation, etc. His analogy was with the political divisions in the U.S. – Can’t we all just get along? In my own research, I think the problems are from the red community (Byzantine agreement, consensus) but the techniques used are from the blue (expanders, samplers). It’d be nice to have more mathematical techniques in our community that are of use to both the reds and the blues.

Talks I found particularly interesting follow:

- Great talk by Gopal Pandurangan on “Efficient Distributed Random Walks with Applications”. Their work returns a random walk of k steps in much less than k time. Essentially they can get down to about square root of kD time in a distributed setting, where D is the diameter of the network. The do this by pasting together short walks that are run in parallel at each node – however the “pasting together” and generation of the walks has to be done in a smart way to avoid congestion. It does not work to have the length of each short walk be deterministic.
*Attention Students: Gopal has a post doc position available. How a post doc position with a great researcher can still be open in this economic climate is mind boggling to me.* - Nice brief announcement by Lasse Kliemann on distributed network formation in an adversary model – basically an adversary removes one edge from the network after it is formed by selfish agents. Surprisingly, this game seems to have a small price of anarchy.
- Nice talk on distributed vertex coloring by Johannes Schneider: “A New Technique for Distributed Symmetry Breaking”. There are two papers at this PODC that have solved a very old problem (> 10 years old?): Can we color a graph with O(Delta) colors in polylog parallel time? This is the paper that solves the problem with a randomized algorithm. The other paper solves it deterministically (and won the best paper award – see below).
- Great talk by Sriram Pemmaraju on “Rapid Randomized Pruning for Fast Greedy Distributed Algorithms”. He presented a general “market based” technique for pruning in greedy algorithms. The technique is powerful enough to provide good greedy algorithms for many types of problems. I asked Sriram after the talk if he had a characterization of the types of problems for which his technique applied. Nothing formal, but he suggested that problems that have a kind of “local” flavor to them (can be solved or approximated locally) may be amenable to his approach.

The conference banquet was at a restaurant on the top of Zurich’s backyard mountain. Valerie and I were thrilled there to receive the best paper award, for our paper on “Breaking the O(n^2) bit barrier: Scalable Byzantine agreement with an Adaptive Adversary”. We shared the award with Barenboim and Elkin and their paper “Deterministic Vertex Coloring in Polylogarithmic Time”. Many people afterward asked me if our paper was a red one or a blue one. I decided that I like to think of it as purple. This was really a great night! It’s so nice to get this recognition after years of hard work on this problem.

Greetings from Zurich and the morning of the second day of PODC! Went for a short hike when I arrived on Sunday in the mountains above the city: meadows, mountain views, cowbells, great chocolate for a snack, lots and lots of very healthy looking blond people – a complete Swiss experience! Pictured on the right is the Swiss National museum next to lake Zurich which abuts the city.

Yesterday Hagit Attiya gave an invited talk on Transactional Memory. The tone of the talk was pessimistic about the benefits of transactional memory, arguing that it has significant theoretical and practical limitations, and that it weakens either consistency or progress guarantees (or simplicity). The talk called for a post-Transaction memory era where we should use techniques like “mini-transactions” that don’t over-promise to the programmers who are facing the difficult challenge of programming in a parallel environment.

Two other talks I enjoyed:

*“Partial Information Spreading with Application to Distributed Maximum Coverage”*by Keren Hillel and Haden Shachnai. This talk introduced a nice generalization of the property of graph conductance and then showed how this generalization could be useful for approximating the maximum coverage problem in a distributed setting. I like the generalization of conductance,*weak conductance,*that was presented since I think many real-world networks may tend to have high weak conductance even though they have low conductance*“Adaptive Randomized Mutual Exclusion in Sub-Logarithmic Time”*by Danny Hendler and Phillip Woelfel. A very nice talk covering many mathematical details of what seems like a subtle proof of correctness for a randomized mutual exclusion algorithm. I know very little about mutual exclusion but felt the talk gave me a good flavor of the mathematical techniques used in the area.

Quick business meeting summary: brief announcements are good, they boost attendance; attendance is up at the least couple of PODCs; to rebuttal or not to rebuttal?; PODC 2011 will be in San Jose, CA; PODC 2012 will be in Madeira, Portugal, known for its bananas, sweet wine and warm waters.

This is probably not surprising if you’ve been reading the last several posts on this blog, but I have an opening for a PhD student that I would like to fill soon. I’m circulating the following announcement about it.

*I have one opening for a PhD student with a keen interest in CS theory research and a strong mathematical background to work on a game theoretic project in network security. The project entitled “Beyond Tit-for-Tat: New Techniques for Collaboration in Network Security Games” will focus on how to enable collaboration on the Internet, where populations are highly fluctuating, selfish, and unpredictable. This project will explore a new algorithmic technique for enabling collaboration in network security games which will improve on past approaches such as tit-for-tat in the following ways: (1) it works even in single round games; (2) it works even when the actions of the players of the game are never revealed; (3) it works even in the presence of churn, i.e. players joining and leaving the game. *

*The position will cover tuition and also pay a stipend of $1,780/month. The position can start in either spring or fall semester of 2011*

*New Mexico is a hot spot for research in complex systems and interdisciplinary research. The Computer Science department at the University of New Mexico benefits from strong ties with the Santa Fe Institute, and Sandia Labs and Los Alamos Labs. The theory group in our department is particularly strong, having graduated students in the past several years who have performed very well in a challenging job market. Permanent Positions secured by these students include: Asst. Prof. at University of Colorado, Boulder; researcher Sandia Labs; engineer at Microsoft. Post doc positions secured include: University of Waterloo, Technion and University of Victoria.*

*Interested? Please contact me about the position at: <my last name>@cs.unm.edu
*

Navin successfully defended his dissertation on July 8th and has recently had his final manuscript accepted. Below is the announcement for his defense, preserved for posterity 🙂 Some of his research results have already been discussed in his previous guest blog posts.

Congratulations Navin!

**PhD Dissertation Defense Presented by: **Navin Rustagi

**Title: **Security in Network Games

**Committee Chair: **

Jared Saia, Associate Professor of Computer Science at UNM

**Committee Members:**

James Aspnes, Professor of Computer Science at Yale University

Josep Diaz, Universitat Politecnica de Catalunya

Tom Hayes, Assistant Professor of Computer Science at UNM

**Abstract:
**

Attacks on the Internet are characterized by several alarming trends:

1) increases in frequency; 2) increases in speed; and 3) increases in

severity. Modern computer worms simply propagate too quickly for human

detection. Since attacks are now occurring at a speed which prevents

direct human intervention, there is a need to develop automated

defenses. Since the financial, social and political stakes are so

high, we need defenses which are provably good against a worst

case attacks and are not too costly to deploy. In this talk we

present two approaches to tackle these problems.

For the first part of the talk we consider a game between an alert and

a worm over a large network. We show, for this game,

that it is possible to design an algorithm for the alerts that can

prevent any worm from infecting more than a vanishingly small fraction of the

nodes with high probability. Critical to our result is designing

a communication network for spreading the alerts that has high

expansion. The expansion of the network is related to the gap between

the $1^{st}$ and $2^{nd}$ eigenvalues of the adjacency

matrix. Intuitively high expansion ensures redundant connectivity. We

also present results simulating our algorithm on networks of size up to

$2^{25}$.

In the second part of the talk we consider the virus inoculation game

which models the selfish behavior of the nodes involved. We present a technique for this game which makes it possible to achieve the “windfall of malice” even without

the actual presence of malicious players. We also show the limitations

of this technique for congestion games that are known to have a windfall of malice.

This dissertation includes research previously published in WINE and OPODIS.