The following terms give some background on how structured peer-to-peer networks perform their indexing and lookup operations. These help clarify the description of CUP over structured networks in the next section.
Node: This is a node in the peer-to-peer network. Each node periodically exchanges ``keep-alive'' messages with its neighbors to confirm their existence and to trigger recovery mechanisms should one of the neighbors fail.
Global Index: A fundamental operation in a peer-to-peer network is that of locating content. The basic idea in structured peer-to-peer networks is that a hashing scheme maps keys (names of content files or keywords) onto a virtual coordinate space using a uniform hash function that evenly distributes the keys to the space. The coordinate space serves as a global index that stores index entries which are (key, value) pairs. The value in an index entry is a pointer (typically an IP address) to the location of a node that stores a replica of the content associated with the entry's key. There can be several index entries for the same key, one for each replica of the content.
Authority Node: Each node N in a structured peer-to-peer system is dynamically allocated a subspace of the coordinate space (i.e., a partition of the global index) and all index entries mapped into its subspace are owned by N. We refer to N as the authority node of these entries. Replicas of content whose key corresponds to an authority node N send birth messages to N to announce they are willing to serve the content. Depending on the application supported, replicas might periodically send refresh messages to indicate they are still serving a piece of content. They might also send deletion messages that explicitly indicate they are no longer serving the content. These deletion messages notify the authority node to delete the corresponding index entry from its local index directory.
Local index directory: This is the subset of global index entries owned by a node.
Search Query: A search query posted at a node N is a request to locate a replica for key K. The response to such a search query is a set of index entries that point to replicas that serve the content associated with K.
Search/Routing Mechanism: In structured networks, when a node issues a query for key K, the query will be routed along a well-defined path with a bounded number of hops from the querying node to the authority node for K. The routing mechanism is designed so that each node on the path hashes K using the same hash function to deterministically choose which of its neighbors will serve as the next hop. The CUP protocol is aware of but neither affects nor is affected by the underlying routing mechanism.
Query Path for Key K: This is the path a search query for key K takes. Each hop on the query path is in the direction of the authority node that owns K. If an intermediate node on this path has unexpired entries cached, the path ends at the intermediate node; otherwise the path ends at the authority node. The reverse of this path is the Reverse Query Path for key K.
PCX: Recently, researchers have suggested caching metadata with expiration times along the reverse query path [2,3,4,5] as the query response is propagated down to the querying node.
Cached index entries: This is the set of index entries cached by a node N in the process of passing up queries and propagating down query responses for keys for which N is not the authority. The set of cached index entries and the local index directory are disjoint sets.
Lifetime of index entries: Each index entry cached at a node has associated with it a lifetime during which it is considered fresh and after which it is considered expired.