Roger Wattenhoffer shares with me slides from his talk on “local looking” distributed algorithms that I think will be interesting to the distributed computing community. This talk was given at another workshop at Bertinoro this summer – a workshop on sublinear algorithms (blogged by Piotr Indyk here). Roger’s talk particularly focuses on lowerbounds and upperbounds for many “local looking” distributed problems like Maximal Independent Set, Minimal Vertex Cover, Minimum Dominating Set and Maximal Matching. The talk discusses the known lowerbounds for these problems: they are all known to require a number of rounds that is Omega(sqrt(log n)) and Omega(log Delta).
The talk also discusses upperbounds – in particular it also discusses a beautiful randomized algorithm for Maximal Independent Set that takes O(log n) rounds in expectation (I’ve recently posted slides from one of my own recent talks on this nice randomized MIS algorithm here. )
Finally, the talk illuminates many interesting open problems in distributed algorithms for these types of problems:
- Is there a deterministic algorithm for Maximal Independent Set (MIS) that takes polylog n rounds?
- Can we close the gap for randomized algorithms for MIS between the best lowerbound O(sqrt(log n)), and the best upperbound, O(log n)?
- What are the problem boundaries between O(1), O(log*n), O(log n) and O(diameter)? A nice picture illustrating what is open on these boundaries is given in the last couple slides of the talk.
Leave a Comment so far
Leave a comment