Leonid Barenboim

TCS Journal 2025 Journal Article

Sampling and output estimation in distributed algorithms and LCAs

• Leonid Barenboim
• Tzalik Maimon

We consider the distributed message-passing model and the Local Computational Algorithms (LCA) model. In both models a network is represented by an n-vertex graph G = ( V, E ). We focus on labeling problems, such as vertex-coloring, edge-coloring, maximal independent set (MIS) and maximal matching. In the distributed model the vertices of v perform computations in parallel in order to compute their own solution for solving the problem for G. In contrast, in the LCA model probes are performed on certain vertices in order to compute their labels in a solution to a given problem. In this work we study the possibility of estimating a solution produced by an algorithm, much before the algorithm terminates. This estimation not only allows for size approximation of a solution, but also for early detection of failure in randomized algorithms. We do this such that a correcting procedure can be executed. To this end, we propose a sampling technique, in which the labels in the sampling are distributed proportionally to the distribution in the algorithm's output. However, the sampling running time is significantly smaller than that of the algorithm in hand. We achieve the following results, in terms of the maximum degree Δ and the arboricity a of the input graph. The running time of our procedures is O ( log ⁡ a + log ⁡ log ⁡ n ), for sampling vertex-coloring, edge-coloring, maximal matching and MIS. This significantly improves upon previous sampling techniques, which incur additional dependency on the maximum degree Δ that can be much higher than the arboricity, as well as more significant dependency on n. Not only that, we also show that our technique extends naturally for the power graph G r for any constant integer r > 1 for the problems of MIS and coloring. Our techniques for sampling in the distributed model provide a powerful and general tool for estimation in the LCA model. In this setting the goal is estimating the size of a solution to a given problem, by making as few vertex probes as possible. For the above-mentioned problems, we achieve estimations with probe complexity d O ( log ⁡ a + log ⁡ log ⁡ n ), where d = m i n ( Δ, a ⋅ p o l y ( log ⁡ ( n ) ). Our results extend as well to power graphs for the coloring and MIS problems.

TCS Journal 2018 Journal Article

A fast network-decomposition algorithm and its applications to constant-time distributed computation

• Leonid Barenboim
• Michael Elkin
• Cyril Gavoille

A partition ( C 1, C 2, …, C q ) of G = ( V, E ) into clusters of strong (respectively, weak) diameter d, such that the supergraph obtained by contracting each C i is ℓ-colorable is called a strong (resp. , weak) ( d, ℓ ) -network-decomposition. Network-decompositions were introduced in a seminal paper by Awerbuch, Goldberg, Luby and Plotkin in 1989. Awerbuch et al. showed that strong ( d, ℓ ) -network-decompositions with d = ℓ = exp ⁡ { O ( log ⁡ n log ⁡ log ⁡ n ) } can be computed in distributed deterministic time O ( d ). Even more importantly, they demonstrated that network-decompositions can be used for a great variety of applications in the message-passing model of distributed computing. The result of Awerbuch et al. was improved by Panconesi and Srinivasan in 1992: in the latter result d = ℓ = exp ⁡ { O ( log ⁡ n ) }, and the running time is O ( d ) as well. In another remarkable breakthrough Linial and Saks (in 1992) showed that weak ( O ( log ⁡ n ), O ( log ⁡ n ) ) -network-decompositions can be computed in distributed randomized time O ( log 2 ⁡ n ). Much more recently Barenboim (2012) devised a distributed randomized constant-time algorithm for computing strong network decompositions with d = O ( 1 ). However, the parameter ℓ in his result is O ( n 1 / 2 + ϵ ). In this paper we drastically improve the result of Barenboim and devise a distributed randomized constant-time algorithm for computing strong ( O ( 1 ), O ( n ϵ ) ) -network-decompositions. As a corollary we derive a constant-time randomized O ( n ϵ ) -approximation algorithm for the distributed minimum coloring problem, improving the previously best-known O ( n 1 / 2 + ϵ ) approximation guarantee. We also derive other improved distributed algorithms for a variety of problems. Most notably, for the extremely well-studied distributed minimum dominating set problem currently there is no known deterministic polylogarithmic-time algorithm. We devise a deterministic polylogarithmic-time approximation algorithm for this problem, addressing an open problem of Lenzen and Wattenhofer (2010).

FOCS Conference 2012 Conference Paper

The Locality of Distributed Symmetry Breaking

• Leonid Barenboim
• Michael Elkin
• Seth Pettie
• Johannes Schneider 0002

We present new bounds on the locality of several classical symmetry breaking tasks in distributed networks. A sampling of the results include 1) A randomized algorithm for computing a maximal matching (MM) in O(log Δ + (log log n) 4 ) rounds, where Δ is the maximum degree. This improves a 25-year old randomized algorithm of Israeli and Itai that takes O(log n) rounds and is provably optimal for all log Δ in the range [(log log n) 4, √log n]. 2) A randomized maximal independent set (MIS) algorithm requiring O(log Δ√log n) rounds, for all Δ, and only 2 O (√log log n) rounds when Δ = poly(log n). These improve on the 25-year old O(log n)-round randomized MIS algorithms of Luby and Alon, Babai, and Itai when log Δ ≫ √log n. 3) A randomized (Δ + 1)-coloring algorithm requiring O(log Δ + 2 O ( (√log log n) ) rounds, improving on an algorithm of Schneider and Wattenhofer that takes O(log Δ + √log n) rounds. This result implies that an O(Δ)-coloring can be computed in 2 O(√log log n) rounds for all Δ, improving on Kothapalli et al. 's O(√log n)-round algorithm. We also introduce a new technique for reducing symmetry breaking problems on low arboricity graphs to low degree graphs. Corollaries of this reduction include MM and MIS algorithms for low arboricity graphs (e. g. , planar graphs and graphs that exclude any fixed minor) requiring O(√log n) and O(log 2/3 n) rounds w. h. p. , respectively.

STOC Conference 2009 Conference Paper

Distributed (delta+1)-coloring in linear (in delta) time

• Leonid Barenboim
• Michael Elkin