Pith. sign in

REVIEW 5 major objections 4 minor 31 references

Improved Network Decompositions using Small Messages with Applications on MIS, Neighborhood Covers, and Beyond

T0 review · 5 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A deterministic CONGEST algorithm computes $(g(N),g(N))$ decompositions of $G^k$ in $k g(N)\log^* S$ rounds with $g(N)=2^{O(\sqrt{\log N})}$, improving prior bounds and yielding faster MIS, neighborhood covers, spanners, and…

desk verdict The deterministic power-graph decomposition is a real advance and the paper deserves refereeing, but the marked-cluster merge step in the proof of Theorem 2.1 has a genuine gap that needs fixing. read the letter →

arxiv 1908.03500 v1 pith:JYAE5FUJ submitted 2019-08-09 cs.DS cs.DC

Mohsen Ghaffari , Julian Portmann This is my paper · ORCID
classification cs.DScs.DC MSC 68W1568W20
keywords networkdecompositionCONGESTmodeldistributedgraphalgorithmsmaximalindependentsetneighborhoodcoverspowergraphsdeterministicsmallmessages
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper's central claim is a deterministic distributed algorithm that computes a network decomposition of a power graph $G^k$ in the CONGEST model, using messages of only $O(S)$ bits in an $N$-node graph with $S$-bit identifiers, in $k g(N)\log^* S$ rounds where $g(N)=2^{O(\sqrt{\log N})}$. This matches, up to constants, the best bounds previously known only for LOCAL-model constructions, and strictly improves the earlier $O(\sqrt{\log n\log\log n})$ exponent of CONGEST algorithms for $k$-hop separated decompositions. The same decomposition powers a randomized MIS algorithm that runs in $O(\log\Delta\sqrt{\log\log n})+2^{O(\sqrt{\log\log n})}$ rounds with high probability, and deterministic constructions of sparse neighborhood covers, spanners, dominating-set approximations, and MST in the corresponding $2^{O(\sqrt{\log n})}$-type regimes. A sympathetic reader would care because network decompositions are a bottleneck primitive: shaving their complexity automatically accelerates many symmetry-breaking and locality-preserving distributed tasks.

What carries the argument

The load-bearing object is the virtual cluster graph $H$ built on the current clusters of the recursive decomposition; its vertices are clusters and its edges record $k$-hop adjacency in the base graph, i.e. edges of the $k$-th power $G^k$, where two nodes are adjacent whenever their distance in $G$ is at most $k$. The algorithm first lets each cluster learn up to $2d$ neighboring clusters, marks clusters with too many outgoing connections, and then works with an undirected $H$ of maximum degree at most $4d^2$. The decisive mechanism is the bounded-overlap invariant: every edge of the base graph is used in at most $12d^3 = 2^{O(\sqrt{\log N})}$ edges of $H$, which lets the algorithm simulate CONGEST communication on $H$ through the base graph with only that overhead. On top of $H$, an $O(d^8\log^* S)$-round coloring of $H^2$ followed by a maximal 2-independent-set computation picks the new cluster centers and bounds the number of new clusters. For the MIS application, the second mechanism is randomized ball carving by exponential shifts: many independent runs are executed in parallel in $O(\log n)$-bit messages, and the deterministic decomposition is used to verify and broadcast a successful run, boosting success probability to $1-1/\mathrm{poly}(n)$ even on components with only $N=O(\log n)$ nodes.

What would settle it

One concrete test is to run the phase-one merger on a constructed graph with many high-degree clusters whose $k$-hop neighborhoods are routed through a single base-graph edge, and count, for that edge, the number of distinct cluster-pairs that establish an edge of the virtual graph $H$. Exceeding $12d^3$ for $d=2^{O(\sqrt{\log N})}$ would refute the bounded-overlap invariant and with it the claimed simulation overhead; alternatively, an implementation that maintains the invariant on adversarial graphs would corroborate the main theorem.

Watch

Extended reading notes

Core claim

In the paper's own terms, the central result is Theorem 2.1: for any $N$-node network with $S$-bit identifiers and $O(S)$-bit messages, there is a deterministic algorithm that computes a $(g(N),g(N))$ network decomposition of $G^k$ in $k g(N)\log^* S$ rounds, and moreover simulates one round of intra-cluster communication on $G^k$ in $k 2^{O(\sqrt{\log N})}$ rounds on the base graph. The construction proceeds in $\sqrt{\log N}$ phases of recursive clustering; each phase merges some old clusters into new ones, colors and removes the leftover low-degree clusters, and maintains invariants that only $n/d^i$ clusters remain, that cluster radii grow by a constant factor per phase, and that every base-graph edge lies in at most $i\cdot 13d^3$ cluster spanning trees, with $d=2^{O(\sqrt{\log N})}$. The result is that $k$-hop separated decompositions are now available in CONGEST with large identifiers and with parameters matching the best LOCAL-model simulation known for this problem.

Load-bearing premise

The whole scheme rests on the assumption that no edge of the base network is ever needed by more than $2^{O(\sqrt{\log N})}$ different virtual cluster connections at once; if some edge must carry more than that, the claimed communication budget fails.

Editorial extensions

If this is right

  • Deterministic CONGEST algorithms for $k$-hop separated network decompositions run in $k 2^{O(\sqrt{\log N})}\log^* S$ rounds, improving the earlier $k 2^{O(\sqrt{\log n\log\log n})}$ bound even when identifiers are large.
  • Deterministic sparse $k$-neighborhood covers with $2^{O(\sqrt{\log n})}$ sparsity and diameter $k 2^{O(\sqrt{\log n})}$ can be built in $k 2^{O(\sqrt{\log n})}$ CONGEST rounds, giving a deterministic MST algorithm in $2^{O(\sqrt{\log n})}(\mu(G,\omega)+\sqrt{n})$ rounds.
  • Randomized MIS in the CONGEST model runs in $O(\log\Delta\sqrt{\log\log n})+2^{O(\sqrt{\log\log n})}$ rounds with high probability, improving prior randomized CONGEST MIS bounds.
  • Deterministic $(2k-1)$-stretch spanners of size $O(k n^{1+1/k}\log n)$ and $O(\log\Delta)$-approximations of minimum dominating set are computable in $2^{O(\sqrt{\log n})}$ CONGEST rounds.
  • Since the decomposition tolerates $S$-bit identifiers with only a $\log^* S$ factor in the round bound, the same algorithms apply unchanged to networks with very large or nonstandard identifiers.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: the bounded-overlap simulation technique is not tied to network decompositions; any low-degree virtual graph whose edges can be embedded in the base graph with at most $2^{O(\sqrt{\log N})}$ overlaps per base edge inherits the same CONGEST simulation lemmas, so the method may transfer to other virtual-topology problems such as routing or locality-preserving covers.
  • Editorial inference: the two-stage success amplification for ball carving—run many independent randomized clusterings, use a deterministic coarse decomposition to verify one—could serve as a general template for derandomizing other shattering-based algorithms on small components, not just MIS.
  • Editorial inference: the identifier-length robustness suggests the decomposition is usable when node labels carry geometric or semantic information rather than small integers; one could test whether the $\log^* S$ factor is actually necessary or an artifact of the coloring subroutine.
  • Editorial inference: if the same recursive clustering can be adapted to weighted graphs with $k$-hop balls replaced by metric balls, the neighborhood-cover and MST consequences would likely extend to weighted distributed settings; this is not claimed in the paper.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

5 major / 4 minor

Summary. The paper claims a deterministic CONGEST algorithm that computes a (g(N), g(N)) network decomposition of G^k in kg(N) log* S rounds with g(N)=2^{O(sqrt(log N))} for arbitrary S-bit identifiers, improving on the Ghaffari-Kuhn bound; it then derives a faster randomized MIS algorithm, deterministic neighborhood covers, spanners, and dominating-set approximations. The proof follows the recursive-clustering template of Awerbuch et al. and Panconesi-Srinivasan, maintaining invariants on cluster count, radius, and per-edge spanning-tree overlap, and introduces a virtual cluster graph H to cope with CONGEST congestion. The MIS section uses shattering followed by a randomized ball-carving network decomposition for small graphs.

Significance. If fully proved, the central theorem would be a substantial advance: it extends the best deterministic CONGEST network-decomposition algorithm to power graphs and to large identifiers, and it would improve several downstream bounds, including MIS, neighborhood covers, and the deterministic MST result of Elkin. The paper's high-level architecture is original and uses prior results as black boxes without circularity; the invariant-based proof structure and the virtual-graph simulation idea are plausible and valuable. However, several load-bearing steps are currently asserted rather than proved, and at least one parameter choice in the randomized section is internally inconsistent, so the manuscript is not yet ready in its present form.

major comments (5)
  1. [§2, 'Forming new clusters' and invariant (C)] The assertion that "we have to send the identifier of at most one marked cluster along each edge" does not establish invariant (C). Nothing in the text rules out two different marked clusters whose floods traverse the same undirected edge in opposite directions, in which case that edge belongs to two marked-centered spanning trees and the per-phase increase can exceed 13d^3. The subsequent claim "e is included in at most one additional cluster" is a non sequitur from the per-node knowledge bound. A concrete flooding/selection protocol is needed that either prevents such crossings or explicitly bounds the number of marked identifiers that can use one edge; without this, the 2^{O(sqrt(log N))} edge-overlap bound and the CONGEST simulation of H are not supported.
  2. [§2, 'Building a small in-degree virtual graph H'] The bounded-forwarding discovery protocol does not prove that every high-degree cluster center receives at least 2d distinct identifiers. An intermediate node that has already seen 2d+1 identifiers may drop the identifier of a neighboring cluster, and the arbitrary selection rule could drop exactly those identifiers needed for a cluster to be classified as high-degree. Since the counting of marked clusters and the progress invariant (A) depend on correct high/low-degree classification, this gap is load-bearing. A deterministic selection rule and an argument that every cluster with more than 2d neighbors is recognized as high-degree are required.
  3. [§3.1, Lemma 3.6, 'One Step of Ball Growing'] The claim that a non-good ball grows by at least a factor of 2 when extended by one hop is false in general. Growing a ball by one hop adds the set of outside neighbors of the boundary, and a large boundary can share a single outside vertex (e.g., in a star), so the ball need not double in size. Consequently the "within log N steps" termination bound, the diameter bound, and the claimed round complexity of Lemma 3.6 do not follow from the argument as written. The progress measure for the ball growing process must be reworked.
  4. [§3.2.2, Lemma 3.7, Claim 3.9 and termination] The success event with beta = 2^{-sqrt(log N) - 2} only guarantees that a 2^{-sqrt(log N)} fraction of the active meta-nodes that received a message are clustered in a phase. After sqrt(log N) phases the remaining fraction is approximately (1 - 2^{-sqrt(log N)})^{sqrt(log N)}, which is close to 1, not 0. The statement "after sqrt(log N) phases there are no meta-nodes remaining" is therefore false, and the claimed O(sqrt(log log n)) color bound and the round complexity of Lemma 3.7 are not established. The parameters must be reconciled with the claimed progress (e.g., a constant beta and a constant success fraction, or an exponential number of phases, which would change the color count).
  5. [Appendix B, Corollary B.2] The claim that the computed neighborhood cover has diameter d + k does not follow from a weak-diameter decomposition of G^{2k}. A cluster of weak diameter d in G^{2k} can have diameter up to 2k d in G, since each edge of the G^{2k} spanning tree corresponds to a path of length at most 2k in G. The proof's path-inclusion argument only shows that those G-paths are contained in the extended cluster; it does not bound their total length by d + k. The asymptotic statements in Corollary 1.3 and Corollary B.3 survive with an O(k d) bound, but the exact statement of Corollary B.2 is incorrect as written.
minor comments (4)
  1. [§3.2.3, heading] The section heading "Proof of Theorem 2.1" appears where the proof of Theorem 3.1 is given; it should be corrected to "Proof of Theorem 3.1".
  2. [§3.2.2, after Claim 3.9] The text says "at least a 2√log N fraction of meta-nodes joined a cluster"; the exponent is missing a minus sign and should read 2^{-sqrt(log N)}.
  3. [Abstract and Corollary 1.3] There are grammatical typos in the abstract ("a faster deterministic distributed algorithms" and "faster a deterministic distributed algorithm") and in Corollary 1.3 ("of and n-node graph G"). These should be fixed in revision.
  4. [§1.3, MIS overview] The phrase "We use the fact that we have a decomposition of H^k" in the proof of Lemma 3.7 is initially introduced only in the proof outline; a forward reference to the precise use of the k-hop separation would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the deterministic decomposition algorithm is self-contained and its applications use prior published results as independent black boxes.

full rationale

The paper's central derivation in Section 2 is an inductive construction of a network decomposition of G^k. The key invariant (C), bounding the number of spanning trees per edge, is established by counting forwarded messages in the construction of the virtual graph H: the paper states that each edge forwards at most 12d^3 messages, so each edge is part of at most 12d^3 edges of H, and the merge analysis adds at most one further spanning tree per marked cluster. This is an accounting argument over the algorithm's own message traffic, not a quantity fitted to the target output. The applications in Sections 3 and Appendices B and C use Theorem 2.1 as a subroutine, while prior results such as Ghaffari's MIS algorithm [Gha16], Ghaffari's ruling-set lemma [Gha19], Elkin and Neiman's ball carving [EN16], and Miller-Peng-Xu's exponential-shift lemma [MPX13] are cited as externally published black boxes with independent proofs; they are not used to define the present paper's decomposition or to presuppose its conclusion. The proof of Lemma 3.7 does use Theorem 2.1 to obtain an initial decomposition of H^K, but Theorem 2.1 is proved earlier and independently, so the dependency is acyclic rather than circular. No fitted parameter is renamed as a prediction, no definition is circular, and no uniqueness claim is imported from the authors' prior work. The flagged concern about the marked-cluster merge step is a potential correctness gap in the proof of invariant (C), but it is not circular because the assertion that each edge carries at most one marked-cluster identifier is not equivalent to the theorem being proved; it is a claimed intermediate bound. Accordingly, no circular step can be exhibited and the score is 0.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

The paper introduces no empirical fit parameters; algorithmic constants such as d and beta are analytic choices. All external inputs are standard distributed computing results used as black boxes and listed above.

assumptions (7)
  • domain assumption CONGEST model with O(log n)-bit messages and synchronous rounds; nodes have O(log n)-bit identifiers.
    The entire paper is built on this model, defined in Section 1.
  • standard math Linial's deterministic O(log* S)-round coloring algorithm exists for graphs of bounded degree.
    Invoked in Section 2 to compute O(d^8)-colorings of H^2 and O(d^2)-colorings of remaining clusters.
  • domain assumption Ghaffari's MIS algorithm and its shattering guarantees as stated in Theorem 3.2 and Lemma 3.3.
    Used as a black box in the MIS application, Section 3. The algorithm itself is reproduced in Appendix A, but the shattering lemma is assumed.
  • domain assumption Ghaffari's ruling set algorithm of Lemma 3.4 computes (k, 10k^2 log log n) ruling sets in O(k^2 log log n) rounds with high probability.
    Used in the MIS algorithm to compute (5, O(log log n)) ruling sets of remaining components.
  • standard math Miller et al. random shifts lemma (Lemma 3.8): for independent EXP(beta) random variables, the probability that the top two shifted values are within 1 is at most beta.
    Used to analyze ball carving success probability in Lemma 3.7 and Claim 3.9.
  • domain assumption Elkin-Neiman ball carving produces non-adjacent clusters of strong diameter at most 2R-2 and can be implemented with small messages.
    Used in Lemma 3.7 as the clustering primitive; the properties are taken from [EN16].
  • domain assumption The transformation of a weak-diameter network decomposition of G^2k into a sparse neighborhood cover is valid.
    Used in Appendix B (Corollary B.2) to obtain neighborhood covers and the deterministic MST algorithm; the transformation adapts [GK18].

how reviews work

0 comments
Cite this review

Pith. "Pith review of Improved Network Decompositions using Small Messages with Applications on MIS, Neighborhood Covers, and Beyond." pith.science (2026). https://pith.science/paper/JYAE5FUJ

@misc{pith2026190803500,
  author       = {Pith},
  title        = {Pith review of: Improved Network Decompositions using Small Messages with Applications on MIS, Neighborhood Covers, and Beyond},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JYAE5FUJ}},
  note         = {Machine review of arXiv:1908.03500}
}
read the original abstract

Network decompositions, as introduced by Awerbuch, Luby, Goldberg, and Plotkin [FOCS'89], are one of the key algorithmic tools in distributed graph algorithms. We present an improved deterministic distributed algorithm for constructing network decompositions of power graphs using small messages, which improves upon the algorithm of Ghaffari and Kuhn [DISC'18]. In addition, we provide a randomized distributed network decomposition algorithm, based on our deterministic algorithm, with failure probability exponentially small in the input size that works with small messages as well. Compared to the previous algorithm of Elkin and Neiman [PODC'16], our algorithm achieves a better success probability at the expense of its round complexity, while giving a network decomposition of the same quality. As a consequence of the randomized algorithm for network decomposition, we get a faster randomized algorithm for computing a Maximal Independent Set, improving on a result of Ghaffari [SODA'19]. Other implications of our improved deterministic network decomposition algorithm are: a faster deterministic distributed algorithms for constructing spanners and approximations of distributed set cover, improving results of Ghaffari, and Kuhn [DISC'18] and Deurer, Kuhn, and Maus [PODC'19]; and faster a deterministic distributed algorithm for constructing neighborhood covers, resolving an open question of Elkin [SODA'04].

Figures

Figures reproduced from arXiv: 1908.03500 by the authors.

Figure 1
Figure 1. Different states of a cluster C in the virtual graph H, where clusters are vertices and an edge C → C′ means that the center of C ′ received the identifier of C. Dashed lines indicate that clusters are neighboring, but neither center received the ID of the other center. Making H undirected with small degrees: One problem is that H is a directed graph with possibly large out-degrees, while we would like to have an un… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

31 extracted references · 29 canonical work pages

  1. [1]

    Fast distributed network decompositions and covers

    Baruch Awerbuch, Bonnie Berger, Lenore Cowen, and David Peleg. Fast distributed network decompositions and covers. Journal of Parallel and Distributed Computing , 39(2):105--114, 1996

    work page 1996

  2. [2]

    A fast and simple randomized parallel algorithm for the maximal independent set problem

    Noga Alon, L \'a szl \'o Babai, and Alon Itai. A fast and simple randomized parallel algorithm for the maximal independent set problem. Journal of algorithms , 7(4):567--583, 1986

    work page 1986

  3. [3]

    Online load balancing in a distributed network

    Baruch Awerbuch, Shay Kutten, and David Peleg. Online load balancing in a distributed network. In Proc. 24th ACM Symp. on Theory of Comput , pages 571--580, 1992

    work page 1992

  4. [4]

    Network decomposition and locality in distributed computation

    Baruch Awerbuch, Michael Luby, Andrew V Goldberg, and Serge A Plotkin. Network decomposition and locality in distributed computation. In Foundations of Computer Science, 1989., 30th Annual Symposium on , pages 364--369. IEEE, 1989

    work page 1989

  5. [5]

    Sparse partitions

    B Awerbuch and D Peleg. Sparse partitions. In Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium on , pages 503--513. IEEE, 1990

    work page 1990

  6. [6]

    Routing with polynomial communication-space srade-ff

    Baruch Awerbuch and David Peleg. Routing with polynomial communication-space srade-ff. SIAM Journal on Discrete Mathematics , 5(2):151--162, 1992

    work page 1992

  7. [7]

    Sparser: A paradigm for running distributed algorithms

    Yehuda Afek and Moty Ricklin. Sparser: A paradigm for running distributed algorithms. Journal of Algorithms , 14(2):316--328, 1993

    work page 1993

  8. [8]

    Space-efficient local computation algorithms

    Noga Alon, Ronitt Rubinfeld, Shai Vardi, and Ning Xie. Space-efficient local computation algorithms. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms , pages 1132--1139. Society for Industrial and Applied Mathematics, 2012

    work page 2012

Show all 31 references
  1. [9]

    Complexity of network synchronization

    Baruch Awerbuch. Complexity of network synchronization. Journal of the ACM (JACM) , 32(4):804--823, 1985

    1985

  2. [10]

    Efficient broadcast and light-weighted spanners

    Baruch Awerbuch. Efficient broadcast and light-weighted spanners. manuscript , 1992

    1992

  3. [11]

    On the locality of some np-complete problems

    Leonid Barenboim. On the locality of some np-complete problems. In International Colloquium on Automata, Languages, and Programming , pages 403--415. Springer, 2012

    2012

  4. [12]

    An algorithmic approach to the lov \'a sz local lemma

    J \'o zsef Beck. An algorithmic approach to the lov \'a sz local lemma. i. Random Structures & Algorithms , 2(4):343--365, 1991

    1991

  5. [13]

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

    Leonid Barenboim, Michael Elkin, and Cyril Gavoille. A fast network-decomposition algorithm and its applications to constant-time distributed computation. Theoretical Computer Science , 751:2--23, 2018

    2018

  6. [14]

    The locality of distributed symmetry breaking

    Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider. The locality of distributed symmetry breaking. Journal of the ACM (JACM) , 63(3):20, 2016

    2016

  7. [15]

    Nearly-linear work parallel sdd solvers, low-diameter decomposition, and low-stretch subgraphs

    Guy E Blelloch, Anupam Gupta, Ioannis Koutis, Gary L Miller, Richard Peng, and Kanat Tangwongsan. Nearly-linear work parallel sdd solvers, low-diameter decomposition, and low-stretch subgraphs. Theory of Computing Systems , 55(3):521--554, 2014

    2014

  8. [16]

    A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs

    Surender Baswana and Sandeep Sen. A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Structures & Algorithms , 30(4):532--563, 2007

    2007

  9. [17]

    Deterministic distributed dominating set approximation in the CONGEST model

    Janosch Deurer, Fabian Kuhn, and Yannic Maus. Deterministic distributed dominating set approximation in the CONGEST model. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing , page to appear. ACM, 2019

    2019

  10. [18]

    Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons

    Devdatt Dubhashi, Alessandro Mei, Alessandro Panconesi, Jaikumar Radhakrishnan, and Aravind Srinivasan. Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons. Journal of Computer and System Sciences , 71(4):467--479, 2005

    2005

  11. [19]

    A faster distributed protocol for constructing a minimum spanning tree

    Michael Elkin. A faster distributed protocol for constructing a minimum spanning tree. In Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms , pages 359--368. Society for Industrial and Applied Mathematics, 2004

    2004

  12. [20]

    A faster distributed protocol for constructing a minimum spanning tree

    Michael Elkin. A faster distributed protocol for constructing a minimum spanning tree. Journal of Computer and System Sciences , 72(8):1282--1308, 2006

    2006

  13. [21]

    Distributed strong diameter network decomposition

    Michael Elkin and Ofer Neiman. Distributed strong diameter network decomposition. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing , pages 211--216. ACM, 2016

    2016

  14. [22]

    An improved distributed algorithm for maximal independent set

    Mohsen Ghaffari. An improved distributed algorithm for maximal independent set. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms , pages 270--277. Society for Industrial and Applied Mathematics, 2016

    2016

  15. [23]

    Distributed maximal independent set using small messages

    Mohsen Ghaffari. Distributed maximal independent set using small messages. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 805--820. SIAM, 2019

    2019

  16. [24]

    Derandomizing distributed algorithms with small messages: Spanners and dominating set

    Mohsen Ghaffari and Fabian Kuhn. Derandomizing distributed algorithms with small messages: Spanners and dominating set. In 32nd International Symposium on Distributed Computing (DISC 2018) . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018

    2018

  17. [25]

    Fast distributed construction of smallk-dominating sets and applications

    Shay Kutten and David Peleg. Fast distributed construction of smallk-dominating sets and applications. Journal of Algorithms , 28(1):40--66, 1998

    1998

  18. [26]

    Distributive graph algorithms global solutions from local data

    Nathan Linial. Distributive graph algorithms global solutions from local data. In Foundations of Computer Science, 1987., 28th Annual Symposium on , pages 331--335. IEEE, 1987

    1987

  19. [27]

    Low diameter graph decompositions

    Nathan Linial and Michael Saks. Low diameter graph decompositions. Combinatorica , 13(4):441--454, 1993

    1993

  20. [28]

    A simple parallel algorithm for the maximal independent set problem

    Michael Luby. A simple parallel algorithm for the maximal independent set problem. SIAM journal on computing , 15(4):1036--1053, 1986

    1986

  21. [29]

    Parallel graph decompositions using random shifts

    Gary L Miller, Richard Peng, and Shen Chen Xu. Parallel graph decompositions using random shifts. In Proceedings of the twenty-fifth annual ACM symposium on Parallelism in algorithms and architectures , pages 196--203. ACM, 2013

    2013

  22. [30]

    Distributed computing

    David Peleg. Distributed computing. SIAM Monographs on discrete mathematics and applications , 5, 2000

    2000

  23. [31]

    Improved distributed algorithms for coloring and network decomposition problems

    Alessandro Panconesi and Aravind Srinivasan. Improved distributed algorithms for coloring and network decomposition problems. In Proceedings of the twenty-fourth annual ACM symposium on Theory of computing , pages 581--592. ACM, 1992

    1992

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.