The Internet has witnessed a steady and widespread increase in available idle computing cycles and computing resources in general. Such available cycles simultaneously allow and foster the increase in development of existing and new computationally demanding applications, driven by algorithm complexity, intensive data processing, or both. Available cycles may be harvested from several scenarios, ranging from college or office LANs, cluster, grid and utility or cloud computing infrastructures, to peer-to-peer overlay networks. Existing resource discovery protocols have a number of shortcomings for the existing variety of cycle sharing scenarios. They either (i) were designed to return only a binary answer stating whether a remote computer fulfills the requirements, (ii) rely on centralized schedulers (or coherently replicated) that are impractical in certain environments such as peer-to-peer computing, (iii) they are not extensible as it is impossible to define new resources to be discovered and evaluated or new ways to evaluate them. In this paper we present a novel, extensible, expressive, and flexible requirement specification algebra and resource discovery middleware. Besides standard resources (CPU, memory, network bandwidth,...), application developers may define new resource requirements and new ways to evaluate them. Application programmers can write complex requirements (that evaluate several resources) using fuzzy logic operators. Each resource evaluation (either standard or specially coded) returns a value between 0.0 and 1.0 stating the capacity to (partially) fulfill the requirement, considering client-specific utility depreciation (i.e., partial-utility, a downgraded measure of how the user assesses the available resources) and policies for combined utility evaluation. By comparing the values obtained from the various hosts, it is possible to precisely know which ones best fulfill each client's needs, regarding a set of required resources.

Cycle sharing over the Internet has increased in popularity during the last decade, with increasingly powerful machines being made available to existing projects. In this paper, we present GiGi-MR, a framework that allows non-expert users to run CPU-intensive jobs on top of volunteer resources over the Internet. GiGi-MR has several distinctive features: it allows non-expert users to easily partition their jobs in several parallel tasks; such Bag-of-Tasks (BoT) are executed in parallel as a set of MapReduce applications; the volunteer resources that provide the best match for the tasks being executed are chosen (using attenuated bloom filters); it provides a portable checkpointing fault-tolerance mechanism based on virtualization; it does not rely exclusively on a central server (or servers) at all times (thus minimizing the bottleneck effect); it deals with malicious participants (possibly byzantine) using an efficient partial replication mechanism to validate the results obtained; and it is compatible with BOINC (one of the most popular open-source software platforms for computing using volunteered resources). We describe GiGi-MR’s architecture and evaluate its performance by executing several MapReduce applications on a wide area testbed. Furthermore, we use micro-benchmarks to assess each one of GiGi-MR’s components independently. The system’s overhead is minimal. When compared to an unmodified volunteer computing system, GiGi-MR obtains a performance increase of over 60 % in application turnaround time, while reducing the bandwidth used by an order of magnitude.

There are increasingly more computing problems requiring lengthy parallel computations. For those without access to current cluster or grid infrastructures, a recent and proven viable solution can be found with on-demand utility computing infrastructures, such as Amazon Elastic Compute Cloud (EC2). A relevant class of such problems, Bag-of-Tasks (BoT), can be easily deployed over such infrastructures (to run on pools of virtual computers), if provided with suitable software for host allocation. BoT problems are found in several and relevant scenarios such as image rendering and software testing.In BoT jobs, tasks are mostly independent; thus, they can run in parallel with no communication among them. The number of allocated hosts is relevant as it impacts both the speedup and the cost: if too many hosts are used, the speedup is high but this may not be cost-effective; if too few are used, the cost is low but speedup falls below expectations. For each BoT job, given that there is no prior knowledge of neither the total job processing time nor the time each task takes to complete, it is hard to determine the number of hosts to allocate. Current solutions (e.g., bin-packing algorithms) are not adequate as they require knowing in advance either the time that the next task will take to execute or, for higher efficiency, the time taken by each one of the tasks in each job considered.Thus, we present an algorithm and heuristics that adaptively predicts the number of hosts to be allocated, so that the maximum speedup can be obtained while respecting a given predefined budget. The algorithm and heuristics were simulated against real and theoretical workloads. With the proposed solution, it is possible to obtain speedups in line with the number of allocated hosts, while being charged less than the predefined budget.