← 研踪 PaperTrailarXiv:2606.13954 · v2
On the Solvability of Sound Distributed Verification under Byzantine Faults
首次提交 2026-06-12 06:33
版本更新 2026-11-10 03:38
雷达观测 2026-11-11 11:04
摘要
Modern distributed systems, ranging from distributed tracing platforms to blockchain oracle networks, frequently rely on processes holding partial observations to collectively certify a global execution state. Under Byzantine failures, a single malicious process withholding or fabricating partial states renders sound verification impossible, as genuine observations remain indistinguishable from fabricated assertions. To overcome this impossibility, we study input overlap x: the minimum number of processes that initially witness each element of a target execution I. We formalize this challenge as the x-reconstruction problem in asynchronous message-passing systems with up to t failures, where the goal is for all correct processes to recover I completely given an input overlap x. We establish tight matching upper and lower bounds for solvability: under crash failures, x-reconstruction is solvable if and only if x >= t + 1; under Byzantine failures, x-reconstruction is solvable if and only if x >= 2t + 1. Finally, we connect these structural bounds to semantic verification. For globally dependent safety properties (such as consensus, linearizability, k-set agreement, and leader election), sound verification under Byzantine faults requires a certificate of size c = t + 1 to guarantee at least one honest report. Consequently, sound distributed verification under Byzantine faults is achievable if and only if the input overlap satisfies x >= 2t + 1.
作者备注：28 pages, 3 figures, full version. Under review
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-10 03:38 · 最新观测版本
On the Solvability of Sound Distributed Verification under Byzantine Faults
Modern distributed systems, ranging from distributed tracing platforms to blockchain oracle networks, frequently rely on processes holding partial observations to collectively certify a global execution state. Under Byzantine failures, a single malicious process withholding or fabricating partial states renders sound verification impossible, as genuine observations remain indistinguishable from fabricated assertions. To overcome this impossibility, we study input overlap x: the minimum number of processes that initially witness each element of a target execution I. We formalize this challenge as the x-reconstruction problem in asynchronous message-passing systems with up to t failures, where the goal is for all correct processes to recover I completely given an input overlap x. We establish tight matching upper and lower bounds for solvability: under crash failures, x-reconstruction is solvable if and only if x >= t + 1; under Byzantine failures, x-reconstruction is solvable if and only if x >= 2t + 1. Finally, we connect these structural bounds to semantic verification. For globally dependent safety properties (such as consensus, linearizability, k-set agreement, and leader election), sound verification under Byzantine faults requires a certificate of size c = t + 1 to guarantee at least one honest report. Consequently, sound distributed verification under Byzantine faults is achievable if and only if the input overlap satisfies x >= 2t + 1.
查看此版本解读 →查看此版本原文 ↗