PODC (day 3)

Leave a comment

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!

Advertisements

**1 Comment so far**Leave a comment

Hi jared. My name is Sam Saia. I’m from Buffalo NY area. Just bored and googling my family name. I like your website. Good luck to you!

Comment by sam saiaJuly 31, 2010 @ 1:42 am