Paxos算法是个一致性算法，已经被用在分布式系统里面了，我想尝试一下UML这种语言的能力，于是写了这个帖子，
请大家看看这样的描述还可以被怎样改进。

我疑惑各种优美的算法的结构是不是和一般的过程有挺本质的区别，各位可有高见？

还有，或许算法证明的过程也能用UML简单的表示出来。
===========================================================================
一般地，我更想知道数学上的算法如何部署到计算机上，自己没经验。

我估计能画出的图的种类会有很多种，现实中会基于其他的考虑，选择合适的实施方案。

根据Leslie Lamport论文中提到的在一个Server和几个Clients之间实现Paxos一致性算法，那就决定画成UML状态机图。

他介绍的用法就是机器之间通信的用法，所以，没必要画个UML Use Case图，如果是真正的涉及到用户和系统之间的交互
具体的应用场景我并不知道。这种在机器之间通信用法的需求来源于要处理大规模的并且对时效有严苛要求的广告系统。

我估计，要是想以 状态机实施 来出发其他UML建模需求，也应该可以找到，还是先做一个最简单而现成的吧。

============================================================================
我简述下Paxos算法：

Paxos算法中涉及到
          三类对象：Proposers ， Acceptors，Learners，他们拥有自主意志。
          一类信息：Proposals（n，v），n是其编号，v是其值，它们来自Proposers，要接受Acceptors的审阅、Learners的学习
          探求的问题是：寻找一个过程，通过这个过程选出一个能被大多数Acceptors接受的V，然后让Learners都了解到V。
---------------------------------------------------------------------------------------------------------------------------------------------------------
在论文Paxos Made Simple中，Leslie  Lamport从最简单的情形将这过程一般化为Paxos算法，选出V分为两阶段：

           Phase1：（a）一Proposer选了一个Proposal（n，*），并且向一大部分Acceptors发送了一个准备请求。
                         （b）如果一Acceptor收到了Proposal（n，*）的准备请求，而且n比该Acceptor之前收到的准备请求的编号
                           都要大，他就回复给该准备请求的Proposer保证不会接受编号小于n的Proposal，或者，他已经接受的
                           Proposal（n0,v0）。
           Phase2：（a）如果该Proposer从大部分的Acceptors收到对Proposal（n，*）的回复，就向每一个Acceptor发送
                           Proposal（n，v）的接受请求，v需要等于v0，如果n0=max{n0 |n0是来自他收到的回复的Proposal
                           （n0，v0）}，或者，如果还没有被接受的Proposal，该Proposer就自己定义Proposal（n，v）。
                         （b）如果一Acceptor收到Proposal（n，v）的接受请求，除非她已经回应了另一个Proposal（m，*）的
                           准备请求，这里m>n，否则她就接受Proposal（n，v）。
---------------------------------------------------------------------------------------------------------------------------------------------------------
选出V之后，就是比较简单的Learners学习V。
=============================================================================
我们用UML状态机图把上面的算法画出来：
如果，假设一个联机的系统共有k台机器，每一台机器都可以扮演Proposer，Acceptor，Learner的角色。
就可以用UML状态机模型描述一次选定V，学习V的过程，相当于一个Instance，而且每一台机器的状态变化都将如此。

画UML状态机模型的目的在于清晰地向开发人员传递涉及过程的信息，如果对于一个不曾了解该算法的人都能轻而易举地了解
了这个过程，可能就是这个模型画的成功的标志，当然前提是他懂UML语言。

为了弄清同一个机器要扮演不同的角色会对我们画状态图产生怎样的影响。首先我们认识到，问题的目的就在于找到一个大多数机器都接受的值，那么对于任意一个值v，机器a只有两种选择接受或者不接受，同时机器a对于值v接受或者不接受不能直
接影响最后机器群一起选择的值；也就是说，如果机器a接受了别人提交的值v，它就不会再自己去找另外一个值了。
---------------------------------------------------------------------------------------------------------------------------------------------------------
最开始，任何一个机器都是可以接受准备请求的，也是可以发送准备请求的，而且它们都会按照规矩来，不存在不遵守规则的
情况，比如不发准备请求，直接发接受请求这样的事情。事实上，我们看到对于发送过准备请求的机器，它想要发送接受请求
是有另外的条件的，就是他收到大部分接受者对于准备请求的回复。这样一来，他就不用提交请求值过去，节省了资源。

接受者接受准备请求也有条件，那就是它得真的确保不会接受之前的请求值，也就是不会通过之前的接受请求。我们感觉到这样的要求是很有效的通信，能够避免请求资源的浪费。

上两段的分析让我们看到通过约束接受者和请求者的行动的前提，能够有效的节约Proposal的资源，更直接的在计算机系统里
面节约的就是计算资源。

再引申一步，请求者发送准备请求的条件是什么，接受者接受接受请求的条件是什么？这两个问题的答案是自然的，直接和研究的问题本身相关，他们作为自主意志的机器，是否有了满意的值，没有的话，请求者还准备请求，接受者拒绝请求值；如果
已经有了满意的值，请求者不再发送准备请求，接受者接受请求值。这里我们还将看到，Paxos算法不仅在请求值的过程中尽
可能减少资源浪费（数量），同时，对已经提请的请求值精致周到地处理，是从对提请值质量的角度进行了节约，避免有价值的提请被拒绝。这一切是怎么做到的，好神奇。
----------------------------------------------------------------------------------------------------------------------------------------------------------
有了对每一种操作前提条件的分析，就比较容易把图画出来了。但是，UML状态机直接的元素是“状态”，我们就把这些严苛的
条件翻译为一些状态吧。

我觉得可以从接受者的角度出发，发现机器的“状态”，将自己作为请求者时候的条件转化为接受者时候的条件，比如有：
“（不）可以接受准备请求的状态”，“（不）可以接受接受请求的状态”。
只要弄清楚这四个状态之间是怎么转化的，好像我们就可以画出UML状态机图了。首先可以确定的是，我们的划分在逻辑上是
完备的，不管机器处在算法过程中的哪一步，它必然处在这四个状态中的一个或者几个中。这确保了我们的图能够有效地为工程人员展示算法的过程，我们只需要将机器在这几种状态之间的转化关系理清楚，画出来即可。

为方便，我们先对四种状态进行命名：
可以接受准备请求状态PrequestOpen；不可以接受准备请求状态PrequestLocked；
可以接受接受请求状态AccrequestOpen；不可以接受准备请求状态AccrequestLocked。

最初始状态自然从PrequestOpen开始。
先把一个机器作为一个Acceptor的状态转化图画出来。
----------------------------------------------------------------------------------------------------------------------------------------------------------
我们看到它在已经接受了Proposal（N,V）之后还在接受Prequest，原因就在于还有别的机器不知道它已经接受了，回复不知道
的机器是为了达成系统的一致性。也就是当一个机器即便是接受了一个Proposal，他依然需要保持PrequestOpen，目的是为了
和其他机器通信，并不是他自己接受了一个Proposal就完了。所以系统的终状态并不是AccrequestLocked，那么每个机器达到
什么状态之后就到了系统的终状态？不是PrequestOpen，AccrequestOpen，AccrequestLocked，那么是PrequestLocked吗？
从逻辑上说这是必然的，因为系统总归要到达得出一个一致值的状态，也就是大多数台机器也都接受了一个值，而所有的机器必须学习到这个值，其实，一个问题我并没有搞明白，就是两阶段的算法过程是不是能让每台机器完成学习大多数机器接受的
这个值，还是这个学习的过程是另外的过程完成的，我觉得这个算法之所以精妙绝伦，很可能在两阶段之后，所有机器已经完成了学习，我们先把这个问题探索明白。
我们看到了阶段2中要求一个持不同意见的Proposer学习已经被大多数接受的值v的过程，大多数都已经同意了一个值，而如果
该Proposer还不同意这个值，而且他即便已经通过了Prequest，算法也将要求他提请最后的值等于大家都认同的值，这样以来
所有的机器都就学习到被大部分接受的这个值了，他是通过提交一个准备请求得到的。
所以，我们看到这个算法是能保证所有的机器学习到这个值的。原论文里，作者还考虑到信息丢失等一系列的异常情况，我觉得Paxos也应该具备有效消除这些行为对达成最终的目标形成的障碍的。
那么，一个机器分别在什么接受状态下可以发送Prequest和Accrequest？
所以，接着前面的，一个机器即便自己已经接受了一个值，还需要保持PrequestOpen，因为还会有持不同意见的机器来向他学习该值的可能。如果再没有机器向他提Prequest时，说明大家都已经学习到了这个值，那么还需要关闭Prequest这样一个状态
吗？如果有一些机器因为异常还没有学习到这个值怎么办？
他还没有接受一个值，他更需要保持PrequestOpen，难道这个算法就要求Prequest一直都是Open的？
接下来的问题，更有意义，一个机器怎么知道一个值已经被大多数机器接受？从算法第二阶段我们看到，一个机器只能知道另外的某一个机器的Proposal（n0，v0），这个机器是他发送过请求的那些机器中的一个，他没有发送请求的那些机器的情况，他是不知道的。他提请的值是来自他关心的那些机器提请的值里面最后的那个。
算法会要求他去关注他没关注的那些机器的值吗？
是不是他想知道所有的机器的情况，只要提请准备请求就可以了呢？机器是有限的，他要是想知道，他总是能知道。
但是，这里又出现了一个问题，有那么多的提请，算法是怎么保证最后选定的是一个值，而不是选不出，或者多余一个呢？
这里就是由Proposal的序列来保证的，那么这里有个问题是，对于不同的机器，这些序列是会一样的吗，感觉不是，比如，一
个没有被提请的机器，这个问题真是不知道啊！
暂且，假设所有的机器在达成一致之前都会保持PrequestOpen，也就是没有。
---------------------------------------------------------------------------------------------------------------------------------------------------------
作为一个Proposer，他的Acceptor状态处于PrequestOpen，AccrequestOpen，AccrequestLocked这三种情况时他会做什么？
作为一个Proposer，他可以提准备请求、提接受请求，自己做的事情写在框里面，别人做的事情写在线框上作为条件。
作为Acceptor，自己状态改变的原因就是自己对别人做的事情的态度。作为Proposer自已做事情的原因就是想让更多的人接受
自己的Proposal，但是每个机器最终的状态由整个机器群体决定。不被接受就要接受别人。不接受就要请别人接受。不管怎么
着，就是要形成一致看法。
Open表示可以接受别人，Lock表示不可接受别人。准备阶段open的原因是准备接受别人，接受阶段Lock的原因是已经准备接
受后面的提请，接受阶段Open的原因是没有准备接受后面的提请。准备阶段拒绝的原因是已经接受了前面的提请。接受与否
都是针对某一个提案的。
作为Acceptor如果接受了一个提案，就不去提请了，只有他拒绝一个提请，才是他去提请的原因。
这样一个机器就成功的成为Acceptor和Proposer的结合体，先Acceptor，后Proposer。
如果先做Proposer，他的提请被接受，他就没必要做Acceptor了，如果提请被拒绝，他可以一直提请直到被接受，或者接受
别人，在某一个时刻，当他接受别人时，他就变成Acceptor了。
如果他已经找到满意的提请，不管来自接受别人，还是来自自己提请被接受，算法已经保证了这个提请就是大多数人都认可
的提请。如果这个提请不是被大多数人认可的，如果是他自己提请的，一定会被拒绝（已经出现了大家认可的）；如果是他
接受别人的，也一定会被拒绝（因为大家不认可）。
算法是怎么保证接受的那个值就是大多数认可的值的？
（1）PrequestOpen

（2）AccrequestOpen

（3）AccrequestLocked

知道他进入，在，离开这三种状态时分别做什么我们能完成完整的UML状态图啦！可是究竟什么是State Machine？
State Machine由一组值定义：
状态集合（Sta），输入集合（In）），输出集合（Out）），转移函数（Tr）），输出函数（Fout）），可识别的状态（开始）
状态集合有：PrequestOpen，AccrequestOpen，AccrequestLocked，PrequestLocked
输入集合有：提交准备请求，提交接受请求，回复准备请求，回复接受请求（别的机器对于机器a就是输入）
输出集合有：提交准备请求，提交接受请求，回复准备请求，回复接受请求（机器a自己对于别的机器就是输出）
转移函数有：Tr（Sta，In）——>Sta
输出函数有：Fout（Sta，In）——>Out
可识别状态：PrequestOpen

需要把Sta写在状态框里，把In写在UML图的箭头上，机器a做了什么是输出out写在状态框下面。
现在需要明确的定义四种状态，否则什么是进入这种状态，什么是在这种状态，什么是离开这种状态，并不明确。
输入、输出集合已经在论文中明确定义过了。
PrequestOpen 就是机器a（系统）没有选定一个满意值的状态，也就是说他正在回复一个接受请求时，也是PrequestOpen的。
AccrequestOpen 就是机器a还没有选定一个满意值，而且，已经收到至少一个被大多数回复的准备请求，但是还没有收到接
受请求的状态。
AccrequestLocked 就是机器a已经选定满意值，而且，已经不能接受新的接受请求的状态。
PrequestLocked 就是机器a已经选定满意值，而且，已经不能接受新的准备请求的状态。

现在我觉得我完全搞明白了，不过，这个图是一个树的选择的图，两个树交叉的图，而且用数学符号表示起来特别好，特别清晰。
++++++++++++++++++++++++++++++发现的风水岭++++++++++++++++++++++++++++++++++++++
虽然，暂时的目标已经实现了，但是，更值得考虑的是，这样有价值的问题是怎么提出来的，精妙的解决方案是怎么被想出来的。我会随时把关于这些问题的讨论加到后面。
---------------------------------------------------------------------------------------------------------------------------------------------------------
我能写出Paxos的code吗？
Leslie Lamport的原论文中好像用了不到150行code。
刘鹏老师在讲广义第二高价的时候，说，code就一行，背后的推理论证和经济学考量是更难的部分。
那岂不是说我可以比较容易的写出code了。
=============================================================================