Lamport逻辑和向量时间戳
1.Lamport逻辑时钟
Lamport认为，重要的不是所有进程在时间上完全一致，而是它们在事件的发生顺序上要达成一致。
先发生的定义： a → b 表示a在b之前发生，此时 C(a) < C(b), a b可以是同一个进程中的两个事件或进程间的消息发送事件。并发事件没有先后关系。
Lamport算法：[more…]
- 遵循事件的先发生关系，每个消息都应携带根据发送者时钟的发送时间，当消息到达并接收时，接收者时钟显示的时间比消息发送者时间早时，接收者就将时钟调到比发送者者的时间大1的值。
- 为了满足全局时间的需要：在每两个事件之间，时钟必须至少滴答一次，如果一个进程以相当快的速度发送或者接收两个消息，那么他得时钟必须在这之间至少滴答一次。
- 两个事件不会精确地同时发生
2.Lamport逻辑时钟的缺陷
不能捕捉因果关系，而向量时间戳可以。
- Lamport时间戳导致分布式系统中所有事件都要经过排序以具有这样的关系：如果a发生在b之前， 那么C(a) < C(b)
- Lamport时间戳只能捕捉事件发生的先后关系，而不能捕捉因果关系。C(a) < C(b)不能说明a事件发生在b事件之前。 因果关系需要通过向量时间戳来捕获。
3.向量时间戳
因果关系：如果VT(a) < VT(b) 则a在因果上处于事件b之前。向量时间戳是让每个进程P都维护一个向量V来完成，该向量的性质如下：
a)Vi[i]是到目前为止进程Pi发生的事件的数量。
b)如果Vi[j]=k，那么进程Pi知道进程Pj中已经发生了k个事件
接收者可以通过消息m的时间戳知道其他进程中有多少事件发生在它之前，消息m在因果上可能依赖于这些事件。
当Pj收到消息m，调整自己的向量，将每项Vj[k]设置为max{Vj[k], vt[k]}, 然后 Vj[i]增加1。
需要会看图计算向量时间戳：
向量时间戳中只有各个分量都是小于关系时存在因果关系，而平行关系是并发关系。
选举算法
1. 欺负算法(Bully Algorithm)
算法：当一个进程发现协调者不再响应请求时，它就发起一个选举：
P向所有编号比它大的进程发送一个election消息；
如果无人响应，P获胜成为协调者；
如果有编号比它大的进程响应，则响应者接管选举工作。P的工作完成。
当以前崩溃的进程恢复时，它将主持一次选举，如果该进程是当前正在运行的进程中进程号最大的，就成为协调者。
总之进程号最大的总是取胜。
2.环算法——不使用令牌环
假设进程按照物理和逻辑顺序进行了排序，那么每个进程就知道它的后继者是谁了。
当任何一个进程注意到协调者不工作时，它就构造一个带有它自己的进程号的election消息，并将该消息发送给它的后继者。
如果后继者崩溃了，发送者沿着此环跳过它的后继者发送给下一个进程，或者再下一个，直到找到一个正在运行进程。
在每一步中，发送者都将自己的进程号加到该消息列表中，以使自己成为协调者的候选人之一。
最终，消息返回到发起此次选举的进程。当发起者进程接收到一个包含自己进程号的消息时，它识别出这个事件。此时，消息类型变成coordinator消息，并再一次绕环运行，向所有进程通知谁是协调者(成员列表中进程号最大的那个)以及新环中的成员都有谁。这个消息再循环一周后被删除，随后每个进程都恢复原来的工作。
互斥算法
1. 集中式算法
(1).算法
选举一个进程作为协调者，如最大网络地址号的机器上的进程。
无论何时一个进程要进入临界区，它都要向协调者发送一个请求消息，说明它想要进入哪个临界区并请求允许。
如果没有进程在临界区就发送“允许”应答，该进程进入临界区，如果有进程在临界区，就把该消息放入请求队列，发送“拒绝请求”的应答。
当临界区中的进程退出临界区，向协调者发送“释放”消息，协调者会从请求队列中取出第一个进程，发送“允许”进入的消息。
(2)优点
实现了互斥，每个时刻，协调者只让一个进程进入临界区。
很公平，没有进程会永远阻塞，不会饥饿，不会死锁
容易实现，每使用一次临界区，只需要三条消息（请求，允许，释放）
可以管理临界区或更一般的资源
(3).缺点
协调者是单点故障，在规模较大的系统中，单个协调者会成为性能瓶颈.
如果进程在发出请求之后阻塞，那么请求者就不能区分“拒绝进入”和协调者已经崩溃的两种情况。
2.分布式算法
1)Lamport算法
当进程Si想进入临界区，向其他n-1个进程广播请求REQUEST(tsi, i), 并把请求放入自己请求队列request_queuei。
其他n-1个进程受到请求REQUEST(tsi, i)后，把该请求放入各自的请求队列request_queuej， 并向进程Si响应一个带时间戳的REPLY消息。
进程Si进入临界区，当且仅当满足以下两个条件：
* Si从其他进程收到的消息的时间戳都大于自己的请求时间戳(tsi, i)- Si的请求是请求队列request_queuei的第一个请求
当进程Si退出临界区：从请求队列request_queuei中删除该请求，并向其他n-1个进程广播一个带时间戳的释放临界区的消息。其他n-1个进程收到该消息后，从请求队列request_queuej中删除该请求
在Lamport算法中，进程Request, REPLY, RELEASE一共发送了3(n-1)条消息，其实在一个接收者收到消息后，如果不同意Si进入临界区，没有必要再发送确认。
可以改进算法在2(n-1)到3(n-1)之间
2)Ricart和Agrwala算法，改进Lamport算法
- 当一个进程想进入一个临界区时，它构造一个消息，其中包含它要进入的临界区的名字、它的进程号和当前时间。然后它将消息发送给所有其他的进程，理论上讲也包括它自己。
- 当一个进程接收到来自另一个进程的请求消息时，它根据自己与消息中的临界区相关的状态来决定它要采取的动作。可以分为三种情况：第一，若接收者不在临界区也不想进入临界区，它就向发送者发送一个OK消息。第二，若接收者已经在临界区，它不进行应答，而是将该请求放入队列中。第三，如果接收者想进入临界区但尚未进入时，它将对收到的消息的时间戳和包含在它发送给其余进程的消息中的时间戳进行比较。时间戳最早的那个进程获胜。如果收到的消息的时间戳比较早，那么接收者向发送者发回一个OK消息。如果它自己的消息的时间戳比较早，那么接收者将接收到的请求放入队列中，并且不发送任何消息。
- 在发送了请求进入临界区的请求消息后，进程进行等待，直到其他所有进程都发回OK消息为止。一旦得到所有进程的允许，它就可以进入临界区了。当它退出临界区时，它向其他队列中的所有进程发送OK消息，并将请求从队列中删除。（也就是说一个进程进入临界区的条件是收到了n-1个OK消息）
算法优点：不会饥饿，死锁；每次进入临界区仅需要2(n-1)条消息；没有单点故障
算法缺点：第一，单点故障变成了n点故障，如果任何一个进程崩溃，不能应答OK，这种不应答被错误的解释为拒绝请求，阻塞了所有进程进入任何一个临界区。第二，网络通信开销多于集中式算法；第三，要么必须使用组通信原语，要么每个进程必须维护组成员清单；第四，要求所有进程参与做出与进入临界区有关的所有决定，强迫每个进程都承担这样的负载是不可能的，可以在得到大多数进程OK的情况下进入临界区，但实现复杂。
3.令牌环算法
(1)算法
- 假设：总线式的网络中，进程没有固定的顺序，环中为每个进程分配了一个位置，每个进程都直到谁在它的下一个位置。
- 当环初始化时，进程0得到一个令牌token。该令牌绕着环运行，用点对点发送消息的方式把它从进程k传递到进程k+1(以环大小为模)。进程从它邻近的进程得到令牌后，检查自己是否要进入临界区。如果自己要进入临界区，那么它就进入临界区，做它要做的工作，然后离开临界区。在该进程退出临界区后，它沿着环继续传递令牌。不允许使用同一个令牌进入另一个临界区。
- 如果一个进程得到了邻近进程传来的令牌，但是它并不想进入临界区，那么它只是将令牌沿环往下传递。因而，当没有进程想进入临界区时，令牌就绕环高速传递。
(2)优点
没有饥饿现象：任何时候都只有一个进程有令牌，并且令牌以固定的顺序循环传递。
(3)缺点
如果令牌丢失，必须重新生成令牌.
检测令牌丢失很困难，网络中令牌出现两次的时间间隔不确定，没有发现令牌可能是丢失，也可能是某个进程在占用。
如果有进程崩溃，该算法会有问题。(恢复方法： 要求每个进程维护进程环的配置信息， 每个进程收到令牌后发出确认信息，当它尝试把令牌传递给它的邻近进程时，如果没有收到确认，该进程就崩溃了，从组中删除该进程，继续传递令牌。)
三种互斥算法的比较
（1）程进入临界区，需要发送的消息数目不同
集中式算法: 3条消息，请求，允许，释放，简单而有效.
分布式算法：2(n-1)条
令牌环算法: 1~(n-1)条
（2）进入临界区之前的消息延迟不同
集中式算法: 2条消息，请求，允许。
分布式算法：2(n-1)条
令牌环算法: 0~(n-1)条
（3）三种算法在这三种算法在进程崩溃的情况下都损失惨重。为了避免进程崩溃造成的系统瘫痪，必须引入专门的措施和额外的复杂性。
资源
分布式系统总结part1 中间件，进程迁移，移动通信失效，名称解析，移动实体定位
分布式系统总结part2 Lamport同步与向量时间戳，两大选举算法，三大互斥算法