“Chord指表查找把这一限制落实为可逐跳执行的例子：节点只读自己的successor和幂二指针，把请求交给目标之前更靠前的成员。在冻结且正确的后继环上可证明返回负责节点；完整成员表只供初始化…”
形式陈述
已知放置公式，但每台机器没有整张表
一致性哈希环规定键k归顺时针第一个坐标≥k的节点。若所有客户端都有完整有序成员表，可以本地二分；Chord解决另一项任务：在消息传递模型中，每个节点只持有少量指针，通过转交查询求同一个后继答案。[1, §IV.C–D]
本页固定m≥1、M=2^m，以及非空、坐标互异的稳定成员集。查找期间成员不加入、退出或失败，消息可靠且最终交付。每个节点u的successor必须是全环紧接u的下一成员；唯一成员的successor指自己。返回的是负责节点身份，不包含取值、复制、事务或成员维护。
完整指表的第i项为
这里successorKey是“不小于目标”的环后继，节点自己的successor则是“严格在自己之后”的成员后继；在唯一成员情形二者都回到自己。不得在多成员环把successorKey(u)=u误当作节点的下一成员。
每一步只读取当前节点的状态
定义顺时针距离δ(a,b)=(b−a) mod M，值在0,…,M−1。节点u处理查询k时：
- 若k=u，返回u；若successor=u，在正确后继前提下整环只有这一成员，返回u
- 若0<δ(u,k)≤δ(u,successor)，返回successor
- 否则从指表里选满足0<δ(u,v)<δ(u,k)的节点v中，δ(u,v)最大的一个，向v转交查询；没有这样的指表项时转交正确successor
步骤3不把越过k、指回自己或落在反方向的指针当作进展。完整指表第一项本来就是successor；显式后备分支用于后文的不完整/陈旧指表。结果沿调用链返回，或由等价的迭代查询驱动器继续下一跳。
直觉
后继保证不漏成员，长指针负责少走路
只沿正确successor也能找到答案：每次走到环上下一成员，直到当前节点与后继把k夹住。它可能访问几乎全部N个成员，但不会跳过真正owner。
幂二指表加入更远的捷径。节点知道自己前方1、2、4、8……个坐标处的首个成员，可以从这些指针中挑仍位于目标之前且最靠前的一个。指表记录的是成员，不是那些幂二起始坐标本身；许多起始坐标可以落到同一个成员。
减半应测到目标前驱，而不是随意测到k
令p为k之前最后一个成员，不把恰等于k的成员算入此前驱。只要当前节点u还未能返回owner且u≠k，p就在u到k的开区间上；转交节点总位于u之后、p及之前，因此不会绕过p。
若u≠p，记D=δ(u,p)>0，选择i使2^i≤D<2^(i+1)。因为p本身是一个成员，完整指表的f=successorKey(u+2^i)必落在从u+2^i到p的闭区间，因而f是合法前进候选。实际所选v至少和f一样靠前，所以
D恰为2^i时新距离为0。于是至多m次转交到达p，再由正确successor返回owner。这里分析的是到成员p的距离；例如成员0、1、16，u=0、k=15时，第一步只能到1，到k的数字距离从15变14，并没有减半，但下一步已经可以返回16。
原论文的O(log N)高概率结论还使用成员位置的随机分布；本页对任意固定合法m位成员布局证明的是O(m)确定跳数。不能仅因一张指表有幂二偏移，就在任意稀疏或对抗布局上宣告O(log N)。[1, Theorem IV.2]
例子与边界
m=5时的整张局部指表
空间0,…,31，成员为1、4、8、14、21、28。每列起点依次为u+1、u+2、u+4、u+8、u+16，按32绕回。
| u | finger[0] | finger[1] | finger[2] | finger[3] | finger[4] |
|---|---|---|---|---|---|
| 1 | 4 | 4 | 8 | 14 | 21 |
| 4 | 8 | 8 | 8 | 14 | 21 |
| 8 | 14 | 14 | 14 | 21 | 28 |
| 14 | 21 | 21 | 21 | 28 | 1 |
| 21 | 28 | 28 | 28 | 1 | 8 |
| 28 | 1 | 1 | 1 | 4 | 14 |
从4查31：4的最大合法前进指针为21；21的最大合法前进指针为28；28发现31落在(28,1]的绕回区间，返回owner1。实际处理查询的节点依次4→21→28，不需要让1再处理一次“求身份”请求。
从1查27，1→21后返回28；从28查0，立即返回1；从14查14，直接返回自己；从8查3，路径8→28→1，最后返回4。后两例分别检查相等和越过零点的区间规则。
指表变短，与后继错误是不同故障
保持成员和所有successor正确，只让每份指表剩自己的successor。从4查31会走4→8→14→21→28，答案仍是1，跳数变多。更一般地，只要候选指针仍指当前活成员且严格位于(u,k)，就保持前进；没有捷径时走successor，最多沿N个成员处理，可能退化到O(N)。此时不再具有完整指表的减半保证。
反过来，把28的successor错误设成4，却仍让成员1留在环内。从28查0会发现0∈(28,4]而返回4，漏掉真正的owner1。即使所有转交看起来都“向前”，错误的终止区间也会制造错误答案。因此正确successor是本定理的条件，不能拿指表搜索结果反过来当作它已经正确的证明。
若一次转交的地址不可达，协议尚未完成。有限超时不能证明该节点已退出，也不能让调用方擅自改成“我目前能联系到的第一个就是owner”。下载器把这种事件和跳数预算耗尽记为UNKNOWN，保留已走路径；这是观察出口，不是成功的成员重配置。
推论与应用
通信跳数与本地扫描分开计
每个节点保存m项指表和一个successor，状态O(m)。本页透明实现逐项扫描求最大的合法前进指针，每个处理节点O(m)整数比较；完整指表至多O(m)个处理节点，故本地总工作O(m²)、消息转交数O(m)。不能把跳数直接当作处理器总工作。
若指表只有s_u项，一条访问路径上的本地扫描工作为O(Σ(1+s_u))；保存h步完整候选日志需O(Σ(1+s_u))输出，不只是h个节点名。简化追踪只保存选中节点和终止理由时才有O(h)日志。下载器的故障实验还把F个不可达地址建成集合，预处理另需期望O(F)时间和空间；它不属于节点本地查找决定。
核验器用一份完整成员表离线生成标准指表，再通过只读当前节点局部状态的查找器执行。这张全表是测试初始化与独立oracle，不是查找器在每跳偷偷读取的共享目录。批量建N份指表用N m次全表后继查询，另付排序和O(Nm)存储；真实系统怎样维护这些表属于另一协议。这里按整数比较和节点索引常数访问计费，Python字典/集合为期望成本，大整数位运算另计。
稳定查找证明不承担动态修复
节点加入、离开和失败会使successor也变旧，需要维护算法及其不变量。Zave明确指出原始Chord维护规格在原假设下并不保证所声称的最终可达性，并给出修正规格与证明。[2, §I–II] 本页没有实现该维护协议，因此不从静态查找推出“任意并发加入和故障都会自动收敛”。
放置与查找终点分别验收完整指表、只有后继的降级状态、错误后继反例及不可达出口。能返回一个节点号，还必须检查它等于当前冻结成员表定义的后继；而位置正确之后，数据是否已迁移仍回到放置单元的另一份责任。
参考资料
- Stoica、Morris、Liben-Nowell、Karger、Kaashoek、Dabek、Balakrishnan，Chord: A Scalable Peer-to-peer Lookup Protocol for Internet Applications，2003作者稿，§IV.C–D、Figure5、TheoremIV.2，PDF pp.4–6：后继查找、局部指表和到目标前驱的距离论证。本文0基指表、相等出口、有限预算及错误后继反例为明确教学接口。
- Pamela Zave，Reasoning About Identifier Spaces: How to Make Chord Correct，2017，所读2019修订稿v2，§§I–II：原维护协议的正确性问题、理想环和维护模型。修正维护仍有通信、存活后继与初始化条件，不能被本页的静态查找实验代替。