Distributed Consensus Reaching Agreement in Faulty Environment 郑朝栋 南京大学计算机科学与技术系
Distributed Consensus Reaching Agreement in Faulty Environment 郑朝栋 南京大学计算机科学与技术系
Distributed computing is everywhere! ☆ What is distributed computing? Multiple agents cooperate to accomplish a task f(P1,P2,P3,…,Pn)→Y
Distributed computing is everywhere! Multiple agents cooperate to accomplish a task 𝑓 𝑃1, 𝑃2, 𝑃3, ⋯ , 𝑃𝑛 → 𝑌 What is distributed computing?
Why we love distributed computing? 。Better performance 2020天猫双全球狂入 RYZEN hedoop 双111 交额49822 210为下hc 1406个4 Stronger fault-tolerance …fel DDos
Why we love distributed computing? • Better performance • Stronger fault-tolerance
No free lunch! Distributed setting introduces new challenges. Locality (Nodes do not know the whole picture.) E.g.:Distributed MST/SSSP problem. Symmetry-breaking(Nodes can only behave identically.) E.g.:Impossibility of deterministic leader election in anon rings. Distributed systems are NOT fault-tolerant by default. In many cases,clever distributed algorithms are needed. E.g.:Paxos/Raft for the consensus problem. Sometimes,certain level of fault-tolerance is impossible! E.g.:Impossibility of crash-tolerant consensus in async setting. A quick look of fault-tolerance via the consensus problem
No free lunch! • Distributed setting introduces new challenges. • Locality (Nodes do not know the whole picture.) E.g.: Distributed MST/SSSP problem. • Symmetry-breaking (Nodes can only behave identically.) E.g.: Impossibility of deterministic leader election in anon rings. • Distributed systems are NOT fault-tolerant by default. • In many cases, clever distributed algorithms are needed. E.g.: Paxos/Raft for the consensus problem. • Sometimes, certain level of fault-tolerance is impossible! E.g.: Impossibility of crash-tolerant consensus in async setting. A quick look of fault-tolerance via the consensus problem
10110 Model and Problem
Model and Problem