Backgrounds

Degree of the graph:

• the “degree” of a vertex (or node) is the number of edges that are incident to it.
• Degree (Graph) = highest degree of any vertex in the graph.

Maximal Independent Set:

• In graph theory, an Independent Set (IS) of a graph is a set of vertices where no two vertices are adjacent (they don’t share a common edge). The Maximum Independent Set (MIS) problem is about finding the largest IS in a graph

Some concepts

• Local Complexity: Focuses on the time it takes for a single node to make its decision or terminate its part of the algorithm.
• Global Complexity: Focuses on the total time it takes for all nodes in the entire system to terminate or complete the algorithm.
• Termination for a node might mean it has decided whether it is part of the Maximum Independent Set or not.
• Complete: means that the entire Maximum Independent Set has been identified throughout the distributed system.

Introduction

This paper presents a very simple randomized alg for this problem,

• Providing a near-optimal local complexity
• near-optimal global complexity when combined with some known techniques.

Specifically, This paper proposes a very simple and clean algorithm that guarantees for each node v that after O(log ∆+log 1/ε) rounds, with probability at least 1 − ε, node v has terminated and it knows whether it is in the (eventual) MIS or it has a neighbor in the (eventual) MIS.

Work Model: standard distributed computation model: LOCAL

• Network: G = (V, E), V =

  n

• Each node only knows its neighbors and can only communicate with its graph neighbor in sync rounds.
• O(log n)-hop Neighborhood: In certain scenarios, a node doesn’t need to be aware of the entire network to make its decision. Instead, it only needs to look at a neighborhood that’s proportional to the logarithm of the total number of nodes n. This is interesting because, in large networks, log(n) is much smaller than n, so this implies a more efficient process.

Question - local compleixty

How long does it take till each particular node v terminates, and knows whether it is in the (eventual) MIS or not, with probability at least 1 − ε?

Theorem 1.1: P(v have not make decision after first O(log(dev(v) + log1/ε) <= ε

Question - global complexity

In the global complexity, how to determine the best possible upper limit (upper bound) for a MIS problem in graph theory, given known lower limits? The best know bound prior is O(log2∆)+2O(√loglogn)

General Strategy: There’s a common method used in these problems:

• Run a randomized algorithm. Over time, nodes in the graph get probabilistically removed.
• After a while, the graph breaks into smaller components. This is called the “shattering” phenomenon.
• Once shattered, a deterministic algorithm (a set, predictable method) is used to solve the problem for these small pieces.

Current SOTA work takes O(log2∆) rounds to reach the threshold of shattering and then takes log ∆ · 2O(√log log n) rounds of determinations to solve this.

This paper improves this and can reach a shattering threshold after O(log ∆) rounds. Also, it reduces the deterministic alg complexity from log ∆ · 2O(√log log n) to 2O(√log log n).

Theorem1.2: Randomized distributed MIS algs which can terminates after O(log∆)+2O(√loglogn) rounds with probability at least 1 - 1/n

Luby’s Algorithm

Progress

• In each round, every node chooses a random number between 0 and 1.
• Nodes that have the smallest number among their neighbors are added to the MIS and then removed from the graph along with their neighbors.
• Implementing a round requires two communication rounds: one to exchange the random numbers and another to inform neighbors of nodes that have joined the MIS

Analysis

• The challenge is to analyze how fast the algorithm simplifies local neighborhoods. Ideally, as the algorithm progresses, each node’s degree (the number of its direct connections) should decrease.

• One might expect that after a few rounds, a node’s degree would halve. But, complications arise because a node’s degree reduction can be delayed if its neighbors’ degrees don’t decrease as anticipated. The degree reductions across different nodes can be interdependent, which complicates the analysis.

  (The randomness in Luby’s algorithm can lead to scenarios where some nodes consistently don’t get selected for the MIS even if they have low degrees because their neighbors might always be picking smaller random numbers. These nodes thus keep getting “unlucky” due to the choices of their neighbors, leading to delays in their removal).

Proposed Algorithm

This paper proposes a very simple and clean algorithm that guarantees for each node v that after O(log ∆+log 1/ε) rounds, with probability at least 1 − ε, node v has terminated and it knows whether it is in the (eventual) MIS or it has a neighbor in the (eventual) MIS.

This is meant to be an improvement over Luby’s algorithm, which had difficulties when determining a node’s progress in the graph due to complex interdependencies with other nodes.

Intuition

Problem of the Luby algs: The challenge in Luby’s algorithm was that a node v’s progress could be influenced by its neighbors, and those neighbors could be influenced by their neighbors, leading to a cascading chain of dependencies.

The authors aim to decouple a node’s progress from nodes that are more than two steps (or edges) away from it.

Two main ways a node v can be removed from consideration:

• Either it tries to join the MIS and doesn’t have too much competition from its neighbors.
• Or, many of its neighbors are trying to join the MIS and they don’t face much competition, so it’s likely one of them will join the MIS, causing node v to be removed.

The Algorithm:

1. Each node v has a “desire-level” p_t(v) which indicates how strongly it wants to join the MIS. It starts at 0.5.
2. A node’s “effective-degree” d_t(v) is the sum of the desire-levels of its neighbors.
3. Over time, the desire levels change based on conditions related to the effective degree.
4. In each round, node v gets marked with probability p_t(v) and if no neighbor of v is marked, v joins the MIS and gets removed along with its neighbors5

The Analysis:

1. The correctness of the algorithm is clear: those that join the MIS form an independent set, and a node stops only if it or one of its neighbors is in the MIS.
2. There are certain “golden rounds” which are particularly good for a node:
   • Either its effective degree is less than 2 or its desire-level is 0.5.
   • Or it has enough low-degree neighbors trying to join the MIS.
3. These golden rounds are essential because, during them, there’s a higher likelihood of the node joining the MIS or one of its neighbors joining, thus removing the node

Lemmas (Supporting Statements):

1. Lemma 3.1

   By a certain number of rounds, either a node has joined the MIS, or it has had many golden rounds.

   • The proof uses the definitions of the golden rounds and effective degrees to show that either a node joins the MIS or has many golden rounds.

2. Lemma 3.2

   In each golden round, there’s a good probability that the node or one of its neighbors joins the MIS.

   • The proof calculates probabilities using the desired level and effective degree to argue that during golden rounds, there’s a high chance of a node being removed from consideration.

The proposed algorithm tries to make nodes in a graph decide if they’ll join the MIS or if one of their neighbors will. This decision is influenced by their desire level and effective degree. The algorithm is designed to have nodes spend a lot of time in scenarios where they are likely to make a decision, termed golden rounds. These golden rounds have a higher probability of ensuring a node’s removal, and the algorithm ensures that nodes either join the MIS or experience many golden rounds in a logarithmic number of rounds.

Improved Global Complexity

The aim is to design a distributed MIS algorithm with a global complexity (how many rounds it takes) of O(logΔ)+2O(logΔ)+2O(loglogn)

Algorithm Basics:

1. Run the algorithm from a previous section for O(logΔ) rounds.
2. Achieve a “shattering threshold” after O(logΔ) rounds. This seems to be a state in which the graph has been sufficiently broken down into smaller components.

Key Lemmas and Ideas:

• Lemma 4.1: It says that if you have a set of nodes that are far apart from each other (at least 5 nodes apart), the probability that they all remain undecided after running the algorithm for a while is quite low.
• Lemma 4.2: After running the algorithm for some rounds, two things are likely to happen:
  • (P1) We don’t have large connected subgraphs.
  • (P2) Each connected part of our graph is small.
• Shattering Phenomena: Graph gets broken down or “shattered” into smaller components. The “2hop randomness locality” concept helps achieve this shattering.
• Finish-off Algorithm: This is the final phase of the algorithm where we’ve “shattered” the graph into smaller components. Now, we want to solve the MIS problem for these smaller parts. They do so by:
  1. Running the base MIS algorithm for a few more rounds.
  2. Grouping nodes into clusters.
  3. Contracting these clusters to form a new, simpler graph.
  4. Applying a known MIS algorithm to this simpler graph.

Concluding Result: By following the given strategy and using the outlined “finish-off” algorithm, they achieve a global complexity for the MIS problem of O(logΔ)+2O(logΔ)+2O(loglogn)

---

• ← Previous Post
• Next Post →