As the adoption of grid technology moves from science to industry, new requirements arise. In todays grid middlewares, the notion of paying for a job is a secondary requirement. In addition, the concept of selling computational power on a market is not established. On the other hand, the lack of billing capabilities hinders the commercial adoption. In this paper, we present our resource allocation protocol that suits the needs of commercial solution providers. We have developed an auction-based resource broker which uses a distributed agent infrastructure to communicate the user's requirements to resource providers and monetary prices back. The protocol has been formally verified and guarantees certain properties - for example, we can guarantee that the right stakeholder is billed for a job.

Scalability constitutes a key property of Peer-to-Peer overlay networks. Recent advances that improve scalability include super-peer infrastructures and network coordinates. As an integral part of an upcoming middleware for distributed computing, we have developed a mechanism that builds and maintains a super-peer overlay network in a decentralized, self-organized way, using network coordinates to facilitate inter-peer distance estimation. We discuss the benefits of super-peer infrastructures in the context of Desktop Grids and present the outcome of experiments conducted on PlanetLab to observe the constructed topology's behavior in a practical environment.

Scalability constitutes a key property in Peer-to-Peer environments. One way to foster this property is the introduction of super-peers, a concept which has gained widespread acceptance in recent years. We solve the problem of selecting super- peers in a distributed, scalable, self-organized way, supported by network coordinates. To this end, we present an exact optimization model and introduce a distributed algorithm that addresses the problem in a decentralized fashion. By means of simulation using actual Internet distance measurements, we demonstrate the savings in communication cost attainable by our super-peer topology construction and maintenance scheme.

Scalability constitutes a property of particular interest when investigating peer-to-peer overlay behavior. Recent advances that improve scalability include super-peer infrastructures and network coordinates. To this end, we introduce a lightweight simulation framework that focuses on peer-to-peer topology construction supported by network coordinates and optionally, super-peers. One of the design goals has been a straightforward way to re-use simulation code in practical applications. We illustrate the utility of our simulation framework by means of a comprehensive application case study that compares different network coordinates generation mechanisms in the context of a distributed super-peer topology construction effort.

Network coordinates facilitate delay estimation in largescale networks. In particular, they support the creation of peer-to-peer-based desktop grid overlay structures. Landmark-based approaches to computing such coordinates have gained widespread acceptance in recent years. Several of these approaches produce coordinates by solving sequences of nonlinear unconstrained optimization problems. Apparently, Simplex Downhill has been the preferred method for solving such problems in the network coordinates context. In this paper, we propose a replacement for this algorithm. Our method works more accurately than Simplex Downhill and refrains from imposing additional requirements on the objective function.

In this paper, we present an efficient algorithm for performing a broadcast operation in P2P grids. Our approach combines the advantages of two overlay architectures: Chord-like regular networks and unstructured networks with epidemic communication. The resulting meta architecture provides higher robustness as well as higher speed and lower message complexity than appropriate base methods. Preliminary experiments show the viability of introduced approach.

Grid resource allocation is a complex task usually solved by systems relying on a centralized information system. In order to create a lightweight scheduling system, we investigated the potential of auctions for resource allocation. Each resource provider runs an agent bidding on the execution of software with respect to local restrictions. This way, the information system becomes obsolete. In addition, each provider can implement different bidding strategies in order to reflect his preferences.

Memetic algorithms (MAs) have demonstrated very effective in combinatorial optimization. This paper offers explanations as to why this is so by investigating the performance of MAs in terms of efficiency and effectiveness. A special class of MAs is used to discuss efficiency and effectiveness for local search and evolutionary meta-search. It is shown that the efficiency of MAs can be increased drastically with the use of domain knowledge. However, effectiveness highly depends on the structure of the problem. As is well-known, identifying this structure is made easier with the notion of fitness landscapes: the local properties of the fitness landscape strongly influence the effectiveness of the local search while the global properties strongly influence the effectiveness of the evolutionary meta-search. This paper also introduces new techniques for analyzing the fitness landscapes of combinatorial problems; these techniques focus on the investigation of random walks in the fitness landscape starting at locally optimal solutions as well as on the escape from the basins of attractions of current local optima. It is shown for NK-landscapes and landscapes of the unconstrained binary quadratic programming problem (BQP) that a random walk to another local optimum can be used to explain the efficiency of recombination in comparison to mutation. Moreover, the paper shows that other aspects like the size of the basins of attractions of local optima are important for the efficiency of MAs and a local search escape analysis is proposed. These simple analysis techniques have several advantages over previously proposed statistical measures and provide valuable insight into the behaviour of MAs on different kinds of landscapes.

With the invention of microarray technology, researchers are capable of measuring the expression levels of ten thousands of genes in parallel at various time points of the biological process. During the investigation of gene regulatory networks and general cellular mechanisms, biologists are attempting to group genes based on the time-depending pattern of the obtained expression levels. In this paper, we propose a new memetic algorithm - a genetic algorithm combined with local search-based on a tree representation of the data - a minimum spanning tree minus; for clustering gene expression data. The combination of both concepts is shown to find near-optimal solutions quickly. Due to the minimum spanning tree representation of the data, our algorithm is capable of finding clusters of different shapes. We show that our approach is superior in solution quality compared to classical clustering methods.

The fitness landscape of the graph bipartitioning problem is investigated by performing a search space analysis for several types of graphs. The analysis shows that the structure of the search space is significantly different for the types of instances studied. Moreover, with increasing epistasis, the amount of gene interactions in the representation of a solution in an evolutionary algorithm, the number of local minima for one type of instance decreases and, thus, the search becomes easier. We suggest that other characteristics besides high epistasis might have greater influence on the hardness of a problem. To understand these characteristics, the notion of a dependency graph describing gene interactions is introduced. In particular, the local structure and the regularity of the dependency graph seems to be important for the performance of an algorithm, and in fact, algorithms that exploit these properties perform significantly better than others which do not. It will be shown that a simple hybrid multi-start local search exploiting locality in the structure of the graphs is able to find optimum or near optimum solutions very quickly. However, if the problem size increases or the graphs become unstructured, a memetic algorithm (a genetic algorithm incorporating local search) is shown to be much more effective.

In this paper, a fitness landscape analysis for several instances of the quadratic assignment problem (QAP) is performed, and the results are used to classify problem instances according to their hardness for local search heuristics and meta-heuristics based on local search. The local properties of the fitness landscape are studied by performing an autocorrelation analysis, while the global structure is investigated by employing a fitness distance correlation analysis. It is shown that epistasis, as expressed by the dominance of the flow and distance matrices of a QAP instance, the landscape ruggedness in terms of the correlation length of a landscape, and the correlation between fitness and distance of local optima in the landscape together are useful for predicting the performance of memetic algorithms-evolutionary algorithms incorporating local search (to a certain extent). Thus, based on these properties, a favorable choice of recombination and/or mutation operators can be found. Experiments comparing three different evolutionary operators for a memetic algorithm are presented.

A memetic algorithm (MA), i.e. an evolutionary algorithm making use of local search, for the quadratic assignment problem is presented. A new recombination operator for realizing the approach is described, and the behavior of the MA is investigated on a set of problem instances containing between 25 and 100 facilities/locations. The results indicate that the proposed MA is able to produce high quality solutions quickly. A comparison of the MA with some of the currently best alternative approaches-reactive tabu search, robust tabu search and the fast ant colony system-demonstrates that the MA outperforms its competitors on all studied problem instances of practical interest.