public keys, nodes with adjacent node identifiers may be farther apart geographically. Pastry also assumes a circular identifier space and each node has a list containing L/2 successors and L/2 predecessors known as the leaf set. A node also keeps track of M nodes that are close according to some metric other than the identifier space, such as network delay. This set is known as the neighborhood set and is not used for routing but for maintaining locality properties. Another node state is the main routing table. It contains |log26 (N) rows and 2b - 1 columns. L, M and b are system parameters. Node identifiers are represented as string of digits of base 2b. In the first row, the routing table of a node contains node identifiers that have a distinct first digit. A node needs to know 2b - 1 nodes for each possible digit except its own. In the second row, the routing table of a node with identifier n contains 2b - 1 nodes that share the first digit with N but differ in the second digit. The third row contains nodes that share the first and second digit of n but differ in the third and SO on. Figure 9.4 illustrates how the identifier space is partitioned with this scheme. For each of the constraints about the node identifiers contained in a routing table, there exist many satisfying nodes. The node with the lowest network delay or the best according to some other criteria is included in the routing table. An item in Pastry is stored at the node that is numerically closest to its id. Such a node will have the longest matching prefix. To locate the clos- est node to an identifier x, a node n checks first if x falls within the range of node identifiers covered by its leaf set. If so, it is forwarded to such a node. Otherwise, the lookup is forwarded to the node in the interval that x belongs to, that is to a node that shares more digits than the shared prefix between n and X. If no such node is found in the routing table of N, the lookup is forwarded to the numerically closest node to X. With the matching of one digit of