In this paper, we propose a hybrid storage framework WukaStore, which offers a scalable, configurable and reliable big data storage service by integrating stable storage (such as Cloud storage or durable storage utilities) and volatile storage (such as idle storage harnessed from desktop PCs over the Internet). By configuring different storage strategies, WukaStore delivers cost-effective storage service to satisfy users’ requirements. We present trace-driven simulations to study the impact of different strategies and how to ensure high availability and durability in WukaStore. We present the prototype implementation of WukaStore based on BitDew, an open source middleware for Big Data management. We conduct performance evaluations to validate the effectiveness of WukaStore, through the deployment of WukaStore in the French Grid'5000 experimental platform. In particular, we also present a case study where WukaStore is deployed in a hybrid environment taking advantage of storage provided by Amazon S3, Dropbox and a local Desktop Grid at the same time. Our evaluation results show that WukaStore provides users with an alternative method to store their big data on hybrid volunteered cloud and desktop systems and to decrease the cost of data storage, while providing great data access performance, scalability as well as reliability.

Summary Cloud computing has increasingly been used as a platform for running large business and data processing applications. Conversely, Desktop Grids have been successfully employed in a wide range of projects, because they are able to take advantage of a large number of resources provided free of charge by volunteers. Ahybrid infrastructurecreated from the combination of Cloud and Desktop Grids infrastructures can provide a low‐cost and scalable solution for Big Data analysis. Although frameworks like MapReduce have been designed to exploit commodity hardware, their ability to take advantage of a hybrid infrastructure poses significant challenges because of their large resource heterogeneity and high churn rate. In this paper, BIGhybrid is proposed, a simulator for two existing classes of MapReduce runtime environments: BitDew‐MapReduce designed for Desktop Grids and BlobSeer‐Hadoop designed for Cloud computing, where the goal is to carry out accurate simulations of MapReduce executions in a hybrid infrastructure composed of Cloud computing and Desktop Grid resources. This work describes the principles of the simulator and describes the validation of BIGhybrid with the Grid5000 experimental platform. Owing to BIGhybrid, developers can investigate and evaluate new algorithms to enable MapReduce to be executed in hybrid infrastructures. This includes topics such as resource allocation and data splitting. Copyright © 2015 John Wiley & Sons, Ltd.

Modern scientific experiments often involve multiple storage and computing platforms, software tools, and analysis scripts. The resulting heterogeneous environments make data management operations challenging, the significant number of events and the absence of data integration makes it difficult to track data provenance, manage sophisticated analysis processes, and recover from unexpected situations. Current approaches often require costly human intervention and are inherently error prone. The difficulties inherent in managing and manipulating such large and highly distributed datasets also limits automated sharing and collaboration. We study a real world e-Science application involving terabytes of data, using three different analysis and storage platforms, and a number of applications and analysis processes. We demonstrate that using a specialized data life cycle and programming model -- Active Data -- we can easily implement global progress monitoring, and sharing, recover from unexpected events, and automate a range of tasks.

Summary This paper introduces HybridMR, a novel model for the execution of MapReduce (MR) computation on hybrid computing environment. Using this model, high performance cloud resources and heterogeneous desktop personal computers (PCs) in Internet or Intranet can be integrated to form a hybrid computing environment. Thanks to HybridMR, the computation and storage capability of large scale desktop PCs can be fully utilized to process large scale datasets. HybridMR relies on two innovative solutions to enable such large scale data‐intensive computation. The first one is HybridDFS, which is a hybrid distributed file system. HybridDFS features reliable distributed storage that alleviates the volatility of desktop PCs, thanks to fault tolerance and file replication mechanism. The second innovation is a new node priority‐based fair scheduling (NPBFS) algorithm has been developed in HybridMR to achieve both data storage balance and job assignment balance by assigning each node a priority through quantifying CPU speed, memory size, and input and output capacity. In this paper, we describe the HybridMR, HybridDFS, and NPBFS. We report on performance evaluation results, which show that the proposed HybridMR not only achieves reliable MR computation, reduces task response time, and improves the performance of MR, but also reduces the computation cost and achieves a greener computing mode. Copyright © 2015 John Wiley & Sons, Ltd.

Since its introduction in 2004 by Google, MapReduce has become the programming model of choice for processing large data sets. MapReduce borrows from functional programming, where a programmer can define both a Map task that maps a data set into another data set and a Reduce task that combines intermediate outputs into a final result. Although MapReduce was originally developed for use by web enterprises in large data-centers, this technique has gained much attention from the scientific community for its applicability in large parallel data analysis (including geographic, high energy physics, genomics, etc.). This special issue of Concurrency and Computation: Practice and Experience is a follow-up to the first Workshop on MapReduce and its Application held in 2010 with the ACM conference High-Performance Parallel and Distributed Computing. The MapReduce workshop attracted many international attendants, allowing deep discussion and the exchange of ideas and results related to ongoing research among attendants. The purpose of this special issue is to focus on recent advances in the developments of tools, applications and environments for MapReduce (or very similar) systems. We selected three contributions that investigate these issues, introduce new execution environments, apply performance evaluations and show the applicability to science and enterprise applications. The paper by Viken Valvåg et al. introduces Cogset, a new MapReduce engine that targets high performance 1. The paper by Urbani et al. presents a scalable application of MapReduce to the problem of RDF data compression 2. The paper by Schütt et al. presents MR-Search, a framework for massively parallel heuristic search 3. The guest editor of this special issue would like to express their deep gratitude to all authors, external reviewers and Geoffrey Fox for their efforts in making this issue possible.

Scheduling tasks in distributed computing infrastructures (DCIs) is challenging mainly because the scheduler is facing a number of more or less dependent parameters that characterize the hosts coming from a particular computing environment and the tasks. In this paper we introduce a multi-criteria scheduling method for DCIs, aiming a better matching between hosts, and tasks waiting in a priority queue at a pull-based scheduler. The novelty of the approach consists in employing the Promethee [1] decision aid for selecting tasks. In the aim of computing preference relationships (priorities) among tasks, this approach performs pairwise comparisons of values that characterize tasks. The method exhibits interesting advantages, such as allowing the user to choose the values for the computation of the priorities, like the expected completion time (ECT) and cost. The approach is also very flexible, allowing through a set of parameters the specification of particular scheduling policies. To validate this method we built an XtrebWeb-like simulator, which is capable of running on real traces. We experiment on internet desktop grid (IDG), cloud and best effort grid (BEG), with various workloads. The results show that the Promethee-based scheduling method obtains good performance especially on IDG when certain fractions of the tasks fail. We also prove that multi-criteria scheduling using Promethee performs better than single-criterion scheduling, improving both makespan and cost. Also, a simple definition of ECT is the most efficient in terms of makespan. In this work we also explain the challenges of using Promethee for scheduling in DCIs.

Exploitation of Best Effort Distributed Computing Infrastructures (BE-DCIs) allow operators to maximize the utilization of the infrastructures, and users to access the unused resources at relatively low cost. Because providers do not guarantee that the computing resources remain available to the user during the entire execution of their applications, they offer a diminished Quality of Service (QoS) compared to traditional infrastructures. Profiling the execution of Bag-of-Tasks (BoT) applications on several kinds of BE-DCIs demonstrates that their task completion rate drops near the end of the execution.

With data intensive applications it can be interesting to resort to a distributed storage to reach scalability and avoid data-intensive problems. Storing data permanently on computing nodes can be an interesting approach especially with the frequent use and the large volume of this data. Moreover, processing large data is a computing intensive task which encourages parallel execution. Nevertheless, data placement on computing nodes should be optimal to reach load balancing. In this work, we investigate scheduling heuristics towards the optimization of data distribution on the computing nodes. Motivated by its capacity to control perfectly the common operations associated with data management, we use BitDew: a desktop grid middleware designed for large scale data management. With BitDew, we build a Data-Driven Master/Worker Platform to carry out the distribution of Magick, the OCR application based on Dynamic Time Warping (DTW) algorithm. We evaluate the benefit of the implementation of studied scheduling heuristics to achieve load balancing with both homogeneous and heterogeneous environment. We present experimental results which demonstrate the efficiency of our aproach.

Desktop Grids and Service Grids are widely used by scientific communities to execute high throughput application. The European EDGeS project aims at developing the technologies to bridge these two kinds of Grid technologies together. In this paper, we present the development and the application of these new technology to extend the EGEE Grid with XtremWeb-HEP based Desktop Grids. We present the setup of the distributed infrastructure which enables EGEE users' jobs to run on one of the three various XtremWeb-HEP DGs. We describe the new volunteer computing project EGEE@Home based on XtremWeb-HEP middleware. To evaluate the capacity of our technology, we present a performance measurement of the main components and conclude that the overhead is kept reasonable despite the fact that the infrastructure is highly distributed.

This article presents the design and building of DSL-Lab, a platform to experiment on distributed computing over broadband domestic Internet. Experimental platforms such as PlanetLab and Grid'5000 are promising methodological approaches to study distributed systems. However, both platforms focus on high-end service and network deployments only available on a restricted part of the Internet, leaving aside the possibility for researchers to experiment in conditions close to what is usually available with domestic connection to the Internet. DSL-Lab is a complementary approach to PlanetLab and Grid'5000 to experiment with distributed computing in an environment closer to how Internet appears, when applications are run on end-user PCs. DSL-Lab is a set of 40 low-power and low-noise nodes, which are hosted by participants, using the participants' xDSL or cable access to the Internet. The objective is to provide a validation and experimentation platform for new protocols, services, simulators and emulators for these systems. In this paper, we report on the software design (security, resources allocation, power management) as well as on the first experiments achieved.

Desktop Grids harvest the computing power of idle desktop computers whether these are volunteer or deployed at an institution. Allowing foreign applications to run on these resources requires the sender of the application to be trusted, but trust in goodwill is never enough. An efficient solution is to provide a secure isolated execution environment ("sandbox"), which does not constrain any additional burden neither on administrators nor on users. Currently Desktop Grids do not provide such facility. In this paper we investigate methods and mechanisms that enable the use of virtual machines as part of a security infrastructure for Desktop Grid clients to provide a sandbox for running (untrusted) applications. We define and analyze the requirements for any platform independent and transparent sandbox for Desktop Grids. We detail a prototype, which we built based on our findings and we give a performance evaluation.

There exists numerous Grid middleware to develop and execute programs on the computational Grid, but they still require intensive work from their users. BitDew is made to facilitate the usage of large scale Grid with dynamic, heterogeneous, volatile and highly distributed computing resources for applications that require a huge amount of data processing. Data-intensive applications form an important class of applications for the e-Science community which require secure and coordinated access to large datasets, wide-area transfers and broad distribution of TeraBytes of data while keeping track of multiple data replicas. In genetic biology, gene sequences comparison and analysis are the most basic routines. With the considerable increase of sequences to analyze, we need more and more computing power as well as efficient solution to manage data. In this work, we investigate the advantages of using a new Desktop Grid middleware BitDew, designed for large scale data management.Our contribution is two-fold: firstly, we introduce a data-driven Master/Slave programming model and we present an implementation of BLAST over BitDew following this model, secondly, we present extensive experimental and simulation results which demonstrate the effectiveness and scalability of our approach. We evaluate the benefit of multi-protocol data distribution to achieve remarkable speedups, we report on the ability to cope with highly volatile environment with relative performance degradation, we show the benefit of data replication in Grid with heterogeneous resource performance and we evaluate the combination of data fault tolerance and data replication when computing on volatile resources.

High performance computing has an important role in scientific and engineering researches. As the size of high performance systems increases continuously, the average time between failures becomes increasingly small. So fault tolerance becomes a critical property for parallel applications running on these systems. MPI (message passing interface) paradigm is actually the most used to write parallel applications. However, in traditional implementations, when a failure occurs, the whole distributed application is shutdown and restarted. To avoid this, many solutions have been proposed, but the most used is rollback recovery. Rollback recovery is based upon the concept of a checkpoint. A checkpoint describes the state of one or more components of the system at a given time of its execution.

As high performance platforms (Clusters, Grids, etc.) continue to grow in size, the average time between failures decreases to a critical level. An efficient and reliable fault tolerance protocol plays a key role in high performance computing. Rollback recovery is the most common fault tolerance technique used in high performance computing and especially in MPI applications. This technique relies on the reliability of the checkpoint storage. Most of the rollback recovery protocols assume that the checkpoint servers machines are reliable. However, in a grid environment any unit can fail at any moment, including components used to connect different administrative domains. Such failures lead to the loss of a whole set of machines, including the more reliable machines used to store the checkpoints in this administrative domain. Thus it is not safe to rely on the high MTBF (mean time between failures) of specific machines to store the checkpoint images. This paper introduces a new coordinated checkpoint protocol, which tolerates checkpoint server failures and clusters failures, and ensures a checkpoint storage reliability in a grid environment. To provide this reliability the protocol is based on a replication process. We propose new hierarchical replication strategies, with two different degrees of hierarchy, adapted to the topology of cluster of clusters. Our solution exploits the locality of checkpoint images in order to minimize inter-cluster communication. We evaluate the effectiveness of our two hierarchical replication strategies through simulations against several criteria such as topology and scalability .

Today basically two grid concepts rule the world: service grids and desktop grids. Service grids offer an infrastructure for grid users, thus require notable management to keep the service running. On the other hand, desktop grids aim to utilize free CPU cycles of cheap desktop PCs, are easy to set up, but the availability towards users is limited compared to the service grid. The aim of the EDGeS project is to create an integrated infrastructure that combines the advantages of the two grid concepts. A building block of this infrastructure is bridging between the different grid types. In the paper we focus on bridging from desktop grids towards service grids, i.e. making desktop grids able to utilize free service grid resources.

In this paper we show how we applied BitTorrent data distribution techniques to the BOINC middleware. Our goal was to decentralize BOINC's data model to take advantage of client network capabilities. To achieve this, we developed a prototype that adds BitTorrent functionality for task distribution and conducted small- scale tests of the environment. Additionally, we measured the impact of the BitTorrent components in both the BOINC client and server, and compared it with the original implementation. Our preliminary results indicate that the BitTorrent client had a negligible influence on the BOINC client's computation time, even in the case where it was seeding extensively. The BOINC server, on the contrary, showed an unexpectedly low bandwidth output when seeding the file, as well as spikes on CPU usage. Current results show the BitTorrent scenario allows clients to share the burden of data distribution on BOINC with almost no negative influence on compute time. This paper will discuss the tests that were performed, how they were evaluated, as well as some improvements that could be made to future tests to enhance server-side efficiency.

Desktop Grids use the computing, network and storage resources from idle desktop PC's distributed over multiple-LAN's or the Internet to compute a large variety of resource-demanding distributed applications. While these applications need to access, compute, store and circulate large volumes of data, little attention has been paid to data management in such large-scale, dynamic, heterogeneous, volatile and highly distributed Grids. In most cases, data management relies on ad-hoc solutions, and providing a general approach is still a challenging issue. To address this problem, we propose the BitDew framework, a programmable environment for automatic and transparent data management on computational Desktop Grids. This paper describes the BitDew programming interface, its architecture, and the performance evaluation of its runtime components. BitDew relies on a specific set of meta-data to drive key data management operations, namely life cycle, distribution, placement, replication and fault-tolerance with a high level of abstraction. The Bitdew runtime environment is a flexible distributed service architecture that integrates modular P2P components such as DHT's for a distributed data catalog and collaborative transport protocols for data distribution. Through several examples, we describe how application programmers and Bitdew users can exploit Bitdew's features. The performance evaluation demonstrates that the high level of abstraction and transparency is obtained with a reasonable overhead, while offering the benefit of scalability, performance and fault tolerance with little programming cost.

"Volunteer computing" uses Internet-connected computers, volunteered by their owners, as a source of computing power and storage. This paper studies the potential capacity of volunteer computing. We analyzed measurements of over 330,000 hosts participating in a volunteer computing project. These measurements include processing power, memory, disk space, network throughput, host availability, userspecified limits on resource usage, and host churn. We show that volunteer computing can support applications that are significantly more data-intensive, or have larger memory and storage requirements, than those in current projects.

Desktop grids use the idle cycles of desktop PC’s to provide huge computational power at low cost. However, because the underlying desktop computing resources are volatile, achieving performance guarantees such as task completion rate is difficult. We investigate the use of buffering to ensure task completion rates, which is essential for soft real-time applications. In particular, we develop a model of task completion rate as a function of buffer size. We instantiate this model using parameters derived from two enterprise desktop grid data sets, evaluate the model via trace-driven simulation, and show how this model can be used to ensure application task completion rates on enterprise desktop grid systems.

Desktop grids, which use the idle cycles of many desktop PC's, are currently one of the largest distributed systems in the world. Despite the popularity and success of many desk-top grid projects, the volatility of hosts within desktop grids has been poorly understood. Yet, such host characterization is essential for accurate simulation and modelling of such platforms. In this paper, we present application-level traces of four enterprise desktop grids with a wide range of user bases. We then describe aggregate and per host statistics that reflect the volatility of desktop grid resources. Further, we determine the correlation of volatility between resources, and investigate the correlation of volatility and other host characteristics. Finally, we detail a number of implications of these findings with respect to application performance.

Desktop grid (DG) systems use the idle computing power of many volunteered desktop PC's on the Internet to support large-scale computation and storage. For over a decade, DG systems have been the largest and the most powerful distributed computing systems, offering a plethora of computing power at a fraction of the cost of supercomputers. The volunteer desktops participating in DG projects are volatile and heterogeneous, but there is little detailed information about their volatility and heterogeneity. Yet this characterization is essential for the simulation and modelling of such systems. We are conducting a project whose goal is to obtain a detailed picture of the DG landscape. To this end, we are deploying resource sensors on the volunteer desktops to measure the availability of CPU, disk space, memory, and network bandwidth. An initial version of the project has been deployed and currently has about 1,800 participating hosts. The resulting resource measurement data and characterization will be useful for a broad range of research areas, including distributed and peer-to-peer computing, and fault tolerance

Data-centric applications are still a challenging issue for Large Scale Distributed Computing Systems. The emergence of new protocols and softwares for collaborative content distribution over Internet offers a new opportunity for efficient and fast delivery of high volume of data. This paper presents an evaluation of the BitTorrent protocol for Computational Desktop Grids. We first present a prototype of a generic subsystem dedicated to data management and designed to serve as a building block for any Desktop Grid System. Based on this prototype we conduct experimentations to evaluate the potential of BitTorrent compared to a classical approach based on FTP data server. The preliminary results obtained with a 65-nodes cluster measure the basic characteristics of BitTorrent in terms of latency and bandwidth and evaluate the scalability of BitTorrent for the delivery of large input files. Moreover, we show that BitTorrent has a considerable latency overhead compared to FTP but clearly outperforms FTP when distributing large files or files to a high number of nodes. Tests on a synthetic application show that Bit- Torrent significantly increases the communication/computation ratio of the applications eligible to run on a Desktop Grid System.

RPC is one of the programming models envisioned for the Grid. In Internet connected Large Scale Grids such as Desktop Grids, nodes and networks failures are not rare events. This paper provides several contributions, examining the feasibility and limits of fault-tolerant RPC on these platforms. First, we characterize these Grids from their fundamental features and demonstrate that their applications scope should be safely restricted to stateless services. Second, we present a new fault-tolerant RPC protocol associating an original combination of three-tier architecture, passive replication and message logging. We describe RPC-V, an implementation of the proposed protocol within the XtremWeb Desktop Grid middleware. Third, we evaluate the performance of RPC-V and the impact of faults on the execution time, using a real life application on a Desktop Grid testbed assembling nodes in France and USA. We demonstrate that RPC-V allows the applications to continue their execution while key system components fail.

Grid computing presents two major challenges for deploying large scale applications across wide area networks gathering volunteers PC and clusters/parallel computers as computational resources: security and fault tolerance. This paper presents a lightweight Grid solution for the deployment of multi-parameters applications on a set of clusters protected by firewalls. The system uses a hierarchical design based on Condor for managing each cluster locally and XtremWeb for enabling resource sharing among the clusters. We discuss the security and fault tolerance mechanisms used for this design and demonstrate the usefulness of the approach measuring the performances of a multi-parameters bio-chemistry application deployed on two sites: University of Wisconsin/Madison and Paris South University. This experiment shows that we can efficiently and safely harness the computational power of about 200 PC distributed on two geographic sites.

Global Computing platforms, large scale clusters and future TeraGRID systems gather thousands of nodes for computing parallel scientific applications. At this scale, node failures or disconnections are frequent events. This Volatility reduces the MTBF of the whole system in the range of hours or minutes. We present MPICH-V, an automatic Volatility tolerant MPI environment based on uncoordinated checkpoint/roll-back and distributed message logging. MPICH-V architecture relies on Channel Memories, Checkpoint servers and theoretically proven protocols to execute existing or new, SPMD and Master-Worker MPI applications on volatile nodes. To evaluate its capabilities, we run MPICH-V within a framework for which the number of nodes, Channels Memories and Checkpoint Servers can be completely configured as well as the node Volatility. We present a detailed performance evaluation of every component of MPICH-V and its global performance for non-trivial parallel applications. Experimental results demonstrate good scalability and high tolerance to node volatility.

High performance computing on parallel architectures currently uses different approaches depending on the hardware memory model of the architecture, the abstraction level of the programming environment and the nature of the application. We introduce an original client-server execution model based on RPCs called out-of-order parallel virtual machine (OVM). OVM aims to provide three main features: portability through a unique memory model; load-balancing using a plug-in support; and high performance provided by several optimizations. The main optimizations are: non-blocking RPCs, dataflow management, persistent and non-persistent data, static data set distribution, dynamic scheduling and asynchronous global operations. We present OVM general architecture and demonstrate high performance for regular parallel applications, a parallel application with load balancing needs and a real time parallel application.

Global computing achieves high throughput computing by harvesting a very large number of unused computing resources connected to the Internet. This parallel computing model targets a parallel architecture defined by a very high number of nodes, poor communication performance and continuously varying resources. The unprecedented scale of the global computing architecture paradigm requires us to revisit many basic issues related to parallel architecture programming models, performance models, and class of applications or algorithms suitable for this architecture. XtremWeb is an experimental global computing platform dedicated to provide a tool for such studies. The paper presents the design of XtremWeb. Two essential features of this design are multi-applications and high-performance. Accepting multiple applications allows institutions or enterprises to set up their own global computing applications or experiments. High-performance is ensured by scalability, fault tolerance, efficient scheduling and a large base of volunteer PCs. We also present an implementation of the first global application running on XtremWeb.