分布式系统作业1

姓名：方伟 学号：201121060429 班级：计算机4班 11.4

解：客户端应该选择最低往返时间为20ms,然后估计当前时间为10：54：28.342+0.02/2=10:54:28.352.精度为10ms.

如果消息的最低传送时间为8ms，然后设置保持不变，但是精度提高到2ms。

11.14

解 P发送消息m;

Q记录状态（101） P发送标识

Q接受消息m，并把它的标志设为102

Q接受标识，并通过标识接受规则，记录它的状态（102），从P到Q的通道的状态作为{}

Q发送标识 P接受标识

P记录收到从Q到P的通道设置消息的状态，因为它保存的状态等于｛｝

3 、Databases-R-Us runs a cluster of three servers A, B, and C, which communicate with one another. You are told that the current clock skews between server pairs are as follows: A-B: 3 ms; B-C: 1 ms; C-A: -4 ms. Further, you are told that correctness in the database requires that no two server clocks be more than 30ms apart. If each of the servers has an absolute clock drift of 2 ms per minute, how many minimum (i.e., worst-case) minutes can the cluster go without running a synchronization algorithm among its servers?

解：由于A,C相差最大，并且三个服务器间存在相同时钟差，所以最段时间应该发生在A,C之间。由于每分钟时钟偏移2ms，两个服务器逆向偏移则最快达到30ms限制，故分钟数为（30-4）/4=6.5min

4. a, b, and c are events and no two events belong to the same process. Prove or disprove (give counter-example) the following: (a)a is concurrent with b and b is before c implies that a is before c. (b)a is concurrent with b and b is concurrent with c implies that a is concurrent with c.

解：(1) A与B并发，B在C之前不意味着A在C之前。例如，B运行一段时间，放弃处理器，处于等待状态，此时C占用处理器，待C运行结束时，B开始运行，同时A也开始运行，A与B并行。但是A并不在C之前。

(2)A与B并发，B与C并发并不意味着A与C并发。例如，A与B的前一个阶段并发，此时A进程结束，C进程开始。C与B并发，此时A进程已经结束，所以A与C不是并发的。