示例：完全有序的多播

案例

1. 旧金山客户增加100美元，纽约银行增加1％的利息
   • 旧金山将有1,111美元，纽约将有1,110美元
2. 更新复制的数据库并使其处于不一致的状态。
3. 可以使用Lamport的完全有序

Lamport Clock (1)

Lamport Clock

1. 所有消息以相同顺序传递给每个接收者的多播操作。
2. Lamport Details:
   • 每条消息都使用其发送者的当前逻辑时间进行时间戳。
   • 多播消息也被发回给发送者。
   • 假设一个发送者发送的所有消息都按照它们发送的顺序被接收，并且没有消息丢失。
   • 接收过程将消息放入根据时间戳排序的本地队列中。
   • 接收者向所有其他进程多播一个ACK
   • 只有在队列头部和所有参与者都认可的情况下才能发送消息
   • 接收过程将消息放入根据时间戳排序的本地队列中。
3. 为什么这个可以？
   • 来自Lamport的关键点：接收到的消息的时间戳低于ACK的时间戳。
   • 所有进程最终将具有相同的本地队列副本->一致的全局排序。

Distributed Mutual Exclusion

A Distributed Algorithm(Lamport Mutual Exclusion)

1. 每个进程都维护一个等待进入临界区的请求队列。 队列由从Lamport时间戳导出的虚拟时间戳排序
   • 对于任何事件e，e'使得e - > e'（因果排序），T（e）<T（e'）
   • 对于任何不同的事件e，e'，T（e）！= T（e'）
2. 当节点i要进入C.S.时，它将时间标记的请求发送到所有其他节点（包括它本身）
   • 等待所有其他节点的回复。
   • 如果自己的请求位于其队列的头部并且已收到所有答复，进入C.S.
   • 退出C.S.时，从队列中删除它的请求，并向每个进程发送释放消息。
3. 其他节点：
   • 收到请求后，在自己的请求队列（按时间戳排序）中输入请求并回复一个时间戳。
     • 这个回复是单播的，不像Lamport完全命令多播的例子。 为什么？
       • 只有请求者需要知道消息已准备好提交。
       • 广播释放消息让其他人继续前进
     • 收到释放消息后，从自己的请求队列中删除相应的请求。
     • 如果自己的请求位于其队列的头部并且已收到所有答复，请进入.S.
4. 正确性
   • When process x generates request with time stamp Tx, and it has received replies from all y in Nx, then its Q contains all requests with time stamps <= Tx.
5. 性能
   • Process i sends n-1 request messages
   • Process i receives n-1 reply messages
   • Process i sends n-1 release messages.
6. 问题
   • 如果节点失败怎么办？
   • 性能比较集中
   • 消息重新排序呢？

Ricart & Agrawala

1. 也依靠Lamport完全顺序的时钟。
2. 当节点我想进入C.S.，它发送时间戳请求到所有其他节点。 这些其他节点回答（最终）。 当我收到n-1个回复时，就可以进入C.S.
3. 技巧：具有较早请求的节点j在完成其C.S.之前不会回复i。

三种不同的情况：

1. 如果接收者没有访问资源并且不想访问资源，它就向发送者返回OK消息。
2. 如果接收者已经可以访问资源，它就不会回复。 而是将请求排队。
3. 如果接收者也想访问资源，但是还没有这样做，它会将传入消息的时间戳与它发送给每个人的消息中包含的时间戳进行比较。 最低的一个胜利。

算法图示

1. 两个进程（0和2）希望同时访问共享资源。

1

2. 进程0具有最低的时间戳，所以它赢了。

2

3. 当进程0完成时，它也发送一个OK，所以2现在可以继续。

3

正确性

1. 看节点A和B.假设两者都被允许同时在关键部分。
   • A must have sent message (Request, A, Ta) & gotten reply (Reply, A).
   • B must have sent message (Request, B, Tb) & gotten reply (Reply, B).
2. 情况1：在其他发送请求之前收到请求。
   - 例如，B在发送（Request，B，Tb）之前收到（Request，A，Ta）。 那么会有Ta <Tb。 A离开C.S之后才会回答。
3. 情况2：在收到他人之前都发送了请求
   • 但是，Ta＆Tb仍然是必须的。 假设Ta <Tb。 那么A在离开C.S之前不会回复B.

无死锁

1. 不能在每个节点等待其他的地方循环
2. 考虑双节点情况：节点A和B造成对方死锁。
   • 如果延期答复B＆B将延期答复给A，则会导致这种情况，但这需要Ta <Tb＆Tb <Ta。
3. 对于一般情况，将有一组节点A，B，C，...，Z，使得A对B延迟回答，B到C，... Y到Z，Z到A.这需要 Ta <Tb <... <Tz <Ta，这是不可能的。

无饥饿

1. 如果节点发出请求，它将被最终授予
2. 声明：如果节点A用时间标记Ta发出请求，则最终所有节点的本地时钟> Ta。
3. 理由：从请求开始，A发送的每个消息将具有时间戳> Ta。
   • 所有节点在接收到这些消息后将更新它们的本地时钟。
   • 因此，最终，A的请求将比其他任何节点请求具有更低的时间戳，并且将被授予。

性能

1. 每个周期涉及2（n-1）条消息
   • n-1 requests by I
   • n-1 replies to I
2. 问题
   • What if node fails?
   • Performance compared to centralized

令牌环算法

A Token Ring Algorithm

1. 将涉及的流程组织到逻辑环中
2. 一个令牌在任何时候->从一个节点到另一个节点沿着环路传递
3. 正确性：
   • 显然安全：只有一个进程可以持有令牌
4. 公平：
   • 在获得访问权限之前，最多只能传递一次环。
5. 性能
   • 每个周期需要1到∞个消息、
   • 协议在0和n-1之间的延迟
6. 问题
   • 令牌的丢失

四种算法的比较

image.png

总结

1. Lamport算法演示了分布式进程如何维护数据结构（优先级队列）的一致副本。
2. Ricart和Agrawala的算法演示了逻辑时钟的实用性。
3. 集中式和基于环的算法消息数量要少得多
4. 这些算法都不能容忍失败的进程或丢弃的消息。

Ricart & Agrawala Example

1. 进程1,2,3通过进程ID计算时间戳T（e）= 10 * L（e）+ id来创建完全排序的时钟，其中L（e）是常规的Lamport时钟。
2. Initial timestamps  P1: 421, P2: 112, P3: 143
3. Action types:
   • R m: Receive message m
   • B m: Broadcast message m to all other processes
   • S m to j: Send message m to process j

image.png
P1 and P2 compete for lock after it is released by P3.
P1's request has timestamp 451, while P2's request has timestamp 182.
P2 defers reply to P1, but P1 replies to P2 immediately.
This allows P2 to proceed ahead of P1.

参考

Lamport Timestamp在totally-ordered multicast中的应用