分布式系统协议与图嵌入技术解析

### 分布式系统协议与图嵌入技术解析 在分布式系统和图论领域，有两项重要的技术值得深入探讨，一项是实现顺序一致性的分布式协议，另一项是将全三元树嵌入递归循环图的方法。下面将详细介绍这两项技术。 #### 分布式系统协议 该分布式系统是异步的，没有对站点的处理速度和消息传输延迟做任何假设。协议遵循客户端/服务器架构的思想，尽可能模块化，只允许进程和对象之间通信，不允许两个进程或两个对象之间直接发送消息，这种约束便于向系统中添加新的进程或对象。 ##### OO 约束与合法性 为每个对象 x 配备一个管理器 Mx 来确保 OO 约束，使得协议真正实现分布式，没有集中控制。管理器 Mx 对关联对象 x 的写操作进行排序，对象值被缓存，对象 x 的最后写入者被视为其所有者，直到该值被另一个进程覆盖或读取。通过缓存值和对象所有权的结合，进程可以免费读取缓存值并更新自己拥有的对象。 为确保满足 OO 约束所需的读写和写读同步，并获得合法的读操作，会对读操作进行适当调度，这是协议的主要部分，通过进程 pi 每次询问管理器 Mx 时执行的检查合法性程序来完成。 ##### 控制变量 - **进程的局部变量**： - `presenti[x]`：布尔变量，当 pi 拥有 x 的合法副本时为 true，表示 pi 可以在本地读取其缓存的 x 副本。 - `Ci[x]`：缓存，包含 x 的副本，只有当 `presenti[x]` 为 true 时其值才有意义。 - `owneri[x]`：布尔变量，如果 pi 是 x 的最后写入者则为 true，且有 `owneri[x] ⇒ presenti[x]`。 - **对象管理器的局部变量**： - `Cx`：包含 Mx 所知的 x 的最后值。 - `ownerx`：包含进程标识或 ⊥。`ownerx = i` 表示除 pi 外没有进程拥有 x 的最后值；`ownerx = ⊥` 表示 Mx 拥有 x 的最后副本，对象 x 的所有者（如果有）是唯一可以修改它的进程。 - `hlwx[1..n]`：布尔数组，`hlwx[i]` 为 true 当且仅当 pi 拥有 x 的最后值。 系统初始状态下，只有 Mx 知道 x 的初始值并保存在 `Cx` 中，初始值如下： - 对于所有进程 pi 和对象 x：`owneri[x] = false`，`presenti[x] = false`，`Ci[x] = undefined`，`ownerx = ⊥`，`hlwx[i] = false`。 ##### 对象管理器的行为 对象管理器 Mx 的行为由以下三种消息处理情况描述： ```plaintext upon reception of write req (v) from pi: (1) if (ownerx ̸= ⊥) then send downgrade req (x) to pownerx; (2) wait downgrade ack (−) from pownerx endif; (3) Cx ← v; ownerx ← i; (4) hlwx[i] ← true; ∀j ̸= i : hlwx[j] ← false; (5) send write ack () to pi upon reception of read req () from pi: (6) if (ownerx ̸= ⊥) then send downgrade req (x) to pownerx; (7) wait downgrade ack (v) from pownerx; (8) Cx ← v; ownerx ← ⊥ endif; (9) hlwx[i] ← true; (10) send read ack (Cx) to pi upon reception of check req () from pi: (11) let d = (hlwx[i] ∧ (no write req is currently processed)); (12) send check ack (d) to pi ``` 下面是对应的 mermaid 流程图： ```mermaid graph TD; A[收到 write req (v) from pi] --> B{ownerx ̸= ⊥}; B -- 是 --> C[send downgrade ```