A peer-to-peer cache architecture stores peer address certificates in different
cache segments according to the number of IDs being stored and their relative distance
in the peer name space. The cache instantiates regions of decreased range and increased
granularity as additional information from close peers is learned. In a large peer
cloud where the number of instantiated IDs is not known, each succeeding cache
region covers one tenth of the preceding cache region. For peers with multiple
IDs registered locally, the segmented cache of the present invention combines overlapping
segments of the same granularity to eliminate the duplication of information that
would otherwise occur. A cache tree, an instantiated segment tree, and an uninstantiated
segment tree are arranged in red-black trees to simplify the search and proper
placement and instantiation of information.
