Paxos算法1-算法形成理论 - 老码农的专栏 - 博客频道 - CSDN.NET



Paxos算法1-算法形成理论 - 老码农的专栏 - 博客频道 - CSDN.NET

我们所有的描述都假设读者已经熟读了Lamport的paxos-simple一文,因此对各种概念不再解释。   状态机:在状态机中的一致性更强调在每个初始状态一致的状态机上执行一串命令后状态都必须相互一致,也就是顺序一致性。Paxos算法中的一致性指的就是这种情况,接下来我们会对这种场景进一步讨论。       大家或许会对该描述有更深的理解。 很显然,为了给每个数据唯一编号,每次表决只能产生一个数据,否则表决就没有任何意义。Paxos的算法的所有精力都放在如何在一次表决只产生一个数据。再进一步,我们称表决的数据叫Value,Paxos算法的核心和精华就是确保每次表决只产生一个Value。     P1:An acceptor must accept the first proposal that it receives. 乍一看,这个条件是显然的,因为之前没有任何value,acceptor理所当然地应该accept第一个proposal,但仔细想想,感觉P1这个条件很不严格,到底是一个对问题的简单描述还是一个数学上严格的必要条件?这些疑问归结为2个问题: (1)这个条件本质上在保证什么? (2)第二个proposal怎么办? 如何解决P1中无法形成多数派的问题 第二个proposal如何选择 于是约束P2出现了: P2:If a proposal with value v is chosen, then every higher-numbered proposal that is chosen has value v.

Read full article from Paxos算法1-算法形成理论 - 老码农的专栏 - 博客频道 - CSDN.NET


No comments:

Post a Comment

Labels

Algorithm (219) Lucene (130) LeetCode (97) Database (36) Data Structure (33) text mining (28) Solr (27) java (27) Mathematical Algorithm (26) Difficult Algorithm (25) Logic Thinking (23) Puzzles (23) Bit Algorithms (22) Math (21) List (20) Dynamic Programming (19) Linux (19) Tree (18) Machine Learning (15) EPI (11) Queue (11) Smart Algorithm (11) Operating System (9) Java Basic (8) Recursive Algorithm (8) Stack (8) Eclipse (7) Scala (7) Tika (7) J2EE (6) Monitoring (6) Trie (6) Concurrency (5) Geometry Algorithm (5) Greedy Algorithm (5) Mahout (5) MySQL (5) xpost (5) C (4) Interview (4) Vi (4) regular expression (4) to-do (4) C++ (3) Chrome (3) Divide and Conquer (3) Graph Algorithm (3) Permutation (3) Powershell (3) Random (3) Segment Tree (3) UIMA (3) Union-Find (3) Video (3) Virtualization (3) Windows (3) XML (3) Advanced Data Structure (2) Android (2) Bash (2) Classic Algorithm (2) Debugging (2) Design Pattern (2) Google (2) Hadoop (2) Java Collections (2) Markov Chains (2) Probabilities (2) Shell (2) Site (2) Web Development (2) Workplace (2) angularjs (2) .Net (1) Amazon Interview (1) Android Studio (1) Array (1) Boilerpipe (1) Book Notes (1) ChromeOS (1) Chromebook (1) Codility (1) Desgin (1) Design (1) Divide and Conqure (1) GAE (1) Google Interview (1) Great Stuff (1) Hash (1) High Tech Companies (1) Improving (1) LifeTips (1) Maven (1) Network (1) Performance (1) Programming (1) Resources (1) Sampling (1) Sed (1) Smart Thinking (1) Sort (1) Spark (1) Stanford NLP (1) System Design (1) Trove (1) VIP (1) tools (1)

Popular Posts