论文标题
部分同步模型中状态机复制的二次最差消息复杂性
Quadratic worst-case message complexity for State Machine Replication in the partial synchrony model
论文作者
论文摘要
我们考虑了与部分同步模型中拜占庭失败有关的状态机器复制协议的消息复杂性。 Dolev和Reischuk的结果为消息复杂性提供了二次下限，但是尚不清楚该下限是否紧密，最有效的已知协议给出了最差的消息复杂性$ O（n^3）$。我们描述了一种符合Dolev和Reischuk二次下限的协议，同时还满足其他理想的特性。要指定这些属性，假设我们有$ n $ epplicas，其中$ f $显示了byzantine故障（带有$ n \ geq 3f+1 $）。假设$δ$是消息延迟的上限，即，如果以时间$ t $发送消息，则会通过时间$ \ text {max} \ {t，gst \} +δ$接收到它。我们描述了一个确定性协议，该协议同时实现了$ O（n^2）$糟糕的消息复杂性，乐观的响应能力，$ o（fδ）$（$ o（fδ）$在$ gst $和$ o（n）$平均消息复杂性之后首次确认。
We consider the message complexity of State Machine Replication protocols dealing with Byzantine failures in the partial synchrony model. A result of Dolev and Reischuk gives a quadratic lower bound for the message complexity, but it was unknown whether this lower bound is tight, with the most efficient known protocols giving worst-case message complexity $O(n^3)$. We describe a protocol which meets Dolev and Reischuk's quadratic lower bound, while also satisfying other desirable properties. To specify these properties, suppose that we have $n$ replicas, $f$ of which display Byzantine faults (with $n\geq 3f+1$). Suppose that $Δ$ is an upper bound on message delay, i.e. if a message is sent at time $t$, then it is received by time $ \text{max} \{ t, GST \} +Δ$. We describe a deterministic protocol that simultaneously achieves $O(n^2)$ worst-case message complexity, optimistic responsiveness, $O(fΔ)$ time to first confirmation after $GST$ and $O(n)$ mean message complexity.
