Distributed Symmetry-Breaking Algorithms for Congested Cliques
This study delves into distributed algorithms for congested cliques, exploring concepts like the local model, congested clique model, routing schemes, and Main idea of Arboricity in graphs. It presents previous results and our findings, emphasizing the efficient handling of communication networks represented by graphs.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Distributed Symmetry-Breaking Algorithms for Congested Cliques Leonid Barenboim and Victor Khazanov
Distributed LOCAL model The communication network is represented by an n-vertex graph Vertices have unique ID s of size O(log n) each A message passes over an edge with one round Running time is the number of rounds of distributed communication Local computation comes for free
Congested Clique Model Set of n machines communicating over complete graph In every round, send to each vertex only O(log n) bits In every round, every pair of vertices can exchange O(log n) bits.
Previous results Routing scheme: each node needs to send at most O(n log n) bits and receive at most O(n log n) bit. Then O(1) rounds are sufficient. C.Lenzen MST in O(log log n) rounds Z. Lotker, E. Pavlov, B. Patt-Shamir, D. Peleg. (deterministic algorithm) MST(Minimum Spanning Tree) in O(log* n) rounds M. Ghaffari and M. Parter (Randomized algorithm) MIS(Maximal Independent Set) in O(log log n) K. Censor-Hillel, M. Parter, G. Schwartzman. (deterministic algorithm) O( ) Coloring in O(log log n) rounds J. Hegeman, and S. Pemmaraju. (Randomized algorithm)
Main idea Lenzen s Routing Problem in Congested Clique constant number of rounds
Main idea Lenzen s Routing Problem in Congested Clique constant number of rounds
Main idea Lenzen s Routing Problem in Congested Clique constant number of rounds
Main idea Arboricity - a(G) Any graph G can be expressed as a sum of forests Determine the minimum number of edge-disjoint forests into which G can be decomposed. This number is arboricity of G: a(G)
Main idea Arboricity - a(G) Any graph G can be expressed as a sum of forests Determine the minimum number of edge-disjoint forests into which G can be decomposed. This number is arboricity of G: a(G)
Main idea H-partition computes an H-partition with degree at most O(a) and size k = O(log n) within O(log a) rounds O(log a) rounds O(1) rounds
Main idea Forest decomposition
Main idea Forest decomposition H-Partition
Main idea Forest decomposition H-Partition
Main idea Forest decomposition Orientation
Main idea Forest decomposition Partitioning the edge set into forests by assigning a distinct label to each outgoing edge of vertex
Better than O(a)-time algorithms O(?2) coloring in O(log a + log* n) rounds Our Procedure Forest-Decomposition-CC runs in O(log a) rounds Procedure Arb-Linial O(?2)-coloring in O(log* n) rounds (L. Barenboim and M.Elkin 2008)
Main idea Defective-coloring In defective coloring, on the other hand, vertices are allowed to have neighbors of the same color to a certain extent (in example d=0, 1, 2)
Main idea Arbdefective-coloring An r-arbdefective k-coloring is a coloring with k colors, such that all the vertices colored by the same color i, 1 i k, induce a subgraph of arboricity at most r. (Barenboim and Elkin 2011)
Main idea Arbdefective-coloring Compute a forests-decomposition
Main idea Arbdefective-coloring Compute a forests-decomposition A vertex selects a new color, once all its parents have selected their colors.
Main idea Arbdefective-coloring Compute a forests-decomposition A vertex selects a new color, once all its parents have selected their colors. Vertex selects the color used by minimal number of parents
Main idea Arbdefective-coloring A partition of k subgraphs with arboricity O(a/k) each
Better than O(a)-time algorithms Defective-coloring Procedure Arbdefective-Coloring-CC in O(?2log?) rounds O(?2????) rounds O(1) rounds
Better than O(a)-time algorithms Proper-Coloring-CC(G,a,p) Arbdefective-Coloring-CC with arboricity a
Better than O(a)-time algorithms Proper-Coloring-CC (G,a,p) Arbdefective-Coloring-CC with arboricity a=a/p
Better than O(a)-time algorithms Proper-Coloring-CC(G,a,p) O(????) O(????)
Better than O(a)-time algorithms Proper-Coloring-CC in O(?????) rounds O(????) O(????)
Better than O(a)-time algorithms O(a) coloring in O(? ) rounds Execute Proper-Coloring-CC(G,a,p) , where p= ? Invoking Procedure Proper-Coloring-CC on a graph G with arboricity a with the parameter p= ? , produces a proper O(a)- coloring of G within time O(? )
Conclusion Deterministic O(?2+ )-coloring in O(log * n) rounds Deterministic O(?2)-coloring in O(log a + log * n) rounds Deterministic O(?1+ )-coloring in O(???2?) rounds MIS in O( a) rounds
Open questions Open questions MM (maximal matching ) in Congested Clique Deterministic algorithm for MST better than in O(log log n) rounds Edge-coloring algorithms
