On the evaluation of services selection algorithms in multi-service P2P grids

It has been shown that the use of a reciprocation mechanism in peer-to-peer grid systems which provide multiple services to their users is an efficient way to prevent free-riding and, at the same time, to promote the clustering of peers that have mutually profitable interactions. However, when peers are subject to resource limitations, they may be unable to offer all possible services and shall select a subset of services to offer. Previous work showed that the overall profitability of a peer is strongly dependent on the set of services it offers. Thus, the use of an appropriate services selection algorithm is crucial to yield better profitability to peers. Clearly, evaluating the efficiency of services selection algorithms is an important aspect in the search for suitable solutions for this problem. Unfortunately, due to the complexity and inherent non-determinism of the system, it is normally intractable to compute optimal solutions even for small systems. This renders the task of evaluating the performance of practical heuristic-based algorithms difficult. This work aims to fill in this gap by providing a cheaper evaluation method. The methodology we propose maps the services selection problem into the well-known knapsack problem, making brute force techniques affordable for reasonably large systems. Then, by immersing the algorithms under evaluation on a similar setting, it is possible to assess their efficiency compared to an optimal solution. We show how the methodology can be used by evaluating two services selection heuristics.