Research map / Learning theory and algorithms / Prediction and decision losses

Resilient Byzantine Agreement with Predictions

NeurIPS 2026 · Learning theory and algorithms › Prediction and decision losses · approach: Algorithms with explicit predictors · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Characterizes consistency-robustness-smoothness trade-offs for prediction-augmented Byzantine agreement (global and local predictions, with and without authentication), giving matching algorithms and impossibility results for resilience.

Problem

Byzantine agreement with predicted honest sets: how many faulty nodes can be tolerated when predictions of honest nodes may be wrong, and how resilience degrades as prediction error grows.

Approach

Use a predicted set P of trusted nodes, pad it deterministically to a minimum size set L tuned by trust parameter alpha, then run Phase King (non-authenticated) or Dolev-Strong (authenticated) inside L; matching indistinguishability arguments show these trade-offs are optimal and independent of the predictor. Smoothness is characterized via an error function counting mispredictions.

Key results

• Non-authenticated pred_ba is alpha-consistent for alpha in [1/3,1] and ((1-alpha)/2 - 1/n)-robust, matched by an impossibility showing robustness cannot exceed (1-alpha)/2.
• Authenticated variant is alpha-consistent for alpha in [1/2,1] and (1-alpha-1/n)-robust, matched by an impossibility at (1-alpha).
• Under local predictions, any alpha-consistent algorithm with alpha >= 1/2 is 0-robust.

Surprising findings

• With local predictions, achieving consistency of 1/2 forces robustness to zero, so local predictions give no robustness benefit in the authenticated case.

Limitations

• Focuses on resilience, not round or communication efficiency; runtime depends on underlying BA subroutine.
• Local-prediction case for non-authenticated consistency in [1/3,1/2) with nontrivial robustness remains open.
• Synchronous binary BA with a fixed known n and upper bound t only.

Experimental setup

Metrics: resilience consistency robustness smoothness

Baselines: prediction-free Byzantine agreement (n>3t non-authenticated) prediction-free authenticated BA (n>2t)

Builds on: Phase King Dolev-Strong Ben-David et al. BA with predictions Boyar et al. smoothness

Closest papers by meaning

• Byzantine Robustness and Partial Participation Can Be Achieved at Once: Just Clip Gradient Differences (NeurIPS 2024 · similarity 0.88)
• Weight for Robustness: A Comprehensive Approach towards Optimal Fault-Tolerant Asynchronous ML (NeurIPS 2024 · similarity 0.87)
• On the Tension between Byzantine Robustness and No-Attack Accuracy in Distributed Learning (ICML 2025 · similarity 0.86)
• Unified Breakdown Analysis for Byzantine Robust Gossip (ICML 2025 · similarity 0.85)
• Dynamic Byzantine-Robust Learning: Adapting to Switching Byzantine Workers (ICML 2024 · similarity 0.85)
• Rethinking the Reliability of Multi-agent System: A Perspective from Byzantine Fault Tolerance (AAAI 2026 · similarity 0.84)