论文标题
拜占庭协议的基本限制
Fundamental Limits of Byzantine Agreement
论文作者
论文摘要
拜占庭协议（BA）是一个分布式共识问题，$ n $处理器希望就$ \ ell $ bit的消息或价值达成协议，但是处理器的最多$ t $是不诚实的或错误的。尽管存在不诚实的处理器，但该BA问题的挑战在于达成协议，这些处理器可能任意偏离设计的协议。 BA协议的质量主要是通过使用以下三个参数来衡量的：处理器的数量$ n $作为$ t $允许的函数（弹性）；回合数（圆形复杂性，用$ r $表示）；以及通信位的总数（通信复杂性，用$ b $表示）。对于任何无错误的BA协议，这三个参数上的已知下限是$ n \ geq 3t+1 $，$ r \ geq t+1 $和$ b \geqΩ（\ \ max \ {n \ ell，nt \}）$，在所有执行所有执行中都正确的协议是正确的。在这项工作中，通过使用编码理论以及图理论和线性代数，我们设计了一个编码的BA协议（称为酷），该协议在$ \ ell $ bit的消息上达成共识，具有最佳的弹性，最佳的最佳圆形复杂性，并在$ \ ell feq ell \ ell \ ell \ geq flog \ geq t $ t $ t $ t $ t $，simultaine simultane simultane simultane simultane simultane时。提出的冷却是一种不依赖加密技术的无错误和确定性的BA协议。它可以防止计算无限的对手。通过提出的凉爽和已知的下限可实现的性能，我们将最佳通信复杂性指数表征为\ [β^*（α，δ）= \ max \ {1+{1+a，1+δ\} \]，用于$β= \ lim_ { \ infty} \ log \ ell/\ log n $和$δ= \ lim_ {n \ to \ infty}} \ log t/\ log n $。这项工作表明，编码是实现拜占庭协议及其变体的基本限制的有效方法。
Byzantine agreement (BA) is a distributed consensus problem where $n$ processors want to reach agreement on an $\ell$-bit message or value, but up to $t$ of the processors are dishonest or faulty. The challenge of this BA problem lies in achieving agreement despite the presence of dishonest processors who may arbitrarily deviate from the designed protocol. The quality of a BA protocol is measured primarily by using the following three parameters: the number of processors $n$ as a function of $t$ allowed (resilience); the number of rounds (round complexity, denoted by $r$); and the total number of communication bits (communication complexity, denoted by $b$). For any error-free BA protocol, the known lower bounds on those three parameters are $n\geq 3t+1$, $r\geq t+1$ and $b\geqΩ(\max\{n\ell, nt\})$, respectively, where a protocol that is guaranteed to be correct in all executions is said to be error free. In this work by using coding theory, together with graph theory and linear algebra, we design a coded BA protocol (termed as COOL) that achieves consensus on an $\ell$-bit message with optimal resilience, asymptotically optimal round complexity, and asymptotically optimal communication complexity when $\ell \geq t\log t$, simultaneously. The proposed COOL is an error-free and deterministic BA protocol that does not rely on cryptographic technique. It is secure against computationally unbounded adversary. With the achievable performance by the proposed COOL and the known lower bounds, we characterize the optimal communication complexity exponent as \[β^*(α,δ)=\max\{1+α,1+δ\}\] for $β= \lim_{n\to\infty}\log b/\log n$, $α=\lim_{n \to \infty} \log \ell/\log n$ and $δ=\lim_{n\to\infty} \log t/\log n$. This work reveals that coding is an effective approach for achieving the fundamental limits of Byzantine agreement and its variants.
