💻 computer science

A Few Shared Random Bits Suffice for Constant-Round Almost Stable Matching

This paper presents a constant-round distributed algorithm for computing an almost stable matching on general bipartite graphs in the CONGEST model using only a few shared random bits, overcoming previous limitations that required polylogarithmic rounds or restricted graph structures by introducing a novel degree-guarded freezing rule.

Original authors: Yijun Chang, Kushagra Chatterjee

Published 2026-08-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yijun Chang, Kushagra Chatterjee

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of computer science, there is a classic puzzle known as the stable marriage problem. Imagine a group of people, divided into two groups, where every person has a ranked list of who they would prefer to be paired with. The goal is to pair everyone up so that no two people would rather be with each other than with their assigned partners. If such a pair exists, they are called a "blocking pair," and the arrangement is considered unstable. For decades, computer scientists have known how to find a perfect, stable arrangement, but doing so on a large network of computers requires a great deal of time and communication. The process is inherently global, meaning every computer often needs to wait for information to travel across the entire network, a delay that grows as the network gets larger. This creates a bottleneck for modern systems that need to make quick decisions.

To solve this, researchers have explored the idea of "almost stable" matching. Instead of demanding a perfect arrangement with zero blocking pairs, they ask for a solution that is good enough, allowing for a tiny, controlled fraction of unhappy pairs. The hope is that by relaxing the rules slightly, the problem becomes local, meaning computers can solve it quickly without waiting for the whole network to catch up. Previous attempts to solve this on general networks, where some people have many connections and others have few, were stuck with a slow, logarithmic delay that grew with the size of the network. The question remained: could we find a nearly perfect solution in a constant number of steps, regardless of how large the network is?

A new study by Yi-Jun Chang and Kushagra Chatterjee answers this question with a definitive yes, provided the computers share a very small amount of random information. The researchers developed a method that allows a network of computers to reach an almost stable matching in a fixed number of rounds, a time that does not increase even if the network grows to include millions of nodes. The key to their success lies in a clever new rule they call a "degree-guarded freezing rule." In their system, when a person with many connections is paired with someone who has very few, the pair is immediately "frozen." This means they are locked in place, and no one else can try to break them up. This simple mechanism prevents the algorithm from getting stuck in a cycle of high-degree individuals constantly swapping partners, a problem that had plagued previous attempts.

The researchers found that by using this freezing rule, they could handle networks with wildly different connection counts simultaneously, without needing to process different groups of people in separate, sequential stages. This eliminated the need for the complex, multi-step thresholds that caused delays in earlier algorithms. However, this approach produces a solution that is statistically good on average, rather than guaranteeing a perfect result in every single step. To ensure the final output is consistently good, the computers use a tiny amount of shared randomness—just a few bits of common data—to agree on which specific moment in the process to stop and declare the result. This shared seed allows them to pick a random iteration where the expected number of blocking pairs is guaranteed to be low.

The implications of this work extend beyond just the theoretical model of computer networks. The researchers demonstrated that their method works efficiently in the standard communication model used for distributed systems, where messages are limited in size. They also showed that the shared randomness is not strictly necessary; if the computers do not start with a common random seed, they can generate it locally within a slightly longer, but still efficient, timeframe. Furthermore, the algorithm translates directly to the massively parallel computing model used by modern data centers, where thousands of machines work together with limited memory. In this setting, the method achieves the same constant-time performance, proving that the solution is robust across different types of computing architectures.

The study also clarifies the limits of what is possible. The authors proved that even with shared randomness, it is impossible to solve the problem faster than a certain minimum time that depends on how strict the requirement for stability is. If one demands a solution that is almost perfectly stable, the time required grows as the allowed margin for error shrinks. This establishes a clear boundary for the problem, showing that while the new method is a significant improvement, it is not a magic bullet that removes all constraints. The work leaves open the question of whether a deterministic method—one that does not rely on any randomness at all—can achieve the same constant speed, but it firmly establishes that with a small amount of shared luck, the problem is solvable in a constant number of steps.

This breakthrough changes the understanding of how local algorithms can handle global problems. By introducing the degree-guarded freezing rule, the researchers found a way to bypass the traditional need for sequential processing of different network densities. The result is a system that is both fast and scalable, capable of handling the messy, uneven reality of real-world networks where some nodes are hubs and others are leaves. The paper concludes that for any fixed level of acceptable imperfection, a stable matching can be found quickly, independent of the network's size, marking a significant step forward in the theory of distributed computing.

Technical Summary: A Few Shared Random Bits Suffice for Constant-Round Almost Stable Matching

Problem Statement

The paper addresses the stable marriage problem in the context of distributed computing. Given a bipartite graph $G = (Y \cup X, E)$ where vertices represent men and women with strict preference orderings over their neighbors, the goal is to find a matching with no "blocking pairs" (edges where both endpoints prefer each other to their current partners).

While the classical Gale–Shapley algorithm guarantees an exact stable matching, it is inherently global, requiring $\Omega(n)$ rounds in the distributed LOCAL model and $\Omega(\sqrt{n/\log^2 n})$ in the CONGEST model, even for graphs with small diameter. To circumvent these lower bounds, the paper focuses on almost stable matching: finding a matching $M$ such that the expected number of blocking pairs, $bp(M)$, is at most $\epsilon|E|$ for a given parameter $0 < \epsilon \le 1/2$ .

The central question is whether such an approximation can be achieved in constant rounds (independent of $n$ ) on general bipartite graphs with arbitrary degree distributions, specifically within the CONGEST model.

Methodology

1. The Quantile-Based Framework

The authors build upon the framework introduced by Ostrovsky and Rosenbaum [OR15], which partitions each vertex's preference list into $k = \Theta(1/\epsilon)$ quantiles. The algorithm proceeds in iterations where men propose to women within specific quantiles. A "quantile match" procedure ensures that after a constant number of rounds, men are either matched or have exhausted their current quantile.

2. Identifying Previous Limitations

The authors identify two sources of dependence on $n$ in the Ostrovsky–Rosenbaum algorithm for general graphs:

Maximal Matching: The algorithm repeatedly computes maximal matchings to resolve conflicts, which incurs polylogarithmic round complexity.
Degree Thresholds: To handle non-uniform degrees, the previous algorithm processes men in $\Theta(\log n)$ successive iterations based on geometrically increasing degree thresholds. This sequential processing prevents constant-round complexity.

3. Proposed Algorithmic Innovations

The paper introduces two key technical modifications to achieve constant rounds:

Edge-Based Almost-Maximal Matching: Instead of computing a full maximal matching in each proposal round, the algorithm uses a truncated randomized procedure to compute an almost-maximal matching. This ensures the expected number of residual edges (edges not covered by the matching) is small, removing the dependency on the maximal matching complexity.
Degree-Guarded Freezing Rule: This is the core contribution. The algorithm introduces a rule where a pair $(m, w)$ is "frozen" (and all other live edges incident to $w$ are deleted) if the man's degree significantly exceeds the woman's degree ( $d(m) > R \cdot d(w)$ for a parameter $R = \Theta(1/\epsilon)$ ).
- Mechanism: Once frozen, the pair cannot be displaced. This prevents high-degree men from being displaced late in the process, which would otherwise cause a spike in the number of blocking pairs.
- Charging Argument: The freezing rule allows for a single global charging argument that handles all degrees simultaneously. When a man is displaced, the degree guard ensures $d(m) \le R \cdot d(w)$ , allowing the cost of the displacement to be charged to the woman's degree. This eliminates the need for $\Theta(\log n)$ degree thresholds.

4. Role of Shared Randomness

The algorithm runs for $L = \Theta(1/\epsilon^3)$ iterations. The analysis shows that the average number of blocking pairs over these iterations is small, but the algorithm cannot deterministically identify which specific iteration yields a good matching.

With Shared Randomness: All vertices use $O(\log(1/\epsilon))$ shared random bits to agree on a uniformly random iteration index $J$ and output the matching from that iteration. This ensures the expected number of blocking pairs is $\le \epsilon|E|$ .
Without Shared Randomness: The authors utilize a low-diameter decomposition (Miller, Peng, and Xu [MPX13]) to partition the graph into clusters. Shared randomness is generated locally within each cluster, and the algorithm runs in parallel. Inter-cluster edges are counted as potential blocking pairs. This adds an additive $O(\log n / \epsilon)$ term to the round complexity.

Key Results

Theoretical Bounds

With Shared Randomness (Theorem 1):
- Model: CONGEST.
- Complexity: $O\left(\frac{\log(1/\epsilon)}{\epsilon^4}\right)$ rounds.
- Randomness: $O(\log(1/\epsilon))$ shared random bits.
- Guarantee: $E[bp(M)] \le \epsilon|E|$ .
- Significance: For constant $\epsilon$ , the round complexity is $O(1)$ , independent of $n$ and the maximum degree $\Delta$ .
Without Shared Randomness (Theorem 2):
- Model: CONGEST.
- Complexity: $O\left(\frac{\log(1/\epsilon)}{\epsilon^4} + \frac{\log n}{\epsilon}\right)$ rounds.
- Guarantee: $E[bp(M)] \le \epsilon|E|$ .
- Significance: Improves upon the previous best randomized bound of $O(\log^2 n)$ (derived from Ostrovsky–Rosenbaum) to $O(\log n)$ for constant $\epsilon$ .
Massively Parallel Computation (MPC) (Theorem 3):
- Model: Fully-scalable MPC (local memory $n^\delta$ , total memory $O(n+|E|)$ ).
- Complexity: $O\left(\frac{\log(1/\epsilon)}{\epsilon^4}\right)$ rounds.
- Significance: This is the first algorithm for almost stable matching in the fully-scalable MPC model.
Lower Bound (Theorem 4):
- In the LOCAL model with shared randomness, any algorithm computing a $(1-\epsilon)$ -stable matching with probability $> 1/2$ requires $\Omega(1/\epsilon)$ rounds. This is derived from the lower bound for exact stable matching by Floréen et al. [FKP+10].

Significance and Claims

The paper claims to resolve the open question of whether almost stable matching can be solved in constant rounds on general bipartite graphs.

Breaking the Logarithmic Barrier: Previous algorithms for general graphs had round complexities dependent polylogarithmically on $n$ (specifically $O(\log^2 n)$ in the randomized CONGEST setting). This work achieves $O(1)$ rounds (for constant $\epsilon$ ) by removing the dependence on $n$ through the degree-guarded freezing rule and shared randomness.
Handling Arbitrary Degrees: The degree-guarded freezing rule is presented as a novel technique that allows a single global charging argument to replace the complex, sequential degree-thresholding mechanisms of prior work.
Efficiency in MPC: The adaptation to the fully-scalable MPC model demonstrates the algorithm's robustness in environments with severe memory constraints per machine, a regime where many graph problems are difficult.

The authors note that while shared randomness is used to select the output iteration, the core algorithmic logic (the proposal process and freezing rules) does not inherently require it, allowing for a removal of this assumption at the cost of an additive $O(\log n)$ term.

AI Disclosure

The paper includes a specific disclosure stating that the manuscript was originally developed during 2024–2025 but was abandoned after the authors discovered a critical flaw in the proof in January 2025 that they were unable to repair at the time. The project was revived in 2026 with the assistance of OpenAI's ChatGPT (GPT-5.6 Sol). The AI proposed the degree-guarded freezing rule, which repaired the flawed proof, and assisted extensively in drafting and revising the text. The authors assert they verified all AI-generated content and take full responsibility for the paper's correctness.