Pith. sign in

REVIEW 1 major objections 5 minor 65 references

All-to-All Communication with Mobile Edge Adversary: Almost Linearly More Faults, For Free

T0 review · 1 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

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

Pith's one-line read The paper proves that any Congested Clique round can be simulated in O(1) rounds when faults are capped by per-node degree, tolerating n^{2-o(1)} corruptions against an adaptive adversary.

desk verdict Strong contribution with a real result, but the cover-free lemma at the heart of the routing theorem has a fixable proof bug that needs correction before publication. read the letter →

arxiv 2505.05735 v1 pith:CX33OCKN submitted 2025-05-09 cs.DS cs.DC

Orr Fischer , Merav Parter This is my paper · ORCID
classification cs.DScs.DC MSC 68W1568P3094B60
keywords CongestedCliqueByzantinemobileadversarybounded-degreeedgefaultsall-to-allcommunicationlocallydecodablecodescover-freefamiliessparserecoverysketchesdistributedcompilers
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

This paper asks whether the classical total-fault bound in the Congested Clique can be replaced by a per-node degree bound without slowing down computation. It answers yes: for a sufficiently small constant $\alpha$, a randomized compiler simulates any fault-free Congested Clique round in $O(1)$ rounds while a non-adaptive adversary corrupts up to $\alpha n$ edges at each node, and a second compiler does the same against an adaptive adversary with $\alpha=\exp(-\sqrt{\log n \log\log n})$ using only one bit of bandwidth. Because each round is simulated with constant overhead, any $r$-round algorithm becomes $O(r)$ rounds in the resilient model. The significance is that the model can now tolerate almost quadratically many edge failures per round, a regime impossible under total-count bounds.

What carries the argument

The load-bearing object is a deterministic resilient super-message routing scheme, the adversarial analogue of Lenzen routing. An instance has $k=O(1/\alpha)$: each node is the source and target of at most $k$ super-messages of $O(\alpha n)$ bits with known target sets, and the scheme delivers them in $O(1)$ rounds under an adaptive bounded-degree adversary. The scheme encodes each super-message with a constant-rate, constant-distance error-correcting code and assigns each codeword bit to a helper node set $A(u,j)$ drawn from a $(k-1,\delta)$-cover-free family, constructed deterministically via a local-lemma algorithm. The cover-free property guarantees that, for any target, only a small $\delta$-fraction of helper nodes are contested by other messages, while the degree bound guarantees at most $O(\alpha k)$ corrupted bits per codeword, keeping the received word within half the code distance. The adaptive compiler layers a locally decodable code and sparse-recovery sketches on top: the code's non-adaptive query pattern lets each node fetch the same $q$ positions for all of its sketches at once, and the sketches keep the data to recover at $O(\alpha n \log^2 n)$ bits, which is why the adaptive threshold is $1/(q \log^6 n)$.

What would settle it

Take $n$ large enough for Lemma 4.3's hypotheses, say $k=\lfloor n/\log n\rfloor$, $\delta=1/50$, and $H$ the $2kn$ input and output index sets, run the deterministic local-lemma construction, and check every tuple in $H$: if any set $A_{i_0}$ has fewer than $(1-\delta)|A_{i_0}|$ elements outside the union of any $k-1$ other sets from $H$, the routing lemma fails. A direct simulation alternative: run SMRoutingProtocol with an adaptive adversary that corrupts any chosen $\alpha n$ edges per node per round; a single target node that fails to decode its super-message, meaning the received error fraction reaches $\delta_C/2$, would refute the routing theorem's guarantees.

Watch

Extended reading notes

Core claim

The central claim is that AllToAllComm, the task of delivering for every ordered pair $(u,v)$ the message $m_{u,v}$, admits $O(1)$-round solutions under the $\alpha$-Byzantine-degree mobile adversary. The non-adaptive solution uses random permutations and error-correcting codes: each codeword bit travels over a secretly random edge, so although an $\alpha$-fraction of bits may be corrupted, the code distance leaves decoding correct with high probability. The adaptive solution is different, because the adversary sees the randomness: the nodes first exchange raw messages, use sparse-recovery sketches to compress the corrupted messages at each node, encode the sketches with a non-adaptive locally decodable code of sub-polynomial query complexity, and route the queried positions through the super-message routing scheme; each node decodes only its own sketch and recovers all corrections. The result is that simulation overhead stays $O(1)$ while the per-round fault budget rises from $\Theta(n)$ total edges to $n^{2-o(1)}$ total edges.

Load-bearing premise

Everything rests on the cover-free helper-set construction: for the parameters used, there must exist, computable in polynomial time, a family of helper sets in which any one helper set is almost entirely disjoint from the union of any $k-1$ other helper sets; if that construction fails, the routing theorem and every compiler in the paper fail with it.

Editorial extensions

If this is right

  • Any $r$-round Congested Clique algorithm can be simulated in $O(r)$ rounds against a non-adaptive adversary with constant $\alpha$ and bandwidth $B=\Theta(\log n)$, tolerating $\Theta(n^2)$ edge corruptions per round.
  • Against an adaptive adversary, $O(1)$-round simulation per round holds with $B=1$ and $\alpha=\exp(-\sqrt{\log n \log\log n})$, so the adversary may corrupt $n^{2-o(1)}$ edges per round.
  • A deterministic compiler simulates every round in $O(\log n)$ rounds with $B=1$ against a constant-fraction adaptive adversary, again tolerating $\Theta(n^2)$ corrupted edges per round.
  • A deterministic $O(1)$-round compiler works for $\alpha=\Theta(1/\sqrt{n})$, supporting $\Theta(n^{3/2})$ corrupted edges per round.
  • The super-message routing procedure itself is a deterministic $O(1)$-round primitive for any routing instance with $k=O(1/\alpha)$ sources and targets and $O(\alpha n)$-bit messages, giving bounded-degree adversarial settings a Lenzen-style routing tool.

Reading between the lines

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

  • The authors state Theorem 5.5 for any locally decodable code with query complexity $q$, so an improved LDC with $q=\mathrm{polylog}\, n$ would immediately raise the adaptive threshold to $1/\mathrm{polylog}\, n$; they do not speculate on such an improvement.
  • The cover-free helper-set construction is a routing-independent combinatorial gadget that could plausibly serve other tasks needing many witness sets protected from bounded-degree failures, such as fault-tolerant aggregation or verification.
  • The deterministic $\Theta(1)$-fault algorithm's hypercube bit-exchange pattern suggests a deterministic route to fault-tolerant sorting or permutation routing in the same model, though the paper does not develop that direction.
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

1 major / 5 minor

Summary. The paper studies the AllToAllComm problem in the Congested Clique under a mobile Byzantine edge adversary with bounded faulty degree, deg(F_i) <= alpha n. For the non-adaptive adversary it presents a randomized O(1)-round compiler with alpha = Theta(1) and bandwidth B = Theta(log n); for the adaptive adversary it presents a randomized O(1)-round compiler with alpha = exp(-sqrt(log n log log n)) and B = 1; and it presents deterministic compilers with O(log n) rounds for constant alpha and O(1) rounds for alpha = Theta(1/sqrt(n)). The key technical ingredient is a deterministic resilient super-message routing scheme (Theorem 4.1), built from Justesen codes, a new cover-free family construction, and, in the adaptive case, locally decodable codes and sparse recovery sketches.

Significance. Assuming correctness, the results are a clear advance over the previous mobile-edge-adversary compiler of Fischer and Parter [32], improving the per-round corruption budget from Theta~(n) to n^{2-o(1)} corrupted edges while reducing round overhead to O(1). The routing formulation is a natural adversarial analogue of Lenzen routing and is likely to be reused. The proof structure is modular, and the analysis of the two-round routing (Lemmas 4.5-4.7) is careful; the adaptive simulation bounds are coherent with the external LDC parameters. The paper does not assume its own conclusions: the fault thresholds come from Justesen codes and the KMRS LDC, and the protocols reduce to routing and coding primitives. The main reservation is a numerically incorrect Chernoff bound in the proof of the cover-free family lemma; it is repairable and does not affect the concrete parameter regimes used by the main theorems, but it must be fixed.

major comments (1)
  1. [Section 4.1 and Appendix A, Lemma 4.3] The Chernoff bound used to bound Pr(X > delta L) is not correct. Since X is a sum of L independent Bernoulli variables with mean mu <= delta L/2, the multiplicative Chernoff bound gives Pr(X > delta L) <= exp(-delta L/6), i.e., exp(-L/300) for delta = 1/50, not exp(-L/12). Consequently the requirements L >= (24+12c2) log N in Section 4.1 and L >= (36+24c2) log N in Appendix A are too small by a factor of about 25; to obtain pmax <= 1/(e N^2 |H|^2) one needs L = Omega((1+c2) log N / delta). Because L = floor(delta N/(4(r+1))), the proof as written does not establish Lemma 4.3 for the full stated range r+1 <= c1 delta N / log N, and hence does not establish Lemma 4.4 and Theorem 4.1 for k = Theta(N/log N) with the stated constants. The issue is repairable by choosing c1 small enough so that L >= C log N for the correct constant C, and the main applications use k = n^{o(1)}, k = O(1), or k = O(sqrt(n)), where L is much larger than any constant multiple of log n; but the proof must be corrected.
minor comments (5)
  1. [Appendix A, LLL construction] The random variable set is declared as Y = {Y_{i,j} | 0 <= i <= r, j in [L]}, but the cover-free family consists of m sets indexed by i in [m]. The bad events are defined for arbitrary i0 in [m], so the variables must be Y_{i,j} for all i in [m]; otherwise the LLL instance does not cover all sets in the family.
  2. [Section 5.1, Lemma 5.4] The Chernoff bound is applied to a single pair (u,v), but the correctness statement is for all pairs simultaneously. Add the standard union bound over n^2 pairs and state the required constant in the exponent.
  3. [Section 5.2, Lemma 5.9] The line 'b = O(nt/n) = O(t)' is confusing; since x = Theta(n), it should simply read b = O(t).
  4. [Section 1, Theorem 1.4] The phrase 'alpha = Omega(1)' conflicts with 'sufficiently small constant'; this should be alpha = Theta(1) with alpha smaller than the constant required by Theorem 4.1.
  5. [Table 1] The bandwidth entry for the deterministic Theta(1) row lists B in {1,...,polyn}; this is fine, but consider clarifying that the O(log n) round bound already holds for B = 1.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the alpha thresholds come from external code constructions and all load-bearing lemmas are either proven in-text or cited to independent prior work.

full rationale

I find no circular dependency in the claimed derivation chain. The central routing theorem (Theorem 4.1) is proved from a cover-free-family construction (Lemma 4.3) whose randomized proof is an independent probabilistic construction and whose derandomization is via the algorithmic Lovasz Local Lemma; neither the routing statement nor the AllToAllComm compilers are assumed in that construction. The fault thresholds alpha are obtained by substituting external, published parameters: the Justesen code's constant distance (Lemma 2.1), the KMRS LDC query complexity q = exp(sqrt(log n log log n)) (Lemma 2.2, reference [46]), and the external sparse-recovery sketch (Lemma 2.3). The authors' own prior work [32] supplies the sketch-correction idea, but Lemmas 2.4, 5.12 and B.1 reproduce the argument in full text, so the citation is not load-bearing. The deterministic alpha = Theta(1/sqrt(n)) compiler is explicitly credited to [2], an external paper, and is then re-proved via the paper's own routing scheme. The deterministic butterfly-based compiler and the non-adaptive randomized compiler are self-contained proofs built on the same routing lemma. Hence no prediction reduces to a fitted parameter, a renamed known result, or a self-citation chain. A numerical issue in the Chernoff tail bound inside Lemma 4.3 is a correctness concern, not a circularity concern, and the parameter regimes actually used by the final theorems are expected to survive a corrected proof.

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

The central claims rest on standard published coding tools and on the paper's own cover-free set construction (Lemma 4.3), proved in Appendix A via the deterministic LLL. No empirical parameters or new physical or conceptual entities are introduced; the alpha values are derived from the parameters of external constructions.

assumptions (6)
  • standard math Justesen codes exist with constant rate <= 1/200 and relative distance > 1/10, with polynomial-time encoding and decoding (Lemma 2.1, citing [42]).
    Used in the resilient routing scheme and non-adaptive compiler to correct corrupted bits.
  • standard math A non-adaptive LDC with constant rate, constant distance, query complexity q = exp(sqrt(log n log log n)) and poly(n) encoding/decoding exists (Lemma 2.2, citing [46]).
    Determines the adaptive adversary's alpha = Theta(1/(q log^6 n)) in Theorem 5.5.
  • standard math Sparse recovery sketches of size O(k log^2 |U|) support Add and Recover for k-sparse multisets with failure probability 1/poly(|U|) (Lemma 2.3, citing [21]).
    Used to compress the set of corrupted messages per receiver in Section 5.2.
  • standard math Harris's deterministic LLL algorithm finds a good assignment in polynomial time when epmax d^{1+epsilon} < 1 and a PEO exists (Lemma A.1, citing [38]).
    Used to derandomize the cover-free family construction in Appendix A.
  • standard math The Poisson-binomial cumulative distribution can be computed exactly in polynomial time (Lemma A.2, citing [61]).
    Provides the partial expectation oracle for the deterministic LLL instance.
  • domain assumption The Congested Clique model with bandwidth B, KT1 knowledge, synchronous rounds, and a mobile Byzantine adversary restricted to deg(F_i) <= alpha n per round (Section 2).
    This is the model under which all compilers are proved; it is inherited from [11] and the prior work [32].

how reviews work

0 comments
Cite this review

Pith. "Pith review of All-to-All Communication with Mobile Edge Adversary: Almost Linearly More Faults, For Free." pith.science (2026). https://pith.science/paper/CX33OCKN

@misc{pith2026250505735,
  author       = {Pith},
  title        = {Pith review of: All-to-All Communication with Mobile Edge Adversary: Almost Linearly More Faults, For Free},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CX33OCKN}},
  note         = {Machine review of arXiv:2505.05735}
}
abstract

Resilient computation in all-to-all-communication models has attracted tremendous attention over the years. Most of these works assume the classical faulty model which restricts the total number of corrupted edges (or vertices) by some integer fault parameter $f$. A recent work by [Bodwin, Haeupler and Parter, SODA 2024] introduced a stronger notion of fault-tolerance, in the context of graph sparsification, which restricts the degree of the failing edge set $F$, rather than its cardinality. For a subset of faulty edges $F$, the faulty-degree $\mathrm{deg}(F)$ is the largest number of faults in $F$ incident to any given node. In this work, we study the communication aspects of this faulty model which allows us to handle almost linearly more edge faults (possibly quadratic), with no extra cost. Our end results are general compilers that take any Congested Clique algorithm and simulate it, in a round by round manner, in the presence of a $\alpha$-Byzantine mobile adversary that controls a $\alpha$-fraction of the edges incident to each node in the fully connected network. For every round $i$, the mobile adversary is allowed to select a distinct set of corrupted edges $F_i$ under the restriction that $\mathrm{deg}(F_i)\leq \alpha n$. In the non-adaptive setting, the $F_i$ sets are selected at the beginning of the simulation, while in the adaptive setting, these edges can be chosen based on the entire history of the protocol up to round $i$. We show general compilers for the non-adaptive, adaptive, and deterministic settings. A key component of our algorithms is a new resilient routing scheme which may be of independent interest. Our approach is based on a combination of techniques, including error-correcting-code, locally decodable codes, cover-free families, and sparse recovery sketches.

Figures

Figures reproduced from arXiv: 2505.05735 by the authors.

Figure 1
Figure 1. Node vi wishes to decode all bits of Sk(Pj , {vi}) from Skℓi (Pj ) (marked as the blue cells). Crucially, these indices are in the same positions Pj . Since the LDC is non-adaptive, for a node vi to be able to decode all blue positions simultaneously, its sufficient to learn the codeword bits given to nodes {vr}r∈N(vi) (marked as the green cells - due to non-adaptivity of LDCDecode, they are the same positions for a… view at source ↗
Figure 2
Figure 2. An illustration of the algorithm of Theorem [PITH_FULL_IMAGE:figures/full_fig_p029_2.png] view at source ↗
Figure 3
Figure 3. An illustration of the algorithm of Theorem [PITH_FULL_IMAGE:figures/full_fig_p032_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

65 extracted references · 64 canonical work pages

  1. [32]

    Distributed CONGEST algorithms against mobile adversaries

    Orr Fischer and Merav Parter. Distributed CONGEST algorithms against mobile adversaries. In Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing (PODC) , pages 262–273. ACM, 2023

    work page 2023

  2. [1]

    Asymptotically optimal two-round perfectly secure message transmission

    Saurabh Agarwal, Ronald Cramer, and Robbert de Haan. Asymptotically optimal two-round perfectly secure message transmission. In Advances in Cryptology (CRYPTO) , volume 4117, pages 394–408, 2006

    work page 2006

  3. [2]

    Reliable communication over highly connected noisy networks

    Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, and Bernhard Haeupler. Reliable communication over highly connected noisy networks. Distributed Comput. , 32(6):505–515, 2019

    work page 2019

  4. [3]

    Byzantine connectivity testing in the congested clique

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

    work page 2022

  5. [4]

    Constant Degree Networks for Almost-Everywhere Reliable Transmission

    Mitali Bafna and Dor Minzer. Constant degree networks for almost-everywhere reliable trans- mission. arXiv preprint arXiv:2501.00337 , 2024

    work page Pith review arXiv 2024

  6. [5]

    Anindo Bagchi and Louis S. Hakimi. Information dissemination in distributed systems with faulty units. IEEE Transactions on Computers , 43(6):698–710, 1994

    work page 1994

  7. [6]

    Cryptographic protocols provably secure against dynamic adversaries

    Donald Beaver and Stuart Haber. Cryptographic protocols provably secure against dynamic adversaries. In Rainer A. Rueppel, editor, Workshop on the Theory and Application of Cryp- tographic Techniques (EUROCRYPT), volume 658, pages 307–323. Springer, 1992

    work page 1992

  8. [7]

    Randomness-efficient oblivious sampling

    Mihir Bellare and John Rompel. Randomness-efficient oblivious sampling. In 35th Annual Symposium on Foundations of Computer Science (FOCS) , pages 276–287. IEEE Computer Society, 1994

    work page 1994

Show all 65 references
  1. [8]

    Piotr Berman and Juan A. Garay. Cloture votes: n/4-resilient distributed consensus in t+1 rounds. Math. Syst. Theory , 26(1):3–19, 1993. 33

    1993

  2. [9]

    Garay, and Kenneth J

    Piotr Berman, Juan A. Garay, and Kenneth J. Perry. Towards optimal distributed consensus (extended abstract). In 30th Annual Symposium on Foundations of Computer Science (FOCS), pages 410–415. IEEE Computer Society, 1989

    1989

  3. [10]

    Douglas Blough and Andrzej M. Pelc. Optimal communication in networks with randomly distributed byzantine faults. Networks, 23(8):691–701, 1993

    1993

  4. [11]

    Fault-tolerant spanners against bounded- degree edge failures: Linearly more faults, almost for free

    Greg Bodwin, Bernhard Haeupler, and Merav Parter. Fault-tolerant spanners against bounded- degree edge failures: Linearly more faults, almost for free. In Proceedings of the 2024 ACM- SIAM Symposium on Discrete Algorithms (SODA) , pages 2609–2642, 2024

    2024

  5. [12]

    Tight bound on mobile byzantine agreement

    Fran¸ cois Bonnet, Xavier D´ efago, Thanh Dang Nguyen, and Maria Potop-Butucaru. Tight bound on mobile byzantine agreement. Theor. Comput. Sci. , 609:361–373, 2016

    2016

  6. [13]

    Asynchronous byzantine agreement protocols

    Gabriel Bracha. Asynchronous byzantine agreement protocols. Information and Computation, 75(2):130–143, 1987

    1987

  7. [14]

    Asynchronous consensus and broadcast protocols

    Gabriel Bracha and Sam Toueg. Asynchronous consensus and broadcast protocols. J. ACM, 32(4):824–840, 1985

    1985

  8. [15]

    Fast distributed algorithms for girth, cycles and small subgraphs

    Keren Censor-Hillel, Orr Fischer, Tzlil Gonen, Fran¸ cois Le Gall, Dean Leitersdorf, and Rotem Oshman. Fast distributed algorithms for girth, cycles and small subgraphs. In 34th Interna- tional Symposium on Distributed Computing (DISC) , volume 179 of LIPIcs, pages 33:1–33:17, 2020

    2020

  9. [16]

    On fast and robust information spreading in the vertex-congest model

    Keren Censor-Hillel and Tariq Toukan. On fast and robust information spreading in the vertex-congest model. Theoretical Computer Science, 2017

    2017

  10. [17]

    Almost-everywhere secure computa- tion with edge corruptions

    Nishanth Chandran, Juan Garay, and Rafail Ostrovsky. Almost-everywhere secure computa- tion with edge corruptions. Journal of Cryptology , 28(4):745–768, 2015

    2015

  11. [18]

    Recognizing hereditary prop- erties in the presence of byzantine nodes

    David Cifuentes-N´ u˜ nez, Pedro Montealegre, and Ivan Rapaport. Recognizing hereditary prop- erties in the presence of byzantine nodes. CoRR, abs/2312.07747, 2023

    2023

  12. [19]

    Coan and Jennifer L

    Brian A. Coan and Jennifer L. Welch. Modular construction of a byzantine agreement protocol with optimal message bit complexity. Inf. Comput., 97(1):61–85, 1992

    1992

  13. [20]

    On the round complexity of randomized byzantine agreement

    Ran Cohen, Iftach Haitner, Nikolaos Makriyannis, Matan Orland, and Alex Samorodnitsky. On the round complexity of randomized byzantine agreement. In 33rd International Symposium on Distributed Computing (DISC) , pages 12:1–12:17, 2019

    2019

  14. [21]

    A unifying framework for l0-sampling algorithms

    Graham Cormode and Donatella Firmani. A unifying framework for l0-sampling algorithms. Distributed Parallel Databases, 32(3):315–335, 2014

    2014

  15. [22]

    L p samplers and their applications: A survey

    Graham Cormode and Hossein Jowhari. L p samplers and their applications: A survey. ACM Computing Surveys (CSUR) , 52(1):1–31, 2019

    2019

  16. [23]

    Reliable gossip schemes with random link failures

    Krzysztof Diks and Andrezej Pelc. Reliable gossip schemes with random link failures. In Proc. 28th Ann. Allerton Conf. on Comm. Control and Comp , pages 978–987, 1990

    1990

  17. [24]

    The byzantine generals strike again

    Danny Dolev. The byzantine generals strike again. J. Algorithms, 3(1):14–30, 1982. 34

    1982

  18. [25]

    Perfectly secure message trans- mission

    Danny Dolev, Cynthia Dwork, Orli Waarts, and Moti Yung. Perfectly secure message trans- mission. J. ACM, 40(1):17–47, 1993

    1993

  19. [26]

    Fischer, Robert J

    Danny Dolev, Michael J. Fischer, Robert J. Fowler, Nancy A. Lynch, and H. Raymond Strong. An efficient algorithm for byzantine agreement without authentication. Information and Con- trol, 52(3):257–274, 1982

    1982

  20. [27]

    Danny Dolev and Ezra N. Hoch. Constant-space localized byzantine consensus. In Distributed Computing, 22nd International Symposium (DISC) , pages 167–181, 2008

    2008

  21. [28]

    Fault tolerance in networks of bounded degree

    Cynthia Dwork, David Peleg, Nicholas Pippenger, and Eli Upfal. Fault tolerance in networks of bounded degree. SIAM J. Comput. , 17(5):975–988, 1988

    1988

  22. [29]

    Problems and results on 3-chromatic hypergraphs and some related questions

    Paul Erdos and Lov´ asz L´ aszl´ o. Problems and results on 3-chromatic hypergraphs and some related questions. Coll Math Soc J Bolyai , 10, 01 1974

    1974

  23. [30]

    An optimal probabilistic protocol for synchronous byzantine agreement

    Pesech Feldman and Silvio Micali. An optimal probabilistic protocol for synchronous byzantine agreement. SIAM J. Comput. , 26(4):873–933, 1997

    1997

  24. [31]

    The consensus problem in unreliable distributed systems (a brief survey)

    Michael J Fischer. The consensus problem in unreliable distributed systems (a brief survey). In International Conference on Fundamentals of Computation Theory , pages 127–140. Springer, 1983

    1983

  25. [33]

    From partial consistency to global broadcast

    Mattias Fitzi and Ueli Maurer. From partial consistency to global broadcast. In Proceedings of the thirty-second annual ACM symposium on Theory of computing , pages 494–503, 2000

    2000

  26. [34]

    Juan A. Garay. Reaching (and maintaining) agreement in the presence of mobile faults (ex- tended abstract). In Distributed Algorithms, 8th International Workshop (WDAG) , volume 857, pages 253–264, 1994

    1994

  27. [35]

    Garay and Yoram Moses

    Juan A. Garay and Yoram Moses. Fully polynomial byzantine agreement for n > 3t processors in t + 1 rounds. SIAM J. Comput. , 27(1):247–290, 1998

    1998

  28. [36]

    Efficient and explicit coding for interactive com- munication

    Ran Gelles, Ankur Moitra, and Amit Sahai. Efficient and explicit coding for interactive com- munication. In IEEE 52nd Annual Symposium on Foundations of Computer Science, (FOCS) , pages 768–777, 2011

    2011

  29. [37]

    Efficient coding for interactive communication

    Ran Gelles, Ankur Moitra, and Amit Sahai. Efficient coding for interactive communication. IEEE Trans. Inf. Theory, 60(3):1899–1913, 2014

    1913

  30. [38]

    David G. Harris. Deterministic algorithms for the lov´ asz local lemma: Simpler, more general, and more parallel. Random Struct. Algorithms, 63(3):716–752, 2023

    2023

  31. [39]

    Hoza and Leonard J

    William M. Hoza and Leonard J. Schulman. The adversarial noise threshold for distributed protocols. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 240–258. SIAM, 2016. 35

    2016

  32. [40]

    Simple and efficient reliable broadcast in the presence of byzantine processes

    Damien Imbs and Michel Raynal. Simple and efficient reliable broadcast in the presence of byzantine processes. arXiv preprint arXiv:1510.06882 , 2015

    2015 arXiv

  33. [41]

    Efficient constructions for almost-everywhere secure computation

    Siddhartha Jayanti, Srinivasan Raghuraman, and Nikhil Vyas. Efficient constructions for almost-everywhere secure computation. In Advances in Cryptology - EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, volume 12...

    2020

  34. [42]

    Class of constructive asymptotically good algebraic codes

    Jørn Justesen. Class of constructive asymptotically good algebraic codes. IEEE Trans. Inf. Theory, 18(5):652–656, 1972

    1972

  35. [43]

    On expected constant-round protocols for byzantine agreement

    Jonathan Katz and Chiu-Yuen Koo. On expected constant-round protocols for byzantine agreement. In Annual International Cryptology Conference , pages 445–462. Springer, 2006

    2006

  36. [44]

    Muhammad Samir Khan, Syed Shalan Naqvi, and Nitin H. Vaidya. Exact byzantine consensus on undirected graphs under local broadcast model. InProceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC) , pages 327–336, 2019

    2019

  37. [45]

    Broadcast in radio networks tolerating byzantine adversarial behavior

    Chiu-Yuen Koo. Broadcast in radio networks tolerating byzantine adversarial behavior. In Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Com- puting (PODC), pages 275–282. ACM, 2004

    2004

  38. [46]

    High-rate locally cor- rectable and locally testable codes with sub-polynomial query complexity

    Swastik Kopparty, Or Meir, Noga Ron-Zewi, and Shubhangi Saraf. High-rate locally cor- rectable and locally testable codes with sub-polynomial query complexity. J. ACM, 64(2):11:1– 11:42, 2017

    2017

  39. [47]

    Coding constructions for blacklisting problems without computational assumptions

    Ravi Kumar, Sridhar Rajagopalan, and Amit Sahai. Coding constructions for blacklisting problems without computational assumptions. In Advances in Cryptology (CRYPTO), volume 1666, pages 609–623, 1999

    1999

  40. [48]

    Truly efficient 2-round perfectly secure message trans- mission scheme

    Kaoru Kurosawa and Kazuhiro Suzuki. Truly efficient 2-round perfectly secure message trans- mission scheme. IEEE Trans. Inf. Theory, 55(11):5223–5232, 2009

    2009

  41. [49]

    Optimal deterministic routing and sorting on the congested clique

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

    2013

  42. [50]

    Locality in distributed graph algorithms

    Nathan Linial. Locality in distributed graph algorithms. SIAM J. Comput. , 21(1):193–201, 1992

    1992

  43. [51]

    On byzantine broadcast in loosely connected net- works

    Alexandre Maurer and S´ ebastien Tixeuil. On byzantine broadcast in loosely connected net- works. In Distributed Computing - 26th International Symposium (DISC) , pages 253–266, 2012

    2012

  44. [52]

    How to withstand mobile virus attacks (extended abstract)

    Rafail Ostrovsky and Moti Yung. How to withstand mobile virus attacks (extended abstract). In Luigi Logrippo, editor, Proceedings of the Tenth Annual ACM Symposium on Principles of Distributed Computing, Montreal, Quebec, Canada, August 19-21, 1991 , pages 51–59. ACM, 1991

    1991

  45. [53]

    Reaching agreement in the presence of faults

    Marshall Pease, Robert Shostak, and Leslie Lamport. Reaching agreement in the presence of faults. Journal of the ACM (JACM) , 27(2):228–234, 1980. 36

    1980

  46. [54]

    Reliable communication in networks with byzantine link failures

    Andrzej Pelc. Reliable communication in networks with byzantine link failures. Networks, 22(5):441–459, 1992

    1992

  47. [55]

    Broadcasting with locally bounded byzantine faults

    Andrzej Pelc and David Peleg. Broadcasting with locally bounded byzantine faults. Inf. Process. Lett., 93(3):109–115, 2005

    2005

  48. [56]

    Schulman

    Sridhar Rajagopalan and Leonard J. Schulman. A coding theorem for distributed computation. In Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing (STOC), pages 790–799, 1994

    1994

  49. [57]

    Romashchenko

    Andrei E. Romashchenko. Reliable computations based on locally decodable codes. In Bruno Durand and Wolfgang Thomas, editors, 23rd Annual Symposium on Theoretical Aspects of Computer Science (STACS), volume 3884, pages 537–548, 2006

    2006

  50. [58]

    Time is not a healer

    Nicola Santoro and Peter Widmayer. Time is not a healer. InAnnual Symposium on Theoretical Aspects of Computer Science , pages 304–313. Springer, 1989

    1989

  51. [59]

    Distributed function evaluation in the presence of trans- mission faults

    Nicola Santoro and Peter Widmayer. Distributed function evaluation in the presence of trans- mission faults. In Algorithms, International Symposium (SIGAL) , pages 358–367, 1990

    1990

  52. [60]

    Schulman

    Leonard J. Schulman. Communication on noisy channels: A coding theorem for computation. In 33rd Annual Symposium on Foundations of Computer Science (FOCS) , pages 724–733. IEEE Computer Society, 1992

    1992

  53. [61]

    B. K. Shah. On the distribution of the sum of independent integer valued random variables. The American Statistician, 27(3):123–127, 1973

    1973

  54. [62]

    Fast distributed agreement

    Sam Toueg, Kenneth Perry, and TK Srikanth. Fast distributed agreement. SIAM Journal on Computing, 16(3):445–457, 1987

    1987

  55. [63]

    Tolerating a linear number of faults in networks of bounded degree

    Eli Upfal. Tolerating a linear number of faults in networks of bounded degree. Inf. Comput., 115(2):312–320, 1994

    1994

  56. [64]

    Salil P. Vadhan. Pseudorandomness. Now Publishers Inc., 2012

    2012

  57. [65]

    The ”mobile adversary” paradigm in distributed computation and systems

    Moti Yung. The ”mobile adversary” paradigm in distributed computation and systems. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC) , pages 171–172. ACM, 2015. A Missing Proofs for Section 4 Derandomization of (r,δ )-Cover Free Sets (Proof...

    2015

Pith tools

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