On the Solvability of Sound Distributed Verification under Byzantine Faults
Gilde Valeria Rodríguez, Borzoo Bonakdarpour, Armando Castañeda, Sergio Rajsbaum
原文摘要
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.
cs.DC