Computer Science – Distributed – Parallel – and Cluster Computing
Scientific paper
2012-02-09
Computer Science
Distributed, Parallel, and Cluster Computing
Scientific paper
We present new bounds on the locality of several classical symmetry breaking tasks in distributed networks. A sampling of the results include (1) A randomized algorithm for computing a maximal matching (MM) in O(log Delta + (loglog n)^4) rounds, where Delta is the maximum degree. This improves a 25-year old randomized algorithm of Israeli and Itai that takes O(log n) rounds and is provably optimal for all log Delta in the range [(loglog n)^4, sqrt{log n}]. (2) A randomized maximal independent set (MIS) algorithm requiring O(log Delta sqrt{log n}) rounds, for all Delta, and only exp(O(sqrt{loglog n})) rounds when Delta=poly(log n). These improve on the 25-year old O(log n)-round randomized MIS algorithms of Luby and Alon et al. when log Delta << sqrt{log n}. (3) A randomized (Delta+1)-coloring algorithm requiring O(log Delta + exp(O(sqrt{loglog n}))) rounds, improving on an algorithm of Schneider and Wattenhofer that takes O(log Delta + sqrt{log n}) rounds. This result implies that an O(Delta)-coloring can be computed in exp(O(sqrt{loglog n})) rounds for all Delta, improving on Kothapalli et al.'s O(sqrt{log n})-round algorithm. We also introduce a new technique for reducing symmetry breaking problems on low arboricity graphs to low degree graphs. Corollaries of this reduction include MM and MIS algorithms for low arboricity graphs (e.g., planar graphs and graphs that exclude any fixed minor) requiring O(sqrt{log n}) and O(log^{3/4} n) rounds w.h.p., respectively.
Barenboim Leonid
Elkin Michael
Pettie Seth
Schneider Johannes
No associations
LandOfFree
The Locality of Distributed Symmetry Breaking does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Locality of Distributed Symmetry Breaking, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Locality of Distributed Symmetry Breaking will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-157233