In the context of Byzantine consensus problems such as Byzantine broadcast (BB) and Byzantine agreement (BA), the good-case setting aims to study the minimal possible latency of a BB or BA protocol under certain favorable conditions, namely the designated leader being correct (for BB), or all correct parties having the same input value (for BA). We provide a full characterization of the feasibility and impossibility of good-case latency, for both BA and BB, in the synchronous sleepy model. Surprisingly to us, we find irrational resilience thresholds emerging: 2-round good-case BB is possible if and only if at all times, at least \(\frac{1}{\varphi } \approx 0.618\) fraction of the active parties are correct, where \(\varphi = \frac{1+\sqrt{5}}{2} \approx 1.618\) is the golden ratio; 1-round good-case BA is possible if and only if at least \(\frac{1}{\sqrt{2}} \approx 0.707\) fraction of the active parties are correct.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Optimal Good-Case Latency for Sleepy Consensus

  • Yuval Efron,
  • Joachim Neu,
  • Ling Ren,
  • Ertem Nusret Tas

摘要

In the context of Byzantine consensus problems such as Byzantine broadcast (BB) and Byzantine agreement (BA), the good-case setting aims to study the minimal possible latency of a BB or BA protocol under certain favorable conditions, namely the designated leader being correct (for BB), or all correct parties having the same input value (for BA). We provide a full characterization of the feasibility and impossibility of good-case latency, for both BA and BB, in the synchronous sleepy model. Surprisingly to us, we find irrational resilience thresholds emerging: 2-round good-case BB is possible if and only if at all times, at least \(\frac{1}{\varphi } \approx 0.618\) fraction of the active parties are correct, where \(\varphi = \frac{1+\sqrt{5}}{2} \approx 1.618\) is the golden ratio; 1-round good-case BA is possible if and only if at least \(\frac{1}{\sqrt{2}} \approx 0.707\) fraction of the active parties are correct.