We view the Internet as supporting a peer-to-peer information system whose components provide services to one another. We model service providers and consumers as autonomous agents. Agents may provide services or give referrals to one another to help find trustworthy services. Once found, some services may be cached. We describe a flexible caching technique that allows peers to operate autonomously (based on their local policies), accommodates heterogeneity of peers, and enables peers to adapt by choosing policies and neighbors as best suits them. In this approach, cache entries are coupled with metadata, thereby allowing the use of heuristics and flexible queries for more informed searches. The entries that are of interest to more agents are replicated at more peers, providing on-demand performance improvement and fault tolerance.
locating and caching services in an open architecture. Referrals have been used in specific applications (see Section 5). However, we propose that referrals form the key organizing principle for large-scale information systems. Thinking about referrals from this perspective enables a new approach to caching in P2P networks.
Because of the openness of large-scale information systems, instead of looking for correct or relevant results, we look for authoritative sources who can provide correct and relevant results. There is an increased emphasis on locating trustworthy (which we take to include authoritative) resources, who are willing and able to provide the services needed. The authoritative sources could be the originators of the desired information or merely caches of it. We cannot expect to find trustworthy resources through traditional mechanisms for three obvious reasons. One, interesting resources may be invisible to traditional search techniques, thereby yielding low recall. Two, because important information and service needs are personalized, traditional indexing techniques simply lack the understanding and the context to produce the right results, thereby yielding low precision. Three, we cannot rely on regulatory restrictions for ensuring that the services offered are of a suitable quality or that the peers found over the network are trustworthy.
Organization. Section 2 introduces key elements of our model for agent-based P2P information systems. Section 3 discusses the design criteria that should be satisfied by flexible caching techniques. Section 4 describes Marmara, a caching technique that fulfills the criteria of Section 3. Section 5 discusses the relevant literature with respect to our work and motivates directions for further work. 2
We now introduce our basic model. The main parties that interact or principals could be people or businesses. They offer varying levels of trustworthiness and are potentially interested in knowing if other principals are trustworthy. Our notion of services is broad; they can involve serving static pages, processing queries, or even carrying out transactions (although caching makes most sense for retrieving rather than modifying information).
The principals can track each other’s trustworthiness and can give and receive referrals to services. Referrals are common in distributed systems, e.g., in the domain name system (DNS), but are usually given and followed in a rigid manner. By contrast, the referrals here are flexible—reminiscent of referrals in human dealings. Importantly, by giving and taking referrals, principals can help one another find trustworthy parties with whom to interact.
The principals are autonomous. That is, we do not require that a principal respond to another principal by providing a service or a referral. When they do respond, there are no guarantees about the quality of the service or the suitability of a referral. However, constraints on autonomy, e.g., due to dependencies and obligations for reciprocity, are easily incorporated. Likewise, we do not assume that any principal should necessarily be trusted by others: a principal unilaterally decides how to rate another principal.
Principals must be represented computationally. Because of the above properties of
principals, they are ideally represented via agents. Agents are persistent computations
that can perceive, reason, act, and communicate [
In abstract terms, the principals and agents act in accordance with the following protocol. When a principal desires a service, or when its agent anticipates the need for a service, the agent begins to look for a trustworthy provider for the specified service. The agent queries some other agents from among its neighbors, which are a small subset of the agent’s acquaintances. A queried agent may offer its principal to perform the specified service or, based on its referral policy, may give referrals to agents of other principals. The querying agent may accept a service offer, if any, and may pursue referrals, if any.
Each agent maintains models of its acquaintances, which describe their expertise
(i.e., the quality of the services they provide) and sociability (i.e., the quality of the
referrals they provide). Both of these elements are adapted based on service ratings
from the agent’s principal. Using these models, an agent applies its neighbor selection
policy to decide which of its acquaintances to keep as neighbors. Key factors include
the quality of the service received from a given provider, and the resulting value that can
be placed on a series of referrals that led to that provider. In other words, the referring
agents are rated as well. The interests and expertise of the agents are represented as
term vectors from the vector space model (VSM) [
In some settings, services can easily be cached. For example, consider a knowledge management setting where the idea for “consuming” knowledge services might be to acquire expertise in the given domain. When an agent asks a question, it gets an answer that can be duplicated. For example, if agent learns about car history trivia from , can then answer the same question by just giving the answer gave. Thus, in addition to generating answers to queries on demand, the answers can also be cached at other peers. Caching aids the search since a peer who is looking for an item can find it in a nearby cache rather than having the provider generate the item afresh. 3
For information systems to work effectively, the caching techniques should satisfy the following criteria.
– Peer Autonomy. Autonomy of a peer is important in two respects. First, a peer should be allowed to choose who it will interact with, and how it will carry out its interactions. Second, it should be allowed to cache items that are useful to itself rather than caching items to serve others. – Peer Heterogeneity. A peer can offer services and follow policies distinct from all others. The difference in policies may result in two peers providing the same service with varying qualities. Put another way, node heterogeneity constitutes a natural way to model varying trustworthiness of peers. By accommodating heterogeneity, an information system also accommodates the fact that the trustworthiness of the peers can be different. – Neighbor Choice. Some of the peers in the system can be more useful than others, because of the type and quality of the services they provide. A peer should be able to modify its choice of neighbors so that the useful peers are contacted before others. – Item Metadata. It is common to identify a data item by a unique identifier. In addition to the identifier, useful information about the item such as the timestamp of the item or the keywords related to it should be made explicit as metadata. This captured metadata can be utilized to form expressive search queries. – Search Criteria. The simplest way to find a data item is through a unique identifier.
In many real settings, the users do not have access to these identifiers, but rather information about the item that is sought. Thus, the caching techniques should allow more expressive searches to be formulated. This has two consequences. First, the items should be searched through metadata, like a list of keywords. Second, trade-offs between different subsets of the metadata should easily be captured. – Heuristics. Ideally, data items should be located by contacting as few peers as possible. In order to achieve this, heuristics should be used to exploit the metadata of the items or the identities of the peers. 4
Marmara is our flexible caching technique. In Marmara, a cache consists of a set of entries that contain the data item as well as some accessing information about the data item. Unlike traditional P2P approaches, which model the data item through a unique global identifier only, we represent it with metadata. Each data item has fields for its name, author, last modification date, version, and a list of domains that it belongs to. If an agent knows the name of the item it is looking for, then it can search for the item with the name field. Mostly, a user would have a list of keywords in mind but not know the exact name of the data item. Our approach allows queries to be formulated with keywords that are matched against the list of domains listed in the metadata. In other words, keywords make up a query vector and the data item is the answer for the query.
The access data of an entry contains at least the timestamp of the last access to that data item. Depending on an application, further information about number of accesses to the item, or peers that access this information can be kept. The date for the last access is used to decide which item to remove from the cache when we run into a space limit.
Each agent can decide on the size of its cache. That is, an entry can stay in the cache as long as it is not manually deleted or automatically replaced by another entry based on the replacement algorithm in use. An entry can specify an expiration date for an item. This expiration date is not meant to be a rigid limit on the life of the item, but a signal to update the data item. A peer is free to use an expired item or find an updated version.
The peers are free to insert items into their caches at their own interest. In other words, there are no rules governing what items each peer can have. The insertion into a cache results from two different operations. First, the user may manually insert an item into the cache, thereby making it also accessible to other peers. Initially, we would expect all items to be inserted this way. Second, a peer may get the item from some other peer’s cache, and decide to keep it, say, because it might be useful in the future.
Many peer-to-peer systems—Chord [
An agent can delete any of the entries in its cache for different reasons such as lack of
space, lack of interest in the item, and so on. Just as each peer can delete its cached
copy, the owner can also delete the original item. Even if the owner of an entry deletes
the original copy, the peers that have a cached copy of the item are not forced to remove
that entry from their caches. Thus, an entry may reside on two caches at one timepoint
and later be deleted from one but still remain on the second one. This contrasts with
Plaxton et al.’s [
In addition to the manual delete, entries in the cache can also be automatically deleted to restore space in the cache. If there is no space left in the cache, when a new entry comes in, then one of the existing entries is replaced with the new entry. We employ the least recently used (LRU) replacement policy. However, we only consider uses by the principal. That is, the cache replaces the entry that has not been accessed for the longest time period by the agent that owns the cache. This ensures that only the entries that the principal is using are kept in the cache. 4.3
An agent can formulate queries in different ways, describing and specifying constraints on the information sought. Different applications can utilize a combination of these queries based on the requirements of the application.
– Keyword. The agent supplies a list of keywords that are used to form a query vector.
This gives flexibility to the search, in that the source peer does not need to know the exact name or the unique identifier of the data item it is looking for. The requested item is returned without any concern of the cost for the search or the version of the returned item. (1) – Cost-constrained. In addition to supplying a list of keywords, the agent also specifies how much it is willing to spend to find this item (assuming that there is an associated cost for searching the data item). This allows an agent to trade quality for cost. An agent that is looking for a data item, but is willing to spend only a little on it, can get an old version of the data item. – Version-constrained. With the cost-constrained query, an agent cannot specify which versions of the item are acceptable. Here, though, it can specify the acceptable timestamp of the item. This is especially useful when there is no constraint on the cost—the agent is willing to spend anything, but wants to get at least a certain version of the item. – Cost-version-constrained. This is a combination of the previous two queries. In addition to the keywords, both the acceptable cost and the version are specified. The same example, with a timestamp of 1 hour, for example, means that the agent is looking for the version of the data item that is at most one hour old and it is only willing to spend a certain amount. Obviously, a successful search should satisfy the cost constraint and the returned data item should satisfy the version constraint. – Exact. If the user knows the unique identifier of the item it is looking for, then it does not need to supply any keywords. The query vector can then be modeled as the interest vector of the agent. Note that this vector will only be used in searching for peers in the graph, not for matching the answers. Thus, only answers that have the unique identifier are returned.
An agent will start the search by sending a query to its neighbors. When the neighbor
gets the query, it searches its own cache. If it does not have the item, it can either refer
some of its neighbors or, if it is also interested in having the data item, it can start a
new search for the data item itself, cache a copy, and return it to the original requesting
agent as well. If the agent decides to refer, it uses its referring policy to choose among
its neighbors. The referral policies take into account the expertise of the agents. One
way to choose the neighbors is through the capability metric, which measures how
sufficient the expertise vector is for a given query vector [
"!$# Y Z>[ \>]AZ>[ ^7]AZ>[ _‘Fa\G[ Zbcd #"$ ˛ K)L+MONQP SR1P2L+T5U7V7W X)W M:V ˝ ˜ ; — ¸ ˚ae¤˚ Øae¤˚ ºŒ Ł £‰˚Æ Sı1ªT&Æ 5ł£ØŁØŒ ; <>= ?>@A<>= B7@A<>= CDFE?G= T ø oe˚ߣ¤oe˚ß P¤oe˚ß Sß oe <HIJ % & ˇ ’)(+*!,.- 0/1-2(+3547678 9)8 *:6 ! item, it can generate a version-constrained query to say that it is willing to pay (wait) whatever it takes to get an at most 30 minute old version of the item. 4.5
Owners of data items can update them. Ideally, it is desirable to ensure that all caches that contain the particular entry are updated when one is updated. Heuristics based on circulating updates in the network turn out to be too costly, especially in distributed systems involving a large number of agents and a large number of items. For this reason, instead of maintaining strictly coherent caches, we let entries be timestamped by their modification date. This allows different versions of the same items to exist in different caches in the system. Obviously, when a cache gets more than one version of the same entry, it can get rid of the previous version and only save the most recent one. In addition, we propose several update models that will be useful depending on the importance of how recent the data item is.
Subscribe Under this model, when a peer requests a data item from a provider, it can subscribe for further updates from this provider. When the requester subscribes for the item, the provider is responsible for notifying the requester for any updates on that item. The requester can obtain the new version of the item whenever it receives an update notification. Alternatively, the requester can obtain the updated version of the item only when there is a request for the item (from its principal or from another peer).
This update model ensures that the requester will always have the up-to-date version of a data item with respect to a provider. In other words, if the provider is the actual updater of the item, then the requester will always have the most recent version of the item. On the other hand, if the provider is not the actual updater of the item, it might not be getting the updated version of the item periodically. Thus, there may still be updates that the provider is missing, all of which will also be missed by the requester.
This leads to the identification of authoritative peers in the system. The peer that updates a data item is, by definition, an authority for the item. The peers that mirror the updates promptly can also serve as authorities for other peers. From a requester’s point of view, there is no difference between the actual authority for a data item and these mirroring peers. Therefore, locating any one of these authoritative peers is enough to guarantee the retrieval of the most up-to-date data item.
Invalidate The subscription model is useful when a peer needs to have an up-to-date version at all times. On the other hand, a peer may need a data item, but not care for updates. In this model, the requester is sent a notification of only the first update and not any later updates. The requester would know that its copy was stale. It may look for an updated version when it needs the item, or (knowingly) use the invalidated copy. When an agent gets an answer to its query, it can request to get updates with one of the methods described. The service provider does not have to fulfill this request since not all service providers are required to support these update models. 5
Referral networks are a natural way for people to go about seeking information [
One reason to believe that referral systems would be useful is that referrals capture
the manner in which people normally help each other find trustworthy authorities. The
importance of referrals to interpersonal relationships has long been known [
MINDS, based on the documents used by each user, was the earliest agent-based
referral system [
Our referral-based approach takes an adaptive, agent-based stance on peer-to-peer
computing. Below, we compare some related approaches based on the design criteria
of Section 3. Piazza is a P2P system where each peer is a member of a sphere of
cooperation and is assigned a role of data origin, storage provider, query evaluator, or query
initiator [
In Piazza, when a peer receives a materialized view of a query, it pushes the view to its neighbors who then pushes it to their neighbors, and so on. Thus many peers —both interested and disinterested— receive the view but it also causes traffic. In our approach, we only push information to the peers that have shown interest in it by subscribing.
Similar to our approach, Piazza assumes that each data has an origin that is responsible for updates. The data in caches expire after a fixed period of time. This is useful when the expected expiration dates can be estimated. Our approach accommodates expiration dates like this, as well as explicit invalidation and subscription models. Piazza does not seem to keep metadata for data items and the type of queries allowed by the system are not discussed.
OceanStore is a global storage application that uses a peer-to-peer network [
When answering a query, the nodes locate and prefetch similar items with the idea that these items will probably be accessed as well. OceanStore can only be queried with the name or the globally unique identifier of the item. e file in the system is divided into blocks, which are automatically replicated on the
Cooperative File System (CFS) [
PeerOLAP design an adaptive P2P system for caching online analytical processing
queries [
Recently, several peer-to-peer network architectures have been proposed [
Past [
Autonomy
geneity Choice
Heuristics
Directions. The Marmara prototype is being implemented. In future work, we will evaluate the performance of Marmara, especially with respect to various policies and load distributions. We will also model richer properties underlying the connectivity among the peers, e.g., communication cost and available bandwidth. These properties affect how efficiently and effectively peers can be located. The overall idea is to understand the trade-offs between performance on the one hand and higher-level descriptions and local controls on the other.