consensus

共识算法通常伴随着复制状态机(replicated state machines)问题,它是分布式系统能够容错的基础,多台服务器就一系列值达成一致,一旦它们就某个值做出决定,该决定就不能被改变。

任何具有 TAV 特性的算法都可以被认为在解决共识问题

  • termination: all non-faulty processes make a decision
  • agreement: all deciding processes make the same decision
  • validity: some process proposed the decision

Further readings

[1] Disk Paxos by Eli Gafni & Leslie Lamport, 2002
[2] The ABCD’s of Paxos by Butler W. Lampson, PODC 2001
[3] Paxos for System Builders: An Overview and The Complete Specification by Yair Amir and Jonathan Kirsch, 2008
[4] How to Build a Highly Available System Using Consensus by Butler W. Lampson, 1996

References

[1] Can’t we all just agree?
[2] Distributed Consensus Reading List 📚 maintained by Heidi Howard