CUP Trees

Figure 2 shows a snapshot of CUP in progress for a network with seven peer nodes. The left half of each node shows the set of keys for which the node is the authority. The right half shows the set of keys for which the node has cached index entries as a result of handling queries. For example, node C owns K1 and K2 and has cached entries for K3, K4, and K5.

The process of querying for a key K and updating cached index entries pertaining to K forms a tree which we refer to as the Real CUP Tree. This tree, denoted R(A,K), is similar to an application-level multicast tree and has as its root the authority node A for K. The exact structure of R(A,K) depends on the actual workload of queries for K. The branches of the tree are formed by the paths traveled by queries from other nodes in the network. For example, in Figure 2, the tree R(C,K1) has grown branch {F, D, C} as the result of a query for K1 at node F. Updates for K1 originate at the root (authority node) C and travel down the tree to interested nodes A, D, E, and F. The entire workload of queries for all keys results in a collection of criss-crossing Real CUP Trees with overlapping branches.

We define the Spanning CUP Tree for key K, S(A,K) as the tree that contains all possible query paths for K. This is the tree that would be generated by issuing a query for K from every node in the peer-to-peer network. For example, in Figure 2, S(C,K1) is rooted at C (level 0), has nodes A, B, D, E at level 1, and nodes F and G at level 2.

Figure: CUP Trees