Each Pastry node has a unique, 128-bit nodeId. The set
of existing nodeIds is uniformly distributed; this can be
achieved, for instance, by basing the nodeId on a secure
hash of the node’s public key or IP address. Given a message
and a key, Pastry reliably routes the message to the
Pastry node with the nodeId that is numerically closest to
the key, among all live Pastry nodes. Assuming a Pastry
network consisting of N nodes, Pastry can route to any
node in less than dlog2bNe steps on average (b is a configuration
parameter with typical value 4). With concurrent
node failures, eventual delivery is guaranteed unless l=2
or more nodes with adjacent nodeIds fail simultaneously
(l is an even integer parameter with typical value 16).
The tables required in each Pastry node have only
(2b
1) dlog2bNe + l entries, where each entry maps
a nodeId to the associated node’s IP address. Moreover,