Distributed graph problems need longer randomized algorithms
Distributed Lower Bounds via Automatic Self-Reduction
Distributed, Parallel, and Cluster ComputingData Structures and Algorithms
Summary
The authors focused on proving that certain problems in distributed computing need more time to solve when computers work randomly. They showed that a classic technique to explain hard problems, called round elimination, can actually be used in a broader way than before. By changing how errors in algorithms are measured, they found stronger limits on how fast distributed algorithms can run. This means many graph problems, like finding matchings, require at least about the square root of the logarithm of the network size in communication rounds.
What this means in practice
- •For network protocol designers: Understand fundamental speed limits for randomized distributed algorithms solving network matching problems, guiding protocol efficiency expectations.
- •For distributed systems engineers: Assess minimum necessary communication rounds for algorithms managing resource allocation modeled as graph packing or matching, improving system design.
A theory result. No direct application yet.
Authors
Alkida Balliu, Francesco d'Amore, Dennis Olivetti
Abstract
The development of round elimination into a general-purpose technique [PODC 2019] marked a turning point in our understanding of the hardness of many graph problems in the distributed setting and led to several breakthrough results. However, the round elimination technique seems unable to yield randomized lower bounds of $ω(\log \log n)$ rounds as a function of the number $n$ of nodes. Very recently, Khoury and Schild [FOCS 2025] introduced a new technique called round elimination via self-reduction, which bypasses the limitations of classical round elimination. Using this approach, the authors show that any randomized algorithm for maximal matching requires $Ω(\sqrt{\log n})$ rounds in the LOCAL model. Their elegant technique is, in some respects, similar to classical round elimination while being fundamentally different in others. However, it is tailored specifically to maximal matching rather than being applicable to a broad class of problems. In this paper, we show that self-reduction is, in fact, a special case of classical round elimination, thereby turning it into a general-purpose approach. In particular, we introduce a new way to measure the error of an algorithm and show that, under this new measure, classical round elimination can indeed yield $ω(\log \log n)$ randomized lower bounds. More specifically, we identify a large class of problems for which this improvement is entirely black-box: once a problem is shown to belong to the class, stronger randomized lower bounds follow automatically from the classical round-elimination framework. As an application, we prove $Ω(\sqrt{\log n})$ randomized lower bounds for a range of graph problems, namely, maximal matching on regular $2$-colored graphs, $\frac{1}{k}$-integral matching, and maximal $H$-packing.