Consensus without failures A set of n nodes each holding an input value viE(0,1}, all nodes need to output an identical out value that is some vi. How to solve this problem when there is no failure? Execute at each node i: 0ut←-Vi: Send out to all nodes. Wait until receive all messages sent in this round. out -min of received values,and current out. Output out as final decision. Clearly this algorithm achieves termination,agreement,and validity. This algorithm needs 1 round,sends (n2)messages in total
Consensus without failures • A set of 𝑛 nodes each holding an input value 𝑣𝑖 ∈ 0,1 , all nodes need to output an identical 𝑜𝑢𝑡 value that is some 𝑣𝑖 . • How to solve this problem when there is no failure? 0 1 1 Execute at each node 𝒊: 𝑜𝑢𝑡 ← 𝑣𝑖 . Send 𝑜𝑢𝑡 to all nodes. Wait until receive all messages sent in this round. 𝑜𝑢𝑡 ← min of received values, and current 𝑜𝑢𝑡. Output 𝑜𝑢𝑡 as final decision. 0 1 1 Clearly this algorithm achieves termination, agreement, and validity. This algorithm needs 1 round, sends Θ 𝑛 2 messages in total
Consensus with crash failures ·A set of n nodes each holding an input value vi∈{0，l, all correct nodes need to output an identical out value that is some vi. Does the algorithm still work if there is one crash failure? Execute at each node i: 0ut←i. Send out to all nodes. Wait until receive all messages sent in this round. 0 out -min of received values,and current out. Output out as final decision. This algorithm is NOT crash tolerant!
Consensus with crash failures • A set of 𝑛 nodes each holding an input value 𝑣𝑖 ∈ 0,1 , all correct nodes need to output an identical 𝑜𝑢𝑡 value that is some 𝑣𝑖 . • Does the algorithm still work if there is one crash failure? 0 1 1 Execute at each node 𝒊: 𝑜𝑢𝑡 ← 𝑣𝑖 . Send 𝑜𝑢𝑡 to all nodes. Wait until receive all messages sent in this round. 𝑜𝑢𝑡 ← min of received values, and current 𝑜𝑢𝑡. Output 𝑜𝑢𝑡 as final decision. 0 1 1 This algorithm is NOT crash tolerant!
Consensus with crash failures A set of n nodes each holding an input value viE(0,1}, all correct nodes need to output an identical out value that is some vi. ·Among n nodes,,at most f may crash,where1≤f≤n-1. Execute at each node i: round←1,0ut←-v. While(rond≤f+1) Send out to all nodes. Wait until receive all messages sent in this round. out min of above received values,and current out. round←-round+1. Output out as final decision. Definition 1:call a round clean if in that round no node crashes. Lemma 1:by the end of a clean round,all correct nodes have identical out value. Lemma 2:once correct nodes have identical out,that value will persist
Consensus with crash failures • A set of 𝑛 nodes each holding an input value 𝑣𝑖 ∈ 0,1 , all correct nodes need to output an identical 𝑜𝑢𝑡 value that is some 𝑣𝑖 . • Among 𝑛 nodes, at most 𝑓 may crash, where 1 ≤ 𝑓 ≤ 𝑛 − 1. Execute at each node 𝒊: 𝑟𝑜𝑢𝑛𝑑 ← 1, 𝑜𝑢𝑡 ← 𝑣𝑖 . While (𝑟𝑜𝑢𝑛𝑑 ≤ 𝑓 + 1) Send 𝑜𝑢𝑡 to all nodes. Wait until receive all messages sent in this round. 𝑜𝑢𝑡 ← min of above received values, and current 𝑜𝑢𝑡. 𝑟𝑜𝑢𝑛𝑑 ← 𝑟𝑜𝑢𝑛𝑑 + 1. Output 𝑜𝑢𝑡 as final decision. Definition 1: call a round clean if in that round no node crashes. Lemma 1: by the end of a clean round, all correct nodes have identical 𝑜𝑢𝑡 value. Lemma 2: once correct nodes have identical 𝑜𝑢𝑡, that value will persist
Consensus with crash failures ·A set of n nodes each holding an input value vi∈{0，l, all correct nodes need to output an identical out value that is some vi. ·Among n nodes,,at most f may crash,where1≤f≤n-1. Execute at each node i: round←1,0ut←-Vi. While(round≤f+1) Send out to all nodes. Wait until receive all messages sent in this round out min of above received values,and current out. round←-round+1. Output out as final decision. This algorithm solves consensus even if there are f crash failures. This algorithm needs f+1 rounds,sends (fn2)messages in total
Consensus with crash failures • A set of 𝑛 nodes each holding an input value 𝑣𝑖 ∈ 0,1 , all correct nodes need to output an identical 𝑜𝑢𝑡 value that is some 𝑣𝑖 . • Among 𝑛 nodes, at most 𝑓 may crash, where 1 ≤ 𝑓 ≤ 𝑛 − 1. Execute at each node 𝒊: 𝑟𝑜𝑢𝑛𝑑 ← 1, 𝑜𝑢𝑡 ← 𝑣𝑖 . While (𝑟𝑜𝑢𝑛𝑑 ≤ 𝑓 + 1) Send 𝑜𝑢𝑡 to all nodes. Wait until receive all messages sent in this round. 𝑜𝑢𝑡 ← min of above received values, and current 𝑜𝑢𝑡. 𝑟𝑜𝑢𝑛𝑑 ← 𝑟𝑜𝑢𝑛𝑑 + 1. Output 𝑜𝑢𝑡 as final decision. This algorithm solves consensus even if there are 𝑓 crash failures. This algorithm needs 𝑓 + 1 rounds, sends Θ 𝑓𝑛 2 messages in total
Crash tolerance is NOT free! Execute at each node i: Execute at each node i: round←1,0ut←vi. out←Vi While(round≤f+1) Send out to all nodes. Send out to all nodes. Wait until receive all messages sent in this round. Wait until receive all messages sent in this round. out -min of received values,and current out. out min of above received values,and current out Output out as final decision. round←round+1. Output out as final decision. Algorithm with no crash tolerance Algorithm tolerating up to f crashes 1 round f+1rounds 0(n2)messages 0(fn2)messages Can we design faster crash tolerant consensus algorithms?
Crash tolerance is NOT free! Execute at each node 𝒊: 𝑜𝑢𝑡 ← 𝑣𝑖 . Send 𝑜𝑢𝑡 to all nodes. Wait until receive all messages sent in this round. 𝑜𝑢𝑡 ← min of received values, and current 𝑜𝑢𝑡. Output 𝑜𝑢𝑡 as final decision. Execute at each node 𝒊: 𝑟𝑜𝑢𝑛𝑑 ← 1, 𝑜𝑢𝑡 ← 𝑣𝑖 . While (𝑟𝑜𝑢𝑛𝑑 ≤ 𝑓 + 1) Send 𝑜𝑢𝑡 to all nodes. Wait until receive all messages sent in this round. 𝑜𝑢𝑡 ← min of above received values, and current 𝑜𝑢𝑡. 𝑟𝑜𝑢𝑛𝑑 ← 𝑟𝑜𝑢𝑛𝑑 + 1. Output 𝑜𝑢𝑡 as final decision. Algorithm with no crash tolerance Algorithm tolerating up to 𝑓 crashes 1 round Θ 𝑛 2 messages 𝑓 + 1 rounds Θ 𝑓𝑛 2 messages Can we design faster crash tolerant consensus algorithms?