利用预测器提升拜占庭容错系统的鲁棒性,准确度越高容错越多。
Resilient Byzantine Agreement with Predictions
- 基于预测器准确性动态调整容错能力,分一致性与鲁棒性两种场景
- 预测正确时可容忍α·n个故障节点,错误时最多容忍(1−α)/2·n−1个(非认证)
- 预测误差每增加一个,容错能力线性下降,认证场景更稳定
本文研究节点拥有预测器以标记可疑故障(拜占庭)行为的拜占庭协议问题。聚焦算法韧性——即算法能容忍的最大故障节点数,并给出依赖预测器准确性的算法与不可能性结果。主要成果一:在非认证与认证设置下,完整刻画了一致性-鲁棒性权衡:对于n个节点和参数α∈[0,1],当预测器正确时可容忍α·n个故障节点(一致性),当预测器任意错误时可容忍((1−α)/2)·n−1个(非认证)或(1−α)·n−1个(认证);该界限严格紧致,再多一个故障节点即不可行。成果二:刻画了平滑性——韧性随预测准确率下降的速率。只要错误预测数在常数倍n以内,韧性线性下降:非认证场景每多一个错误预测损失1单位韧性,认证场景因需两个错误预测才损失1单位,故降幅减半。
原文摘要 · Abstract (English)
This paper studies the Byzantine Agreement problem where the nodes have access to a predictor that flags nodes for suspicion of faulty (Byzantine) behavior. We focus on algorithmic resilience -- the maximum number of faulty nodes an algorithm can tolerate -- and present algorithms and impossibility results whose resilience depend on the accuracy of the predictor. As our first main result, we bring a complete characterization of the consistency--robustness trade-offs in both the non-authenticated and authenticated settings: for $n$ nodes and a parameter $α\in [0, 1]$, we present algorithms that tolerate up to $α\cdot n$ faulty nodes when the predictor is correct (consistency), and up to $\frac{1-α}{2} \cdot n - 1$ faulty nodes when the predictor is arbitrarily wrong (robustness); in the authenticated setting the robustness bound improves to $(1-α) \cdot n - 1$. These trade-offs are exactly tight as we show that one additional faulty node renders the problem impossible. Our second main result characterizes smoothness: the rate at which resilience degrades as the predictor becomes less accurate. We show that resilience linearly decreases in the number of wrong predictions as long as that number stays within a constant fraction of $n$. Concretely, in the non-authenticated setting each additional wrong prediction loses one unit of resilience, whereas in the authenticated setting the decline is halved since two wrong predictions are needed to lose one unit of resilience.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。