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.
3 Comments so far
Leave a comment