Another advantage of free choice (Extended Abstract)

• Protocol proceeds in rounds
• Every round we check if we have \((n+t)/2+1\) messages for the same value.
  • If we do, output it but continue
  • Else, if there is a value that \(t+1\) nodes support use that for future rounds
  • Else, set a random value
• If a node decides, all nodes will set the decided value in future, and therefore the remaining honest nodes will also eventually decide the same value
• The protocol guarantees termination if there is no initial consensus, since nodes will randomly choose values until they are at consensus.

This paper presents a consensus protocol.

• This paper points out that consensus is impossible for \(n \le 2t\).
• This paper also shows how a randomized algorithm can do better than the \(t+1\) round bound by Dolev and Reischuk.