Consensus in arbitrary failures

Consider a set of processes where the communication between processes is inconsistent.

a) bad forwarding of messages. b) communicating different information to different processes.

System's model

• Consider a primary P and n-1 backups B1, ..., Bn-1.

• A client sends v ∈ {T, F} a P

• Messages can get lost, but are detected.

• Messages cannot be corrupted without being detected.

• A message receptor can reliably detect who is the sender.

Requirements for a Byzantine Agreement (BA)

• BA1: All non-failing backups store the same value.

• BA2: If the primary is not failing then all non-failing backups store exactly what the primary sends.

Sufficient processes

3k is not sufficient

3k+1 is sufficient