C1: Distributed Algorithms on Ruling Sets

June 28, 2024

• The Algorithm [CKPU]
• Reference

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.

---

1. Each node $v$ is independently sampled with prob. $1/\sqrt{d(v)}$ and we use $V_{samp}$ to denote the set of sampled nodes;

2. Put good nodes that do not have neighbors in $V_{samp}$ in $V_1$;

3. Compute an MIS on $G[V_{samp}]$ using Luby’s algorithm (bad nodes first)

4. 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$.

5. Compute an MIS on $G[V_1]$.

6. Run Lines 1 to 5 on $G'$ that is the induced subgraph of $V$ removing 2-hop nodes from nodes in $I$.

7. 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.