Because an integer in [0, 2 n ⫺ 1] can be expressed as an n-bit binary number in a DHT, each key can be expressed as k = (k 0 , k 1 , . . . , k n–1 ), and each peer iden-tifier can be expressed p = (p 0 , p 1 , . . . , p n–1 ). Let’s now define the XOR distance between a key k and peer p as
Describe how this metric can be used to assign (key, value) pairs to peers. (To learn about how to build an efficient DHT using this natural metric, see [Maymounkov 2002] in which the Kademlia DHT is described.)
For each key, we first calculate the distances (using d(k,p)) between itself and all peers, and then store the key in the peer that is closest to the key (that is, with smallest distance value).