pith. sign in

arxiv: 2605.17961 · v1 · pith:DTSFQ34Ynew · submitted 2026-05-18 · 💻 cs.DC

The Task Completion Problem and its Application to Crash-Resilient Computation

Orr Fischer , Ran Gelles This is my paper

Pith reviewed 2026-05-20 00:49 UTC · model grok-4.3

classification 💻 cs.DC
keywords task completioncongested cliquecrash faultsload balancing covering familyfault-tolerant simulationdeterministic distributed algorithmworkload balancingcrash-resilient computation
0
0 comments X

The pith

A load balancing covering family lets n crash-prone nodes finish M tasks in O(ceil(M/n) log n) rounds.

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

The paper studies the Task Completion problem where M abstract tasks must be completed by n nodes, up to a constant fraction of which may crash. It gives a deterministic congested-clique algorithm that finishes every task in O(ceil(M/n) log n) rounds and shows this bound is optimal up to log log n factors. The algorithm rests on a combinatorial object called a load balancing covering family that assigns each task to a subset of nodes so that work stays balanced and every remaining task keeps enough active candidates no matter which nodes fail. A sympathetic reader would care because the same method yields an improved simulation of arbitrary T-round congested-clique algorithms that tolerates crashes in O(T squared log n plus T log squared n) rounds.

Core claim

The paper claims that a load balancing covering family induces, for each task, a subset of responsible nodes whose properties guarantee that no node ever holds too many incomplete tasks and no task is left with too few potential workers, even after arbitrary crashes of up to alpha n nodes; when this family is used inside a simple round-robin scheduling loop, all M tasks are completed in O(ceil(M/n) log n) rounds.

What carries the argument

A load balancing covering family: a collection of node subsets, one per task, whose intersection and union properties force balanced workload and continued progress on every remaining task regardless of which nodes have crashed.

If this is right

  • Any T-round congested-clique algorithm can be simulated under up to alpha n crashes in O(T squared log n plus T log squared n) rounds.
  • The task-completion bound is optimal up to log log n factors.
  • Workload remains balanced and every unfinished task retains enough live candidates after any crash pattern.
  • The method improves the previous simulation bound of T squared times 2 to the O of square-root log n times log log n.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same covering-family technique may apply directly to other distributed models that tolerate a constant fraction of crashes.
  • Closing the remaining log log n gap would require either a stronger family or a matching lower bound construction.
  • The approach suggests a general template for turning static combinatorial objects into dynamic fault-tolerant schedulers.

Load-bearing premise

Such a load balancing covering family exists and can be built so that its coverage and load properties hold for every possible set of crashes and every possible set of still-incomplete tasks.

What would settle it

An explicit family of subsets for given n and M, together with a crash pattern and a set of unfinished tasks, in which some node receives more than O(ceil(M/n) log n) work or some task loses all its assigned nodes before completion.

read the original abstract

We study the Task Completion problem, in which $M$ abstract tasks must be completed by a network of $n$ crash-prone nodes, where up to $\alpha n$ nodes may crash for some constant $\alpha<1$. Our main result is a deterministic congested-clique algorithm that completes all $M$ tasks in $O(\lceil M/n\rceil \log n)$ rounds. This round complexity is optimal up to $\log\log n$ terms. The key technical ingredient underlying our algorithm is a novel combinatorial structure, which we call a \emph{load balancing covering family}. In essence, this covering family induces, for each task, a subset of nodes responsible for attempting to complete it. The properties of the load balancing covering family guarantee that, regardless of which tasks remain incomplete and which nodes crash, (i) no node is overloaded with incomplete tasks, and (ii) no task is left with too few potential assigned nodes. This yields a balanced per-node workload and prevents non-crashed nodes from being concentrated on a small subset of tasks, thereby ensuring sufficient progress in completing the remaining tasks. As an application of our task completion method, we give a deterministic algorithm for simulating any $T$-round congested-clique algorithm in the presence of up to $\alpha n$ crash faults in $O(T^2 \log n + T \log^2 n)$ rounds. This improves upon a recent result by Censor-Hillel et al. (DISC~2025), which requires $T^2\cdot 2^{O(\sqrt{\log n}\log\log n)}$ rounds.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper defines the Task Completion problem: complete M abstract tasks on n nodes in the congested-clique model, tolerating up to αn crashes for constant α<1. The central result is a deterministic algorithm achieving O(⌈M/n⌉ log n) rounds, claimed optimal up to log log n factors. The algorithm repeatedly applies a novel load balancing covering family that, for any set of remaining tasks and any crash set of size ≤αn, assigns tasks so that (i) no live node is overloaded and (ii) every remaining task retains sufficiently many live nodes. This yields per-phase progress that multiplies to the stated bound. The same primitive is used to simulate an arbitrary T-round congested-clique algorithm under crashes in O(T² log n + T log² n) rounds, improving the dependence on T relative to Censor-Hillel et al. (DISC 2025).

Significance. If the load-balancing covering family can be constructed deterministically inside the congested-clique model and the two invariants are proven to hold simultaneously for constant α<1, the result supplies a near-optimal primitive for fault-tolerant task execution and a quadratic improvement in simulation overhead. Both contributions are load-bearing for reliable distributed computation in high-bandwidth models and would be of interest to the DISC/ PODC community.

major comments (2)
  1. [§4] §4 (Construction of the load balancing covering family): The manuscript must exhibit an explicit, deterministic construction of the family together with a proof that, for every subset S of unfinished tasks and every crash set C with |C|≤αn, the induced assignment satisfies both (i) maximum load O(⌈M/n⌉) on any live node and (ii) every task in S is assigned to Ω(log n) live nodes. Without a self-contained argument that these two combinatorial properties hold simultaneously, the per-phase progress argument that produces the log n factor cannot be verified.
  2. [§5] §5 (Simulation application): The reduction from arbitrary T-round congested-clique algorithms to the task-completion primitive must be spelled out, including how the O(T² log n + T log² n) bound is obtained and why the log n factor from task completion does not inflate further when tasks correspond to message deliveries.
minor comments (2)
  1. [Abstract] Abstract and §1: The optimality claim is stated as 'up to log log n terms'; the paper should clarify whether this gap arises from a known lower bound or from the current analysis of the covering family.
  2. [§2] Notation: The parameter α is introduced as a constant <1 but never instantiated; a concrete range (e.g., α≤1/3) should be fixed when the covering-family parameters are chosen.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive review. The comments highlight important points for clarity and completeness. We address each major comment below and will revise the manuscript to strengthen the presentation while preserving the core contributions.

read point-by-point responses

  1. Referee: [§4] §4 (Construction of the load balancing covering family): The manuscript must exhibit an explicit, deterministic construction of the family together with a proof that, for every subset S of unfinished tasks and every crash set C with |C|≤αn, the induced assignment satisfies both (i) maximum load O(⌈M/n⌉) on any live node and (ii) every task in S is assigned to Ω(log n) live nodes. Without a self-contained argument that these two combinatorial properties hold simultaneously, the per-phase progress argument that produces the log n factor cannot be verified.

    Authors: We agree that the exposition in §4 requires expansion for full self-containment. The manuscript already presents a deterministic construction of the load-balancing covering family (via a combinatorial design that can be computed locally from n and M) together with the two invariants. However, the simultaneous proof that both the O(⌈M/n⌉) load bound and the Ω(log n) coverage per task hold for arbitrary remaining S and crash set C of size ≤αn is only sketched. In the revision we will insert a complete, self-contained combinatorial argument establishing both properties at once; this will directly justify the multiplicative log n progress per phase without external references. revision: yes

  2. Referee: [§5] §5 (Simulation application): The reduction from arbitrary T-round congested-clique algorithms to the task-completion primitive must be spelled out, including how the O(T² log n + T log² n) bound is obtained and why the log n factor from task completion does not inflate further when tasks correspond to message deliveries.

    Authors: We will expand §5 with a detailed reduction. Each round of the original T-round algorithm is simulated by treating the required message deliveries as tasks in one invocation of the Task Completion primitive. Because the covering family is reusable and the per-phase progress multiplies across O(log n) phases, the cost per simulated round is O(n log n) in the worst case (M = Θ(n²)). Summing over T rounds produces the T² log n term; the additional T log² n term accounts for the overhead of maintaining the family and handling crash detection. The log n factor does not compound further because each simulated round invokes the primitive only once and the invariants guarantee linear progress in the number of completed deliveries per phase, independent of prior rounds. revision: yes

Circularity Check

0 steps flagged

No circularity; combinatorial construction of load balancing covering family is independent

full rationale

The derivation introduces a novel load balancing covering family as a combinatorial object whose properties (balanced per-node workload and sufficient live nodes per task for any crash set of size ≤ αn and any unfinished task subset) are established directly by deterministic construction in the congested-clique model. The O(⌈M/n⌉ log n) bound follows from repeated application of this family to guarantee per-phase progress, but the family's existence and invariants are proven combinatorially without reducing to the target round complexity by definition, parameter fitting, or self-referential equations. The simulation result is a separate reduction that inherits the same independent primitive. No load-bearing step collapses to its own inputs or a self-citation chain; the argument is self-contained against external combinatorial benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The central claim rests on the standard congested-clique communication model with crash faults and the existence of the newly introduced load balancing covering family; no free parameters or additional invented entities beyond the covering family are visible from the abstract.

axioms (2)
  • domain assumption Congested-clique model where every pair of nodes can exchange messages of size O(log n) per round
    Standard assumption in the field for the algorithm's communication setting
  • domain assumption Up to αn nodes may crash for constant α < 1
    Core fault model stated in the problem definition
invented entities (1)
  • load balancing covering family no independent evidence
    purpose: Induces subsets of nodes responsible for each task to ensure no overload and sufficient coverage despite crashes
    Novel combinatorial object introduced as the key technical ingredient

pith-pipeline@v0.9.0 · 5823 in / 1358 out tokens · 51638 ms · 2026-05-20T00:49:57.813053+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

52 extracted references · 52 canonical work pages · 1 internal anchor

  1. [1]

    Anderson and Heather Woll

    Richard J. Anderson and Heather Woll. Algorithms for the certified Write-All problem.SIAM Journal on Computing, 26(5):1277–1283, 1997. 21

    work page 1997

  2. [2]

    Byzantine connectivity testing in the congested clique

    John Augustine, Anisur Rahaman Molla, Gopal Pandurangan, and Yadu Vasudev. Byzantine connectivity testing in the congested clique. In36th International Symposium on Distributed Computing (DISC), volume 246, pages 7:1–7:21, 2022

    work page 2022

  3. [3]

    Efficient deterministic distributed coloring with small bandwidth

    Philipp Bamberger, Fabian Kuhn, and Yannic Maus. Efficient deterministic distributed coloring with small bandwidth. InACM Symposium on Principles of Distributed Computing (PODC), pages 243–252, 2020

    work page 2020

  4. [4]

    Buss, Paris C

    Jonathan F. Buss, Paris C. Kanellakis, Prabhakar L. Ragde, and Alex Allister Shvartsman. Parallel algorithms with processor failures and delays.Journal of Algorithms, 20(1):45–86, 1996

    work page 1996

  5. [5]

    Quantum distributed algorithms for detection of cliques

    Keren Censor-Hillel, Orr Fischer, François Le Gall, Dean Leitersdorf, and Rotem Oshman. Quantum distributed algorithms for detection of cliques. In13th Innovations in Theoretical Computer Science Conference (ITCS), volume 215, pages 35:1–35:25, 2022

    work page 2022

  6. [6]

    Two for One, One for All: Deterministic LDC–Based Robust Computation in Congested Clique

    Keren Censor-Hillel, Orr Fischer, Ran Gelles, and Pedro Soto. Two for One, One for All: Deterministic LDC–Based Robust Computation in Congested Clique. In39th International Symposium on Distributed Computing (DISC 2025), volume 356 ofLIPIcs, pages 20:1–20:19, 2025

    work page 2025

  7. [7]

    Fast distributed algorithms for girth, cycles and small subgraphs

    Keren Censor-Hillel, Orr Fischer, Tzlil Gonen, François Le Gall, Dean Leitersdorf, and Rotem Oshman. Fast distributed algorithms for girth, cycles and small subgraphs. In34th International Symposium on Distributed Computing (DISC), volume 179, pages 33:1–33:17, 2020

    work page 2020

  8. [8]

    On distributed listing of cliques

    Keren Censor-Hillel, François Le Gall, and Dean Leitersdorf. On distributed listing of cliques. InSymposium on Principles of Distributed Computing (PODC), pages 474–482, 2020

    work page 2020

  9. [9]

    Computing in a Faulty Congested Clique

    Keren Censor-Hillel and Pedro Soto. Computing in a Faulty Congested Clique. In29th International Conference on Principles of Distributed Systems (OPODIS), volume 361, pages 10:1–10:19, 2025

    work page 2025

  10. [10]

    The complexity of (∆+1) coloring in congested clique, massively parallel computation, and centralized local computation

    Yi-Jun Chang, Manuela Fischer, Mohsen Ghaffari, Jara Uitto, and Yufan Zheng. The complexity of (∆+1) coloring in congested clique, massively parallel computation, and centralized local computation. InProceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 471–480, 2019

    work page 2019

  11. [11]

    Chlebus, Roberto De Prisco, and Alex A

    Bogdan S. Chlebus, Roberto De Prisco, and Alex A. Shvartsman. Performing tasks on restartable message-passing processors. In Marios Mavronicolas and Philippas Tsigas, editors,Distributed Algorithms, pages 96–110. Springer Berlin Heidelberg, 1997

    work page 1997

  12. [12]

    Chlebus, Leszek Gąsieniec, Dariusz R

    Bogdan S. Chlebus, Leszek Gąsieniec, Dariusz R. Kowalski, and Alexander A. Schwarzmann. Doing-it-All with bounded work and communication.Information and Computation, 254:1–40, 2017

    work page 2017

  13. [13]

    Chlebus, Leszek Gąsieniec, Dariusz R

    Bogdan S. Chlebus, Leszek Gąsieniec, Dariusz R. Kowalski, and Alex A. Shvartsman. A robust randomized algorithm to perform independent tasks.Journal of Discrete Algorithms, 6(4):651– 665, 2008. Selected papers from the 1st Algorithms and Complexity in Durham Workshop (ACiD 2005). 22

    work page 2008

  14. [14]

    Chlebus and Dariusz R

    Bogdan S. Chlebus and Dariusz R. Kowalski. Randomization helps to perform independent tasks reliably.Random Structures & Algorithms, 24(1):11–41, 2004

    work page 2004

  15. [15]

    Recognizing hereditary proper- ties in the presence of byzantine nodes

    David Cifuentes-Núñez, Pedro Montealegre, and Ivan Rapaport. Recognizing hereditary proper- ties in the presence of byzantine nodes. In Andrei Arusoaie, Emanuel Onica, Michael Spear, and Sara Tucci Piergiovanni, editors,29th International Conference on Principles of Distributed Sys- tems (OPODIS), LIPIcs, pages 26:1–26:15. Schloss Dagstuhl - Leibniz-Zentr...

    work page 2025

  16. [16]

    Optimal (Degree+1)-coloring in congested clique

    Sam Coy, Artur Czumaj, Peter Davies, and Gopinath Mishra. Optimal (Degree+1)-coloring in congested clique. In50th International Colloquium on Automata, Languages, and Programming (ICALP), volume 261, pages 46:1–46:20, 2023

    work page 2023

  17. [17]

    Simple, deterministic, constant-round coloring in congested clique and MPC.SIAM J

    Artur Czumaj, Peter Davies, and Merav Parter. Simple, deterministic, constant-round coloring in congested clique and MPC.SIAM J. on Computing, 50(5):1603–1626, 2021

    work page 2021

  18. [18]

    Schwarzmann

    Seda Davtyan, Roberto De Prisco, Chryssis Georgiou, Theophanis Hadjistasi, and Alexander A. Schwarzmann. Coordinated cooperative task computing using crash-prone processors with unreliable multicast.Journal of Parallel and Distributed Computing, 109:272–285, 2017

    work page 2017

  19. [19]

    Time-optimal message-efficient work perfor- mance in the presence of faults

    Roberto De Prisco, Alain Mayer, and Moti Yung. Time-optimal message-efficient work perfor- mance in the presence of faults. InProceedings of the Thirteenth Annual ACM Symposium on Principles of Distributed Computing, PODC ’94, page 161–172, 1994

    work page 1994

  20. [20]

    Tri, Tri Again

    Danny Dolev, Christoph Lenzen, and Shir Peled. “Tri, Tri Again”: Finding triangles and small subgraphs in a distributed setting. InDistributed Computing, volume 7611, pages 195–209. Springer, 2012

    work page 2012

  21. [21]

    Halpern, and Orli Waarts

    Cynthia Dwork, Joseph Y. Halpern, and Orli Waarts. Performing work efficiently in the presence of faults. InProceedings of the Eleventh Annual ACM Symposium on Principles of Distributed Computing, PODC ’92, page 91–102, 1992

    work page 1992

  22. [22]

    Shvartsman

    Antonio Fernández, Chryssis Georgiou, Alexander Russell, and Alex A. Shvartsman. The Do-All problem with Byzantine processor failures.Theoretical Computer Science, 333(3):433–454, 2005. Structural Information and Communication Complexity

    work page 2005

  23. [23]

    Possibilities and impossibilities for distributed subgraph detection

    Orr Fischer, Tzlil Gonen, Fabian Kuhn, and Rotem Oshman. Possibilities and impossibilities for distributed subgraph detection. InProceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 153–162, 2018

    work page 2018

  24. [24]

    All-to-all communication with mobile edge adversary: Almost linearly more faults, for free

    Orr Fischer and Merav Parter. All-to-all communication with mobile edge adversary: Almost linearly more faults, for free. InProceedings of the ACM Symposium on Principles of Distributed Computing, PODC ’25, page 326–336, 2025

    work page 2025

  25. [25]

    Shvartsman

    Chryssis Georgiou, Alexander Russell, and Alex A. Shvartsman. The complexity of synchronous iterative Do-All with crashes.Distributed Computing, 17(1):47–63, 2004

    work page 2004

  26. [26]

    Shvartsman.Do-All Computing in Distributed Systems: Cooperation in the Presence of Adversity

    Chryssis Georgiou and Alexander A. Shvartsman.Do-All Computing in Distributed Systems: Cooperation in the Presence of Adversity. Springer New York, 2008. 23

    work page 2008

  27. [27]

    MST in log-star rounds of congested clique

    Mohsen Ghaffari and Merav Parter. MST in log-star rounds of congested clique. InProceedings of the 2016 ACM Symposium on Principles of Distributed Computing (PODC), pages 19–28, 2016

    work page 2016

  28. [28]

    Hegeman, Gopal Pandurangan, Sriram V

    James W. Hegeman, Gopal Pandurangan, Sriram V. Pemmaraju, Vivek B. Sardeshmukh, and Michele Scquizzato. Toward optimal bounds in the congested clique: Graph connectivity and MST. InProceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 91–100, 2015

    work page 2015

  29. [29]

    Triangle finding and listing in CONGEST networks

    Taisuke Izumi and François Le Gall. Triangle finding and listing in CONGEST networks. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 381–389, 2017

    work page 2017

  30. [30]

    MST inO(1) rounds of congested clique

    Tomasz Jurdzinski and Krzysztof Nowicki. MST inO(1) rounds of congested clique. InPro- ceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2620–2632, 2018

    work page 2018

  31. [31]

    P. C. Kanellakis and A. A. Shvartsman. Efficient parallel algorithms can be made robust. In Proceedings of the Eighth Annual ACM Symposium on Principles of Distributed Computing, PODC ’89, page 211–219, 1989

    work page 1989

  32. [32]

    Springer Science & Business Media, 1997

    Paris Christos Kanellakis and Alex Allister Shvartsman.Fault-tolerant parallel computation, volume 401 ofThe Springer International Series in Engineering and Computer Science. Springer Science & Business Media, 1997

    work page 1997

  33. [33]

    Z. M. Kedem, K. V. Palem, A. Raghunathan, and P. G. Spirakis. Combining tentative and definite executions for very fast dependable parallel computing. InProceedings of the Twenty- Third Annual ACM Symposium on Theory of Computing, STOC ’91, page 381–390, 1991

    work page 1991

  34. [34]

    Z. M. Kedem, K. V. Palem, and P. G. Spirakis. Efficient robust parallel computations. In Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, STOC ’90, page 138–148, 1990

    work page 1990

  35. [35]

    Deterministic MST Sparsification in the Congested Clique

    Janne H. Korhonen. Deterministic MST sparsification in the congested clique.CoRR, abs/1605.02022, 2016

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  36. [36]

    Musiał, and Alexander A Shvartsman

    Dariusz Kowalski, Peter M. Musiał, and Alexander A Shvartsman. Explicit combinatorial structures for cooperative distributed algorithms. In25th IEEE International Conference on Distributed Computing Systems (ICDCS’05), pages 49–58. IEEE, 2005

    work page 2005

  37. [37]

    Fault-tolerant graph realizations in the congested clique, revisited

    Manish Kumar. Fault-tolerant graph realizations in the congested clique, revisited. InDistributed Computing and Intelligent Technology, volume 13776, pages 84–97. Springer, 2023

    work page 2023

  38. [38]

    Fault-tolerant graph realizations in the congested clique

    Manish Kumar, Anisur Rahaman Molla, and Sumathi Sivasubramaniam. Fault-tolerant graph realizations in the congested clique. InAlgorithmics of Wireless Networks, volume 13707, pages 108–122, 2022

    work page 2022

  39. [39]

    Optimal deterministic routing and sorting on the congested clique

    Christoph Lenzen. Optimal deterministic routing and sorting on the congested clique. In Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing (PODC), pages 42–50, 2013. 24

    work page 2013

  40. [40]

    Minimum-weight spanning tree construction inO(log logn) communication rounds.SIAM J

    Zvi Lotker, Boaz Patt-Shamir, Elan Pavlov, and David Peleg. Minimum-weight spanning tree construction inO(log logn) communication rounds.SIAM J. on Computing, 35(1):120–131, 2005

    work page 2005

  41. [41]

    Cambridge university press, 2017

    MichaelMitzenmacherandEliUpfal.Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge university press, 2017

    work page 2017

  42. [42]

    Joseph Naor and Ron M. Roth. Constructions of permutation arrays for certain scheduling cost measures.Random Structures & Algorithms, 6(1):39–50, 1995

    work page 1995

  43. [43]

    A deterministic algorithm for the MST problem in constant rounds of congested clique

    Krzysztof Nowicki. A deterministic algorithm for the MST problem in constant rounds of congested clique. In53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1154–1165, 2021

    work page 2021

  44. [44]

    On the distributed complexity of large-scale graph computations

    Gopal Pandurangan, Peter Robinson, and Michele Scquizzato. On the distributed complexity of large-scale graph computations. InProceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 405–414, 2018

    work page 2018

  45. [45]

    (Delta+1)coloringinthecongestedcliquemodel

    MeravParter. (Delta+1)coloringinthecongestedcliquemodel. In45th International Colloquium on Automata, Languages, and Programming (ICALP), volume 107, pages 160:1–160:14, 2018

    work page 2018

  46. [46]

    Randomized (Delta+1)-coloring in O(log* Delta) congested clique rounds

    Merav Parter and Hsin-Hao Su. Randomized (Delta+1)-coloring in O(log* Delta) congested clique rounds. In32nd International Symposium on Distributed Computing (DISC), volume 121, pages 39:1–39:18, 2018

    work page 2018

  47. [47]

    Reed and Gustave Solomon

    Irving S. Reed and Gustave Solomon. Polynomial codes over certain finite fields.Journal of the Society for Industrial and Applied Mathematics, 8(2):300–304, 1960

    work page 1960

  48. [48]

    Shvartsman

    Alex A. Shvartsman. Achieving optimal CRCW PRAM fault-tolerance.Information Processing Letters, 39(2):59–66, 1991. 25 Appendix A Additional Technical Lemmas Theorem A.1(Chernoff inequality for independent Bernoulli variables).LetX1, . . . , Xn be mutually independent 0–1 random variables withPr(Xi = 1) = pi. Let X =Pn i=1 Xi and set µ = E[X]. The following holds,

    work page 1991

  49. [49]

    for0< δ≤1,Pr(X≥(1 +δ)µ)≤e −µδ2/2

    work page

  50. [50]

    for0< δ <1,Pr(X≤(1−δ)µ)≤e −µδ2/2

    work page

  51. [51]

    for0< δ≤1,Pr(|X−µ| ≥δµ)≤2e −µδ2/3

    work page

  52. [52]

    Lemma A.2.Letx∈[0,1)andy≥0

    forR≥6µ,Pr(X≥R)≤2 −R For proof, see Theorems 4.4 and 4.5 in [41]. Lemma A.2.Letx∈[0,1)andy≥0. Then⌊x⌈y⌉⌋ ≤ ⌈xy⌉. Proof. Since y≥ ⌈y⌉ − 1, we havexy≥x (⌈y⌉ − 1). Taking ceiling on both sides, we get⌈xy⌉ ≥ ⌈x⌈y⌉ −x⌉. Letk=⌊x⌈y⌉⌋, andϵ=x⌈y⌉ −k. We notice thatϵ∈[0,1). We have that ⌈x⌈y⌉ −x⌉=⌈k+ϵ−x⌉ ≥k=⌊x⌈y⌉⌋, where the first equality follows from the definiti...

    work page