Reminder: This post contains 1374 words
· 4 min read
· by Xianbin
In this post, I will introduce some distributed algorithms on Ruling Set.
An \(t\)-ruling set is a set \(S\) of nodes such that nodes in \(S\) are within distance \(2\), and nodes in \(V\setminus S\) has a node in \(S\) within distance \(t\).
\(\textbf{Theorem}\) There eixts a randomized algorithm that can find a 2-ruling set in \(O(1)\) rounds in the Congested Clique model.
The Algorithm [CKPU]
We say that a node \(u\) is good if \(\sum_{v\in N(u)}\frac{1}{\sqrt{d(v)} }\geq \alpha \log d(u)\). Otherwise, it is bad.
The intuition of defining good nodes and bad nodes are very clear. Good neighbors have at least \(poly \log n\) sampled. Then, these nodes have high chance to be covered.
we use \(B_d\) to denote the set of bad nodes in \(G\) with degree in the range \([d,2d)\).
The process of the algorithm is as follows.
-
Each node \(v\) is independently sampled with prob. \(1/\sqrt{d(v)}\) and we use \(V_{samp}\) to denote the set of sampled nodes;
-
Put good nodes that do not have neighbors in \(V_{samp}\) in \(V_1\);
-
Compute an MIS on \(G[V_{samp}]\) using Luby’s algorithm (bad nodes first)
-
If any uncovered node \(u\in B_d\) has a neighbor \(v\) that has at least \(c\sqrt{d}\log^5(d)\) neighbors in \(B_d\), we put \(u\) into \(V_1\).
-
Compute an MIS on \(G[V_1]\).
-
Run Lines 1 to 5 on \(G'\) that is the induced subgraph of \(V\) removing 2-hop nodes from nodes in \(I\).
-
Compute an MIS on the induced subgraph of the remaining uncovered nodes.
Reference
[1]. Cambus, Mélanie, et al. “Time and Space Optimal Massively Parallel Algorithm for the 2-Ruling Set Problem.” 37th International Symposium on Distributed Computing. 2023.