Byzantine Failures

• Byzantine Agreement (BA) problem.
• Impossibility result: not possible to solve BA with $n=3, f=1$ (three process with one faulty)
• In general, cannot solve the problem if $n\leq 3f$

EIG for Byzantine failure (to agree on 1 bit)

• Assume $n>3f$
  • Same EIG tree as in the stopping case
    • same rule to decorate the tree, $val(x)$ is the decoration of the node with label $x$
    • if no msg is received, set $val(x)=v_0$
  • New decision rule:
    • redecorate the tree with $newval(x)$
      • proceed bottom-up
      • leaf: $newval(x)=val(x)$
      • nonleaf: $newval(x)=$ strict majority of children, $v_0$ otherwise
    • decision: $d_i=newval(\lambda)$ (newval at root)

Illusion of EIG for Byzantine failure. Process 3 could tell others either 1 or 0. "Lies" means that Process 3 gives wrong value to others.

Illusion of EIG for Byzantine failure.

• Complexity
  • $f+1$ rounds
  • communication $O(n^{f+1})$ bits
  • requirement: $n>3f$
• General BA using binary BA
  • to agree on $\mathcal{l}$ bits, we could
    • run binary BA $l$ times, in total $l(f+1)$ rounds
    • run TurnpinCoan algorithm with $f+3$ rounds
    • recent interests on large $l$ (agree on distributed transactions, e.g., bitcoin