交付三份不同用途的时钟证书
时钟观测、限期权限与因果标签路线最后交付三种可重算结果:偏移的可行集合、权限有效期的不重叠证明、事件的因果递增标签。下载标准库核验器,普通和python -O都执行显式检查,JSON只写到标准输出。用Fraction保存分数,9/10不能在复算中被不明舍入规则偷偷改变。
一、从报文记录恢复可行世界
第一份输入是四戳(100,134,136,112)。明确前提:整个交换窗口内两钟单位速率、偏移恒定;报文从发送到收到只有非负延迟,打点和内容诚实且属于同一请求。四戳分别是客户端发送、服务端接收、服务端发送、客户端接收。
客户端等了12,服务端处理2,因此传播往返10。上界来自T₂−T₁=34,下界来自T₃−T₄=24。提交区间[24,34],并保留中点29与它的最坏误差半径5。
不要只提交中点。用同一组观测分别构造三份见证:θ=24时去程10/回程0;θ=30时去程4/回程6;θ=34时去程0/回程10。每份都代回两条方程,说明为什么记录无法唯一选出30。改变传播为5/5、保持处理2及真偏移30,新的四戳应为100/135/137/112,中点才恰为30。
然后加入(200,232,233,205)、(300,331,332,304)。三次共用一个恒定偏移时,累计区间依次[24,34]、[28,32]、[28,31]。再加入(400,441,442,405),最后一条区间[37,41]与前面无交,输出INCOMPATIBLE,保留导致空交集的记录。
若实际钟在探测之间调整过,应该更换模型或分段重新估计,不能把INCOMPATIBLE藏成四个中点的平均。若外部另承诺参考时刻后的偏移变化率最多1/10,则把[28,32]传播10个真实单位后得到[27,33];这条未来保证不是有限探测自行证明的。
二、把权限期限放在两只不同的钟上
另起租约任务,不将前一节中点当作速率证据。客户端与授予者各有速率范围[9/10,11/10];授予持续时长L=11,所以客户端保守时长为9。请求q从客户端本地100发出,先保存截止109。
实例使用C(t)=100+0.9t、S(t)=700+1.1t。真实2才授予,此时S=702.2,记录服务端期限713.2;正常回复真实4到达,C=103.6。客户端实际可用区间为[4,10),到真实10、C=109必须失效;服务端真实12才到713.2,可改授新客户端。
以精确分数报告所有数值。证明中用的是客户端最慢速率和授予者最快速率;其他合法分段速率路径也必须满足“客户端仍有效 ⇒ 服务端未到期”。枚举路径是代码检查,一般结论仍由两条不等式及g≥t₀给出。
比较三份错误或未完成记录:
- 正常回复4到达后错误地重启9个本地单位,会持续到真实14,与服务端12后的新授权重叠
- 不缩短、从本地100计11个单位,会到真实110/9才停,也晚于12
- 回复直到真实11才到达,此时C=109.9,正确客户端拒绝本次过期回复;重复旧q不能获得新的109以后期限
还要真的尝试服务端提前改授:真实11读712.1仍小于713.2,应拒绝;真实12到等号才允许。申请尚未收到有效回复的客户端没有权限,不能把自己已经设置deadline误当成已被授予。
三、暂停之后,检查效果发生在哪里
客户端真实9时通过期限检查,随后线程暂停到13。若持续时间钟照常走,恢复读到111.7,应拒绝新的本地受保护动作。若暂停连钟也停,旧108.1可能被保留;这不在速率下界合同中,不能把它算作算法在合法输入上的成功例。
另一份轨迹更隐蔽:9时检查确实合法,消息却在13才到外部存储。新持有者从12开始工作,客户端的旧检查不能收回在途消息。先不启用fencing,演示旧41号写覆盖新值;再使用旧页的资源端接口,先完成Activate(42),再让41到达,必须拒绝且保持新值。
在验收表中分别记录“本地权限是否有效”和“资源端是否接受操作”。前者受时间模型保护,后者由效果发生处的原子代际接口保护;只有在资源完成激活后,才能声明该资源已阻挡旧代。此处不实现授予服务的复制、续期或崩溃恢复。
四、给同一消息图重新编号
现在转到HLC。它使用独立的事件模型,允许物理读数倒退,因此不能拿它的l或c去代替上一节有速率下界的持续时间钟。
A/B/C初态都是(0,0)。按下面日志编号事件:
| 事件 | 动作 | 物理读数 | 完整结果 |
|---|---|---|---|
| a | A向B发送m₁ | 100 | (100,0) |
| b | B向A发送m₀ | 90 | (90,0) |
| c | B接收m₁ | 91 | (100,1) |
| d | B向A发送m₂ | 90 | (100,2) |
| e | A接收m₂ | 99 | (100,3) |
| f | C向A发送m₃ | 120 | (120,0) |
| g | A接收m₃ | 101 | (120,1) |
| h | A接收迟到m₀ | 130 | (130,0) |
| i | A再次接收m₂ | 129 | (130,1) |
每行保留旧状态、消息标签、新l的来源、计数分支和新状态。c/g用消息计数加一;e同时越过A旧计数0和消息计数2;h由物理值严格推进并归零;i保留本地l=130并加一。不要只核第一分量,看起来同为100的四个标签必须按计数正确递增。
独立列出进程内边和消息边,例如a→c、d→e、b→h、d→i,再取传递闭包验证全部因果对都严格递增。反例也要保留:d与f之间没有因果路径,但(100,2)<(120,0)。给两个新进程各自一个物理100首事件,它们还可以具有相同(100,0);需要唯一排序时才加稳定身份,不能将破并列解释成通信证据。
五、分开验证物理距离和字段容量
给另一个有真实时间的测试事件图,另外承诺每次物理读数距事件真实时刻≤ε。独立从每个事件全部祖先的物理读数求最大值,对照HLC的l,再验证p≤l≤t+ε及l−p≤2ε。误差界违反时,应只保留因果递增结论,不继续输出“物理距离已保证”。
把物理读数一直固定100,让同一进程继续发生事件。无界整数实现依次(100,0)、(100,1)…;字段上限为3的实现从(100,3)再推进应明确拒绝且保留原状态。错误取模变成(100,0)会直接违反同进程顺序。
不要直接重启清空HLC后继续声称跨崩溃因果安全。本任务不包含恢复,和上一节租约的授予者不得忘记旧期限一样,需要把恢复状态纳入更大的合同。
六、成本和最终交付
单条四戳是常数次有理算术,m条区间求交O(1+m);每资源租约是常数个状态字段与常数次比较;每个HLC事件是常数次最大值和加一。JSON历史、独立闭包、速率路径枚举都是验收成本,Fraction的约分及大整数位操作另算。
交付三份证书及各自前提:四戳的可行区间与空交集,租约两端截止、迟回复和效果边界,HLC事件分支、因果图、并发反例与溢出拒绝。将去/回延迟改成对称、将ρ改小、或将某次HLC物理值抬高,分别重新求结果;这些修改影响不同合同,不能只改一份全局“时间正确”的标签。