The leader election problem requires a set of n parties, out of which up to t can be Byzantine, to elect a leader uniformly at random such that no two parties disagree on the elected leader and an honest leader is elected with constant probability. The Scalable Leader Election protocol published in SODA’2006 is an important breakthrough in solving this problem efficiently for all but o(1) of the parties. They achieve a protocol for \(t < (\frac{1}{3} - \varepsilon )n\) (for \(\varepsilon = o(1)\) ) in the full-information setting such that every party only sends \(\text {polylog}(n)\) bits. In this paper, we revisit their work and show that there are subtleties in the protocol that are not dealt with in the analysis. In particular, two mechanisms related to “silencing” parties and dealing with “bad nodes” are at odds with each other, which is why the existing analysis is insufficient. We present these concerns in detail and subsequently present a modification to their protocol with a corresponding analysis to solve leader election with the desired metrics.

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

Leader Election with Poly-Logarithmic Communication Per Party

  • Amey Bhangale,
  • Chen-Da Liu-Zhang,
  • Julian Loss,
  • Kartik Nayak,
  • Sravya Yandamuri

摘要

The leader election problem requires a set of n parties, out of which up to t can be Byzantine, to elect a leader uniformly at random such that no two parties disagree on the elected leader and an honest leader is elected with constant probability. The Scalable Leader Election protocol published in SODA’2006 is an important breakthrough in solving this problem efficiently for all but o(1) of the parties. They achieve a protocol for \(t < (\frac{1}{3} - \varepsilon )n\) (for \(\varepsilon = o(1)\) ) in the full-information setting such that every party only sends \(\text {polylog}(n)\) bits. In this paper, we revisit their work and show that there are subtleties in the protocol that are not dealt with in the analysis. In particular, two mechanisms related to “silencing” parties and dealing with “bad nodes” are at odds with each other, which is why the existing analysis is insufficient. We present these concerns in detail and subsequently present a modification to their protocol with a corresponding analysis to solve leader election with the desired metrics.