BenOr - Randomized CFT Consensus

Notes

  • Asynchronous network
  • Solves binary consensus
  • \(n>2t\) for \(t\) crash faults
  • Protocol
    1. Set \(r \leftarrow 1\)
    2. Wait till \(n-t\) messages of type \((1,r,*)\) are received. If more than \(n/2\) messages have the same value \(v\), then send the message \((2,r,v,D)\) to all the processes. Else, send the message \((2,r,?)\) to all processes.
    3. Wait till \(n-t\) messages of type \((2,r,*)\) to arrive.
      1. If there is one D-message \((2,r,v,D)\) then set \(v_i \leftarrow v\).
      2. If there are more than \(t\) D-messages, then output \(v\).
      3. Else, set \(v_i \in \{0,1\}\) randomly with probability 1/2.
    4. Set \(r\leftarrow r+1\) and go to step 1.
  • Round complexity: Expected \(O(2^{2n})\) for \(n=2t+1\). The \(2n\) is because we need the randomness of \(n\) servers to all output the same value in two rounds to terminate.