# Machinations

Day 2 PODC’09

New Animals at the Zoo!

More from Amitabh – Ed

Day 2 began for me early at 8:20 when I presented our paper ‘The Forgiving Graph: A distributed data structure for low stretch under adversarial attack ‘. The early morning start gave me an opportunity to wish good evening to my European friends who were still suffering from jet-lag! Our paper gives provably good bounds on degree increase and stretch for a network under attack by an omniscient adversary which adds or removes nodes from the system, and the algorithm repairs only by adding edges. We also introduce a new data structure which we call the half-full tree (haft). The talk was well received and I was actually asked some questions after the talk which is usually a good sign! The slides from the talk are here .

Another talk in the same session I found particularly engaging was Andrew Handley’s presentation of his paper The Flip Markov Chain and a Randomizing P2P Protocol’ (work with Colin Cooper and Martin Dyer). The general problem is of obtaining random graphs from regular graphs using the simple operations switch’ (take two independent edges and swap their endpoints) and ‘flip'(take a 3-path, break and reconnect the side edges). Cooper, Dyer and Greenhill (CDG)( (journal version , SODA) have shown that random switches make a random graph quickly via a complicated analysis of a markov chain that applies the switch to random edges. However, flips are a better operation for P2P networks since they are local, preserve connectivity and allow simple protocols. In this paper, the authors improve the bounds on making random graphs by flips by constructing a new markov chain using the markov chain of CDG, but replacing a switch by a series of flips, and analysing this new chain.

The last session had another set of elegant talks. One would think that the area of random walks has been studied to death but here was another paper on it. Atish Das Sarma presented his paper with Danupon Nanonkai and Gopal Pandurangan Fast Distributed Random walks. Their results include showing a random walk of length \ell can be done in Õ(l^2/3D^1/3) rounds on an undirected unweighted network where D is the diameter of the network, and k random walks can be done in Õ((kl)^2/3D^1/3) if k <= l^2 and Õ((kl)^1/2)  otherwise . They do this by the simple idea of nodes starting to random walk in anticipation of future use, thus, a few short walks are done in the beginning and stitched’ together as required, if more short walks are required they are done on the fly. They show how to do many short walks in parallel without causing too much congestion.

The second talk was Distributed and Parallel Algorithms for Weighted Vertex Cover and other Covering Problems by Christos Koufogiannakis and Neal Young. They have developed algorithms for covering problems including a parallel 2-approximation algorithm for Weighted Vertex Cover in polylog rounds. The idea is to use edge-discount operations where a node with higher weight discounts an node with a lower weight node taking the connecting edge weight to zero. In the distributed version, over a few rounds, a bipartite version of the network is formed in each round. Independent rooted stars are taken from this graph and a coordinated probabilistic discount operation is done within the stars, till the covering is obtained. Christos explained the algorithm by using the classic model of the nodes of the bipartite graph being boys and girls, and as in the real world, the girls jilting a number of boys!

The third and final talk Return of the Primal-Dual: Distributed Metric Facility Location by Saurav Pandit and Sriram Pemmaraju , was introduced by Sriram as one in the Star Wars’ series following on from Greedy strikes back.: Improved facility location algorithms . Informally, the facility location problem is that given a set of facilities and clients, how to assign clients to open facilities such as to minimize overall costs which include costs of opening the facility and connection costs. In this paper, they obtain a 7-approximation in O(log(number of facilities) + log(number of clients)) round distributed algorithms for the metric facility location problem in the CONGEST model (message sizes bound by O(log network size)). For this, they have used the elegant primal-dual method method (based on Jain and Vazirani’s   A primal-dual schema based approximation algorithm for the element connectivity problem) and a quick randomized sparsification of graphs due to Gfeller and Vicari (A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs ). A question posed at the end is that can the technique of primal-dual plus rapid sparsification be applied to other settings, where generally the technique of LP relaxation is used (e.g. What cannot be computer locally!, Kuhn et al )).

Note: Calgary zoo is very nice especially when there is a conference banquet there 🙂 – Banff forests are supposed to be even nicer, and there I head tomorrow, hopefully I can get the last installment of the reports out on time.