Models

Model = Assumptions Assumptions -> Timing + Failures

Timing assumptions

Processes Bounds on time to make a computation step Network Bounds on time to transmit a message between a sender and a receiver Clocks Lower and upper bounds on clock drift rate

Failure assumptions

Processes What kind of failure a process can exhibit? Crashes and stops Behaves arbitrary (Byzantine) Network Can a network channel drop messages? Can certain channels temporarily disconnect? (partitions)

Asynchronous system model

• No bound on time to deliver a message
• No bound on time to compute
• Clocks are not synchronized

Consensus is non-solvable in asynchronous systems

Synchronous system

• Known bound on time to deliver a message (latency)
• Known bound on time to compute
• Known lower and upper bounds in physical clock drift rate

Consensus is solvable in synchronous system with up to N-1 crashes

Partially synchronous system

• Initially system is asynchronous
• Eventually the system becomes synchronous (for a while)

Consensus solvable in any partially synchronous system with up to N/2 crashes

Byzantine faults

Some processes might behave arbitrarily

• Sending wrong information
• Omit messages…

Byzantine algorithms that tolerate such faults

• Only tolerate up to 1/3 Byzantine processes
• Non-Byzantine algorithms can often tolerate 1/2 nodes in the asynchronous model