Leader Election with Poly-Logarithmic Communication Per Party

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<(13-ε)n (for ε=o(1)) in the full-information setting such that every party only sends 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.

Duke Scholars

Author Kartik Nayak Computer Science