• N processes communicating by message passing
• Synchronous or asynchronous system
• Communication is reliable
• Process failures
• Crash failures
• Byzantine failures (e.g. processes can lie)
• Algorithm must tolerant certain (specified) failures
• Faulty processes: exhibit some specified typesof fault; all other processes are correct
• Assume messages are not digitally signed

• Termination: Eventually each correct process sets its decision value
• Agreement: all correct processes must have decided on the same value
• Integrity: if all correct processes propose the same value, then any correct process that has decided must have chosen that value
• Variations of integrity requirement depending on the application, e.g. agreed value was proposed by some process

• Processes reliably multicast proposed value to othes
• Wait until N values are collected (including own)
• Decide through majority function (Special value ± if none; can also use max/min instead of majority)
• Termination and integrity guaranteed by use of reliable multicast
• Majority vote ensures agreement
• Assumes no failures (Crash failures or arbitrary failures)

Consensus and Reliable Totally Ordered (RTO) Multicast

• Possible to reduce Consesnsus to RTO-mutlicast
• Collect all processes in group g
• Each process P_i RTO-multicasts its value v_i to g
• Each process P_i chooses d_i as the first value it RTO-delivers
• It is also possible to reduce RTO-multicast to consensus

• Only allow process crash failures
• Assume up to f of the N processes may crash
• Algorithm uses basic multicast (guaranteed delivery to correct processes assuming sender does not crash)
• Algorithm
• f + 1 rounds used to multicast values
• Process crash possible at any point
• Each round uses timeouts based on maximum time taken by a correct process to multicast message

• Initially, each process proposes a value form a set D
• Each process maintains the set of values V_i^r known to it at round r
• In round r, where 1 <= r <= f + 1:
• Each process multicasts values to others (only values not sent before V_i^r - V_i^r+1)
• Each process receives multicast messages according any new value in V_i^r+1  
• After F+1 rounds, each process chooses minimum V_i^r+2 as decision value 

• Sets timeout to maximum time for correct process to multicast message
• Can conclude process crashed if no reply
• If process crashes, some value may not be forwarded
• At round F+1:
• All correct processes arrive at the same set of values
• Hence reach the same decision value (minimum)
• At least f+1 rounds needed to tolerate f crash failures (with any algorithm, not just this one)

• Process exhibits arbitrary failures
• Faulty processes may send any message at any time/ommit messages
• Up to f of the N processes faulty
• In synchronous systems can use timeout to detect absence of a message
• Cannot conclude process crashed if no reply
• No solution exists when N <= 3f
• Requirements
• Termination, Agreement, as for consensus
• Integrity: If the commander is correct, then all correct processes decide on value proposed by commander
• Integrity implies agreement when commander is correct

[image]