ABSTRACT Reducing the running time of graph algorithms is vital for tackling real‐world problems such as shortest paths and matching in large‐scale graphs, where path information plays a crucial role. To address this critical challenge, this paper introduces a graph restructuring algorithm that identifies bipartite cliques and replaces them with tripartite graphs. This restructuring leads to fewer edges while preserving complete graph path information, enabling the direct application of algorithms like matching and all‐pairs shortest paths to achieve significant runtime reductions, especially for large, dense graphs. The running time of the proposed algorithm for a graph , with and is , which is better than , the running time of the best existing algorithm for speeding‐up other graph algorithms (the Feder–Motwani ( FM ) algorithm), where . Both the FM algorithm and the proposed algorithm are originally formulated for bipartite graphs, but can also be applied to general directed or undirected graphs. Our extensive experimental analysis demonstrates that the proposed algorithm achieves up to 21.26% higher reduction in the number of edges and runs up to faster than the FM algorithm. On large synthetic graphs with up to 1.05 billion edges, it attains a reduction in the number of edges of up to 74.36%. On real‐world graphs, it achieves a reduction in the number of edges by up to 46.8%. Furthermore, when used as a preprocessing step, our approach yields up to a speedup for the matching algorithms on large synthetic graphs, and up to a speedup for the All‐Pairs Shortest Path algorithms on real‐world graphs, when compared to using the given graph as input.

Ensuring low battery degradation in Autonomous Ground Robot (AGR) fleets operating in online environments (e.g., delivery services) is essential for enhancing their long-term sustainability. However, most existing studies either rely on offline methods—unsuitable for scenarios requiring real-time decisions—or focus solely on maximizing task allocation, resource utilization, or revenue, with limited consideration for battery health. Additionally, maximizing fleet sustainability requires bounded relative revenue losses from unassigned tasks within a user-defined acceptable limit to make it an attractive option for industry. To address these limitations, we propose an online task and charge allocation framework that jointly optimizes revenue generation and battery lifespan, while allowing users to explicitly constrain relative revenue losses. The framework includes three event-driven algorithms: BTC-M, which computes optimal decisions at each event, and two computationally efficient greedy variants, BTC-G and BTC-WG, which provide sub-optimal solutions with reduced overhead. We evaluate the performance of our approach under different task arrival distributions representative of real-world applications. Simulation results based on a real AGR, compared against multiple baselines, demonstrate that our framework can extend battery lifespan by up to 19% with minimal revenue loss.

Edge computing has been developed as a low-latency data driven computation paradigm close to the end user to maximize profit, and/or minimize energy consumption. Edge computing allows each user’s task to analyze locally-acquired sensor data at the edge to reduce the resource congestion and improve the efficiency of data processing. To reduce application latency and data transferred to edge servers it is essential to consider data sharing for some user tasks that operate on the same data items. In this article, we formulate the data sharing-aware allocation problem which has as objectives the maximization of profit and minimization of network traffic by considering data-sharing characteristics of tasks on servers. Because the problem is${\sf NP-hard}$, we design the${\sf DSTA}$algorithm to find a feasible solution in polynomial time. We investigate the approximation guarantees of${\sf DSTA}$by determining the approximation ratios with respect to the total profit and the amount of total data traffic in the edge network. We also design a variant of${\sf DSTA}$, called${\sf DSTAR}$that uses a smart rearrangement of tasks to allocate some of the unallocated tasks for increased total profit. We perform extensive experiments to investigate the performance of${\sf DSTA}$and${\sf DSTAR}$, and compare them with a representative greedy baseline that only maximizes profit. Our experimental analysis shows that, compared to the baseline,${\sf DSTA}$reduces the total data traffic in the edge network by up to 20% across 45 case study instances at a small profit loss. In addition,${\sf DSTAR}$increases the total profit by up to 27% and the number of allocated tasks by 25% compared to${\sf DSTA}$, all while limiting the increase of total data traffic in the network.

Edge computing allows end-user devices to offload heavy computation to nearby edge servers for reduced latency, maximized profit, and/or minimized energy consumption. Data dependent tasks that analyze locally acquired sensing data are one of the most common candidates for task offloading in edge computing. Thus, the total latency and network load are affected by the total amount of data transferred from end-user devices to the selected edge servers. Most existing solutions for task allocation in edge computing do not consider that some user tasks may operate on the same data items. Making the task allocation algorithm aware of the existing data sharing characteristics of tasks can help reduce network load at a negligible profit loss by allocating more tasks sharing data on the same server.In this PhD thesis, we formulate the data sharing-aware task allocation problem that makes decisions on task allocation for maximized profit and minimized network load by considering the data-sharing characteristics of tasks. In addition, because the problem is NP-hard, we design and implement an offline algorithm, which finds a good feasible solution to the problem in polynomial time. We also design and implement online algorithms for task allocation in edge computing that take into account the sharing of data among the tasks offloaded to the same server. We analyze the performance of our offline algorithm against a state-of-the-art baseline that only maximizes profit. We also perform an extensive performance analysis by comparing our online algorithms with their sharing-oblivious counterparts.

Autonomous mobile robots (AMRs) are capable of carrying out operations continuously for 24/7, which enables them to optimize tasks, increase throughput, and meet demanding operational requirements. To ensure seamless and uninterrupted operations, an effective coordination of task allocation and charging schedules is crucial while considering the preservation of battery sustainability. Moreover, regular preventive maintenance plays an important role in enhancing the robustness of AMRs against hardware failures and abnormalities during task execution. However, existing works do not consider the influence of properly scheduling AMR maintenance on both task downtime and battery lifespan. In this paper, we proposeMTC,a maintenance-aware task and chargingscheduler designed for fleets of AMR operating continuously in highly automated environments.MTCleverages Linear Programming (LP) to first help decide the best time to schedule maintenance for a given set of AMRs. Subsequently, the Kuhn-Munkres algorithm, a variant of the Hungarian algorithm, is used to finalize task assignments and carry out the charge scheduling to minimize the combined cost of task downtime and battery degradation. Experimental results demonstrate the effectiveness ofMTC, reducing the combined total cost up to 3.45 times and providing up to 68% improvement in battery capacity degradation compared to the baselines.

Private and public transportation will be dominated by Autonomous Vehicles (AV), which are safer than regular vehicles. However, ensuring good performance for the autonomous features requires fast processing of heavy tasks. Providing each AV with powerful computing resources may result in increased AV cost and decreased driving range. An alternative solution is to install low-power computing hardware on each AV and offload the heavy tasks to powerful nearby edge servers. In this case, the AV’s reaction time depends on how quickly the navigation tasks are completed in the edge server. To reduce task completion latency, the edge servers must be equipped with enough network and computing resources to handle the vehicle demands, which show large spatio-temporal variations. Thus, deploying the same resources in different locations may lead to unnecessary resource over-provisioning. In this paper, we leverage simulations using real traffic data to discuss the implications of deploying heterogeneous resources in different city areas to sustain peak versus average demand of edge-assisted AVs. Our analysis indicates that a reduction in network bandwidth and computing cores of up to 60% and 50%, respectively, is achieved by deploying edge resources for the average demand rather than peak demand. We also investigate how the peak-hour demand affects the safe travel time of AVs and find that it can be reduced by approximately 20% if they would be rerouted to areas with a lower edge-resource load. Thus, future research must consider that traditional turn-by-turn navigation systems may not provide the fastest routes for edge-assisted AVs.

In Vehicular Edge Computing (VEC) systems, the computing resources of connected Electric Vehicles (EV) are used to fulfill the low-latency computation requirements of vehicles. However, local execution of heavy workloads may drain a considerable amount of energy in EVs. One promising way to improve the energy efficiency is to share and coordinate computing resources among connected EVs. However, the uncertainties in the future location of vehicles make it hard to decide which vehicles participate in resource sharing and how long they share their resources so that all participants benefit from resource sharing. In this paper, we propose VECMAN, a framework for energy-aware resource management in VEC systems composed of two algorithms: (i) a resource selector algorithm that determines the participating vehicles and the duration of resource sharing period; and (ii) an energy manager algorithm that manages computing resources of the participating vehicles with the aim of minimizing the computational energy consumption. We evaluate the proposed algorithms and show that they considerably reduce the vehicles’ computational energy consumption compared to the state-of-the-art baselines. Specifically, our algorithms achieve between 7 and 18 percent energy savings compared to a baseline that executes workload locally and an average of 13 percent energy savings compared to a baseline that offloads vehicles’ workloads to RSUs.

In the Steiner Forest problem, we are given an undirected graph with non-negative weights for edges, a set of pairs of vertices, called terminals, and the goal is to find the minimum cost subgraph that connects each of the terminal pairs together. There exist several sequential heuristic and approximation algorithms for the Steiner Forest problem. In practice, the primal-dual 2-approximation algorithm is one of the fastest and obtains solutions that are very close to the optimal solution. In this paper, we design a practical parallel approximation algorithm based on the primal-dual sequential algorithm. The parallel algorithm maintains the approximation guarantees of the sequential primal-dual algorithm and it is specifically designed for execution on multi-core computers. We implement and run the parallel algorithm on a multi-core system with a large number of cores and perform an extensive experimental performance analysis on randomly generated graphs. The results show that our proposed parallel approximation algorithm achieves a significant speedup with respect to the sequential primal-dual algorithm.

We design a parallel algorithm for the Constrained Shortest Path (CSP) problem. The CSP problem is known to be NP-hard and there exists a pseudo-polynomial time sequential algorithm that solves it. To design the parallel algorithm, we extend the techniques used in the design of the Δ-stepping algorithm for the single-source shortest paths problem.

Abstract In the Steiner forest problem, we are given a set of terminal pairs and need to find the minimum cost subgraph that connects each of the terminal pairs together. Motivated by the recent work on greedy approximation algorithms for the Steiner forest, we provide efficient implementations of existing approximation algorithms and conduct a thorough experimental study to characterize their performance. We consider several approximation algorithms: the influential primal‐dual 2‐approximation algorithm due to Agrawal, Klein, and Ravi, the greedy algorithm due to Gupta and Kumar, and a randomized algorithm based on probabilistic approximation by tree metrics. We also consider the simplest heuristic greedy algorithm for the problem, which picks the closest unconnected pair of terminals and connects it using the shortest path between the terminals in the current graph. To characterize the performance of the algorithms, we created a new library with more than one thousand Steiner forest problem instances and conducted an extensive experimental analysis on those instances. Our analysis reveals that for the majority of instances the primal‐dual algorithm is the fastest among all the algorithms considered here, and obtains solutions that are very close to the optimal solutions obtained by solving the integer program formulation of the problem.

In this article, we address the Multi-Component Application Placement Problem (${\sf MCAPP}$) in Mobile Edge Computing (MEC) systems. We formulate this problem as a Mixed Integer Non-Linear Program (MINLP) with the objective of minimizing the total cost of running the applications. In our formulation, we take into account two important and challenging characteristics of MEC systems, the mobility of users and the network capabilities. We analyze the complexity of${\sf MCAPP}$and prove that it is$NP$-hard, that is, finding the optimal solution in reasonable amount of time is infeasible. We design two algorithms, one based on matching and local search and one based on a greedy approach, and evaluate their performance by conducting an extensive experimental analysis driven by two types of user mobility models, real-life mobility traces and random-walk. The results show that the proposed algorithms obtain near-optimal solutions and require small execution times for reasonably large problem instances.

In this article, we address the resource allocation and monetization challenges in Mobile Edge Computing (MEC) systems, where users have heterogeneous demands and compete for high quality services. We formulate the Edge Resource Allocation Problem (ERAP) as a Mixed-Integer Linear Program (MILP) and prove that ERAP is NP-hard. To solve the problem efficiently, we propose two resource allocation mechanisms. First, we develop an auction-based mechanism and prove that the proposed mechanism is individually-rational and produces envy-free allocations. We also propose an LP-based approximation mechanism that does not guarantee envy-freeness, but it provides solutions that are guaranteed to be within a given distance from the optimal solution. We evaluate the performance of the proposed mechanisms by conducting an extensive experimental analysis on ERAP instances of various sizes. We use the optimal solutions obtained by solving the MILP model using a commercial solver as benchmarks to evaluate thequality of solutions. Our analysis shows that the proposed mechanisms obtain near optimal solutions for fairly large size instances of the problem in a reasonable amount of time.

The papers in this special section focus on energy efficient edge computing. The future increase in the amount of data and workloads generated by Internet of Things (IoT) devices and connected sensors will lead to the necessity to move computational nodes from the cloud data centers closer to the data source, i.e., at the edge of the cloud, for reduced latency. An edge system is composed of any computing and networking resources along the path between data sources and cloud data centers. Depending on the specific computing needs, edge computing devices can use either a wireless or a wired connection to exchange messages with the data sources. IoT devices and sensors can then exploit the hierarchical structure of the edge and cloud system to analyze the collected data and provide useful information to users in a timely manner. For example, wearable sensors could use the computing resources of the user’s smartphone, laptop, or even smart vehicle to analyze the collected data. Because a large majority of edge devices are battery operated and have limited connectivity, the energy efficiency of computation becomes critical. To this end, it is important to minimize the energy consumption of all the components of an edge system, including sensors, IoT devices, edge nodes, and network devices while guaranteeing the desired performance. For this special section we selected eight articles that cover experimental, conceptual, and theoretical contributions to energy-efficient edge computing.

Cloud providers can form cloud federations by pooling their resources together to balance their loads, reduce their costs, and manage demand spikes. However, forming cloud federations is a challenging problem, especially when considering the incentives of the cloud providers making their own decisions to participate in cloud federations. In this paper, we model the formation of cloud federations necessary to provide resources to execute Map-heavy/Reduce-heavy programs while considering the trust and reputation among the participating cloud providers. The objective is to form cloud federations with highly reputable cloud providers that achieve maximum profit for their participation. This is an NP-hard bicriteria optimization problem. We introduce a coalitional graph game, called trust-aware cloud federation formation game, to model the cooperation among cloud providers. We design a mechanism for cloud federation formation that enables the cloud providers with high reputation to organize into federations reducing their costs. Our proposed mechanism guarantees the highest profits for the participating cloud providers in the federations, and ensures high reliability of the formed federations in executing the applications. We perform extensive experiments to characterize the properties of the proposed mechanism. The results show that our proposed mechanism produces Pareto optimal and stable cloud federations that not only guarantee that the participating cloud providers have high reputation, but also high individual profits.

Cloud providers face the challenge of efficiently managing their infrastructure through minimizing resource consumption while allocating service requests such that their revenue is maximized. Solutions addressing this challenge should consider the sharing of memory pages among virtual machines (VMs) and the available capacity of each type of requested resources. We provide such solution by designing a greedy approximation algorithm for solving the sharing-aware virtual machine revenue maximization (SAVMRM) problem. The SAVMRM problem requires determining the set of VMs that can be instantiated on a given server such that the revenue derived from hosting the VMs is maximized. In addition, we model the SAVMRM problem as a multilinear binary program and optimally solve it, while accounting for page sharing and multiple resource constraints. We determine and analyze the approximability properties of our proposed greedy algorithm and evaluate it by performing extensive experiments using Google cluster workload traces. The experimental results show that under various scenarios, our proposed algorithm generates higher revenue than other VM allocation algorithms while achieving significant reduction of allocated memory.

The low-latency requirements of connected electric vehicles and their increasing computing needs have led to the necessity to move computational nodes from the cloud data centers to edge nodes such as road-side units (RSU). However, offloading the workload of all the vehicles to RSUs may not scale well to an increasing number of vehicles and workloads. To solve this problem, computing nodes can be installed directly on the smart vehicles, so that each vehicle can execute the heavy workload locally, thus forming a vehicular edge computing system. On the other hand, these computational nodes may drain a considerable amount of energy in electric vehicles. It is therefore important to manage the resources of connected electric vehicles to minimize their energy consumption. In this paper, we propose an algorithm that manages the computing nodes of connected electric vehicles for minimized energy consumption. The algorithm achieves energy savings for connected electric vehicles by exploiting the discrete settings of computational power for various performance levels. We evaluate the proposed algorithm and show that it considerably reduces the vehicles' computational energy consumption compared to state-of-the-art baselines. Specifically, our algorithm achieves 15-85% energy savings compared to a baseline that executes workload locally and an average of 51% energy savings compared to a baseline that offloads vehicles' workloads only to RSUs.

The Quality of Service (QoS) in Mobile Edge Computing (MEC) systems is significantly dependent on the application offloading and placement decisions. Due to the movement of users in MEC networks, an optimal application placement might turn into the least efficient placement in few minutes. Thus, it is crucial to take the dynamics of the system into account when designing application placement mechanisms. On the other hand, energy consumption of servers is a significant component of the cost of services in MEC systems and must also be considered in the design of the mechanisms. In this article, we model the problem of energy-aware application placement in edge computing systems as a multi-stage stochastic program. The objective is to maximize the QoS of the system while taking into account the limited energy budget of the edge servers. To solve the problem, we design a novel parallel Sample Average Approximation (SAA) algorithm. We conduct an extensive experimental analysis to evaluate the performance of the proposed algorithm using real-world trace data.

Mobile Edge Computing (MEC) is a new paradigm that aims at decreasing the response time of running mobile applications by offloading the component of the applications on the servers located at the edge of the network instead of on the cloud servers. In this paper, we address a very important problem in the management of MEC systems, that is, the problem of finding an efficient application placement on the edge servers such that the cost of execution is minimized. We develop a multi-stage stochastic programming model for the application placement problem in edge computing systems and design a novel parallel greedy algorithm based on the Sample Average Approximation method to solve it. We evaluate the performance of the proposed algorithm by conducting extensive experimental analysis using data extracted from a real-world dataset. The experimental results show that the proposed algorithm can solve the problem efficiently.

This special issue consists of six representative research articles presented at the 14th International Symposium on Parallel and Distributed Computing, in Limassol, a beautiful coastal Mediterranean city on the South coast of Cyprus. This annual symposium brings together practitioners, researchers, and scholars from the field of parallel and distributed computing to facilitate the exchange of ideas, enable collaborations, and promote the development of new research directions. The symposium had a highly selective program composed of papers describing original and unpublished research advancing the state of the art in the field of parallel and distributed computing. For this special issue, we selected the six best papers presented at the symposium. These papers reflect the broad nature of the field, addressing both theoretical and practical issues in mobile ad-hoc networks, clouds, routing, graphics processing unit computing, parallel irregular applications, security, and workflow scheduling. Alshareef and Grigoras 1 propose the use of a cloud service to register, save, pause, and resume sessions between mobile ad-hoc network (MANET) member nodes such that both the work in progress and energy are saved. They also introduce a checkpointing technique that captures the progress of a session and allows it to be resumed. Chilipirea et al.,2 describe a new fast simulator, designed to minimize the work needed to conduct extensive tests for opportunistic routing algorithms on multiple traces. They also present a comprehensive analysis of the most popular routing algorithms through extensive simulations conducted on their proposed simulation platform. Kouge et al.,3 propose a graphics processing unit implementation for digital halftoning employing local exhaustive search to produce high-quality binary images and to achieve significant speedup over the CPU implementation. Neves 4 presents two refinements of Exploit Parallelism in Irregular Codes (EPIC), a framework developed to ease the exploitation of task parallelism in irregular applications that use third-party tools and/or generate asymmetric sets of tasks. The two refinements focus on the software design and the scheduling algorithm of the EPIC framework. Sapegin et al.,5 present the design of a security information and event management system based on an in-memory database with an integrated machine learning library. Employing deep normalization of log messages, storing data in the main memory, and running data analysis directly in the database, the system achieves significant processing speeds allowing machine learning analysis of security events in almost real time. Xie et al.,6 propose three workflow scheduling algorithms, a fairness-based algorithm, a priority-based scheduling algorithm, and a tradeoff-based scheduling algorithm. The tradeoff-based algorithms were designed to meet the deadlines of more higher-priority workflows, while still allowing the lower-priority workflows to be processed actively for better performance. The guest editors would like to thank Prof. Geoffrey C. Fox for his help in putting together this special issue. The guest editors are very grateful to the reviewers for their high-quality reviews and constructive feedback on the papers.

brings together practitioners, researchers, and scholars from the field of parallel and distributed computing to facilitate the exchange of ideas, enable collaborations, and promote the development of new research directions.

One of the key problems that cloud providers need to efficiently solve when offering on-demand virtual machine (VM) instances to a large number of users is the VM Packing problem, a variant of Bin Packing. The VM Packing problem requires determining the assignment of user requested VM instances to physical servers such that the number of physical servers is minimized. In this paper, we consider a more general variant of the VM Packing problem, called the Sharing-Aware VM Packing problem, that has the same objective as the standard VM Packing problem, but allows the VM instances collocated on the same physical server to share memory pages, thus reducing the amount of cloud resources required to satisfy the users' demand. Our main contributions consist of designing several online algorithms for solving the Sharing-Aware VM Packing problem, and performing an extensive set of experiments to compare their performance against that of several existing sharing-oblivious online algorithms. For small problem instances, we also compare the performance of the proposed online algorithms against the optimal solution obtained by solving the offline variant of the Sharing-Aware VM Packing problem (i.e., the version of the problem that assumes that the set of VM requests are known a priori). The experimental results show that our proposed sharing-aware online algorithms activate a smaller average number of physical servers relative to the sharing-oblivious algorithms, directly reduce the amount of required memory, and thus, require fewer physical servers to instantiate the VM instances requested by users.

We consider a competitive environment for reward-based scheduling of periodic tasks, where the execution of each task consists of a mandatory and an optional part. Each task obtains a value if the processor successfully schedules all its mandatory part, and also an additional reward value if the processor successfully schedules a part of its optional execution. Each task is owned by a self-interested agent who has multiple choices for its requests based on its optional part. We model the reward-based scheduling problem by considering such multi-minded agents. However, the agent may try to manipulate the system to obtain an unfair optional allocation. We address this challenge by designing novel truthful mechanisms in which it is always in the agent's best interest to report their true task characteristics. We propose two truthful mechanisms (an exact and approximate) for selecting a feasible subset of agents and an allocation of optional execution that maximizes the total reward obtained by the selected tasks. To address the pseudo-polynomial complexity of the exact mechanism, we show that our proposed approximate mechanism is a polynomial-time approximation scheme (PTAS). Our extensive experiments show that our proposed approximation mechanism is capable of finding near-optimal solutions efficiently while guaranteeing truthfulness.

Cloud providers provision their various resources such as CPUs, memory, and storage in the form of virtual machine (VM) instances which are then allocated to the users. The users are charged based on a pay-as-you-go model, and their payments should be determined by considering both their incentives and the incentives of the cloud providers. Auction markets can capture such incentives, where users name their own prices for their requested VMs. We design an auction-based online mechanism for VM provisioning, allocation, and pricing in clouds that considers several types of resources. Our proposed online mechanism makes no assumptions about future demand of VMs, which is the case in real cloud settings. The proposed online mechanism is invoked as soon as a user places a request or some of the allocated resources are released and become available. The mechanism allocates VM instances to selected users for the period they are requested for, and ensures that the users will continue using their VM instances for the entire requested period. In addition, the mechanism determines the payment the users have to pay for using the allocated resources. We prove that the mechanism is incentive-compatible, that is, it gives incentives to the users to reveal their actual requests. We investigate the performance of our proposed mechanism through extensive experiments.

Cloud service providers offer services to a large number of users by employing virtualization technologies. One of the challenges faced by the cloud providers using virtualized environments is the development of efficient algorithms for assigning Virtual Machine (VM) instances to servers such that the number of hosting servers is minimized. This is also known as the problem of VM Packing. In this paper, we design a family of sharing-aware online algorithms for solving the VM Packing problem that take into account the sharing of memory among collocated VMs. We introduce a new server resource scarcity metric which establishes an order among servers that are suitable for hosting an arriving VM request and use it in the design of the algorithms. We evaluate the performance of our sharing-aware online algorithms by performing an extensive set of experiments comparing them against several existing sharing-oblivious VM packing algorithms.

Cloud providers face the challenge of efficiently managing their infrastructure through minimizing resource consumption while allocating requests such that their profit is maximized. We address this challenge by designing a greedy approximation algorithm for solving the multi-resource sharing-aware virtual machine maximization (MSAVMM) problem. The MSAVMM problem requires determining the set of VMs that can be instantiated on a given server such that the profit derived from hosting the VMs is maximized. The solution to this problem has to consider the sharing of memory pages among VMs and the restricted capacities of each type of resource requested by the VMs. We analyze the performance of the proposed algorithm by determining its approximation ratio and by performing extensive experiments against other sharing-aware VM allocation algorithms.

The amount of computing resources required by current and future data-intensive applications is expected to increase dramatically, creating high demands for cloud resources. The cloud providers' available resources may not be sufficient enough to cope with such demands. Therefore, the cloud providers need to reshape their business structures and seek to improve their dynamic resource scaling capabilities. Federated clouds offer a practical platform for addressing this service management issue. We introduce a cloud federation formation game that considers the cooperation of the cloud providers in offering cloud IaaS services. Based on the proposed federation formation game, we design a cloud federation formation mechanism that enables the cloud providers to dynamically form a cloud federation maximizing their profit. In addition, the proposed mechanism produces a stable cloud federation structure, that is, the participating cloud providers in the federation do not have incentives to break away from the federation. We analyze the performance of the proposed mechanism by performing extensive experiments. The results of the experiments show that the cloud federation obtained by our proposed mechanism is stable, yielding high profit for the participating cloud providers.

We address the problem of physical machine resource management in clouds considering multiple types of physical machines and resources. We formulate this problem in an auction-based setting and design optimal and approximate strategy-proof mechanisms that solve it. Our proposed mechanisms consist of a winner determination algorithm that selects the users, provisions the virtual machines (VMs) to physical machines (PMs), and allocates them to the selected users; and a payment function that determines the amount that each selected user needs to pay to the cloud provider. We prove that our proposed approximate winner determination algorithm satisfies the loser-independent property, making the approximate mechanism robust against strategic users who try to manipulate the system by changing other users' allocations. We show that our proposed mechanisms are strategy-proof, that is, the users do not have incentives to lie about their requested bundles of VM instances and their valuations. In addition, our proposed mechanisms are in alignment with green cloud computing strategies in which physical machines can be powered on or off to save energy. Our theoretical analysis shows that the proposed approximation mechanism has an approximation ratio of 3. We perform extensive experiments in order to investigate the performance of our proposed approximation mechanism compared to that of the optimal mechanism.

Cloud providers provision their heterogeneous resources such as CPUs, memory, and storage in the form of virtual machine (VM) instances which are then allocated to the users. One of the major challenges faced by the cloud providers is to allocate and provision these resources such that their profit is maximized, and the resources are utilized efficiently. Recently, cloud providers have introduced auction-based models which allow users to submit bids for their requested VMs. We address the problem of autonomic VM provisioning and allocation for the auction-based model considering multiple types of resources by designing an approximation mechanism. In addition, the mechanism determines the payment the users have to pay for using the allocated resources. This problem is computationally intractable, and our proposed mechanism is by far the strongest approximation result that can be achieved for this problem. We show that the proposed approximation mechanism is a polynomial-time approximation scheme (PTAS). Furthermore, our proposed mechanism drives the system into an equilibrium in which the users do not have incentives to manipulate the system by untruthfully reporting their VM bundle requests and valuations. We perform extensive experiments using real workload traces in order to investigate the performance of the proposed mechanism.

The majority of large-scale data intensive applications executed by data centers are based on MapReduce or its open-source implementation, Hadoop. Such applications are executed on large clusters requiring large amounts of energy, making the energy costs a considerable fraction of the data center's overall costs. Therefore minimizing the energy consumption when executing each MapReduce job is a critical concern for data centers. In this paper, we propose a framework for improving the energy efficiency of MapReduce applications, while satisfying the service level agreement (SLA). We first model the problem of energy-aware scheduling of a single MapReduce job as an Integer Program. We then propose two heuristic algorithms, called energy-aware MapReduce scheduling algorithms (EMRSA-I and EMRSA-II), that find the assignments of map and reduce tasks to the machine slots in orderto minimize the energy consumed when executing the application. We perform extensive experiments on a Hadoop cluster to determine the energy consumption and execution time for several workloads from the HiBench benchmark suite including TeraSort, PageRank, and K-means clustering, and then use this data in an extensive simulation study to analyze the performance of the proposed algorithms. The results show that EMRSA-I and EMRSA-II are able to find near optimal job schedules consuming approximately 40 percent less energy on average than the schedules obtained by a common practice scheduler that minimizes the makespan.

A major challenging problem for cloud providers is designing efficient mechanisms for virtual machine (VM) provisioning and allocation. Such mechanisms enable the cloud providers to effectively utilize their available resources and obtain higher profits. Recently, cloud providers have introduced auction-based models for VM provisioning and allocation which allow users to submit bids for their requested VMs. We formulate the dynamic VM provisioning and allocation problem for the auction-based model as an integer program considering multiple types of resources. We then design truthful greedy and optimal mechanisms for the problem such that the cloud provider provisions VMs based on the requests of the winning users and determines their payments. We show that the proposed mechanisms are truthful, that is, the users do not have incentives to manipulate the system by lying about their requested bundles of VM instances and their valuations. We perform extensive experiments using real workload traces in order to investigate the performance of the proposed mechanisms. Our proposed mechanisms achieve promising results in terms of revenue for the cloud provider.

Cloud providers provision their various resources such as CPUs, memory, and storage in the form of Virtual Machine (VM) instances which are then allocated to the users. We design online mechanisms for VM provisioning and allocation in clouds that consider several types of available resources. Our proposed online mechanisms make no assumptions about future demand of VMs, which is the case in real cloud settings. The proposed mechanisms are invoked as soon as a user places a request or some of the allocated resources are released and become available. The mechanisms allocate VM instances to selected users for the period they are requested for, and ensure that the users will continue using their VM instances for the entire requested period. In addition, the mechanisms determine the payment the users have to pay for using the allocated resources. We prove that the mechanisms are incentive-compatible, that is, they give incentives to the users to reveal their true valuations for their requested bundles of VM instances. We investigate the performance of our proposed mechanisms through extensive experiments.

The big data trend is generating compute-intensive and data-intensive applications requiring unique services that are different from conventional computing services. Therefore, there is a need to fundamentally address such requirements by developing market mechanisms for managing, trading, and pricing big data computing services. The cloud computing platforms have a great potential to meet the economic requirements of market mechanisms for big data applications due to their technological advances, cost benefit ratios, and easy to use services. We design a two-sided mechanism for trading computing resources for big data applications. Our proposed mechanism is universally strategy-proof, providing incentives for both cloud providers and users to voluntarily reveal their true private information. We perform extensive experiments to evaluate our proposed mechanism.

The ever-growing demand for cloud resources places the resource management at the heart of the design and decision-making processes in cloud computing environments. Cloud providers offer heterogeneous resources such as CPUs, memory, and storage in the form of Virtual Machine (VM)instances. Recently, cloud providers have introduced auction-based models to sell their unutilized resources in an auction market which allow users to submit bids for their requested VMs. In this PhD dissertation, we address the problem of autonomic VM provisioning and allocation for the auction-based model considering multiple types of resources by designing exact and approximation mechanisms. The mechanisms also determine the payment the users have to pay for using the allocated resources. Furthermore, our proposed mechanisms drive the system into an equilibrium in which the users do not have incentives to manipulate the system by untruthfully reporting their VM bundle requests and valuations.

One of the benefits of cloud computing is that a cloud provider can dynamically scale-up its resource capabilities by forming a cloud federation with other cloud providers. Forming cloud federations requires taking the data privacy and security concerns into account, which is critical in satisfying the Service Level Agreements (SLAs). The nature of privacy and security challenges in clouds requires that cloud providers design data protection mechanisms that work together with their resource management systems. In this paper, we consider the privacy requirements when outsourcing data and computation within a federation of clouds, and propose a framework for minimizing the cost of outsourcing while considering two key data protection restrictions, the trust and disclosure restrictions. We model these restrictions as conflict graphs, and formulate the problem as an integer program. In the absence of computationally tractable optimal algorithms for solving this problem, we design a fast heuristic algorithm. We analyze the performance of our proposed algorithm through extensive experiments.

Service providers face multiple challenges in hosting an increasing number of virtual machine (VM) instances. Minimizing the utilization of system resources while maximizing the potential for profit are among the most common challenges. Recent studies have investigated memory reclamation techniques focused on virtual technologies, specifically page sharing, for minimizing the utilization of system resources. In this paper, we address the problem of sharing-aware VM maximization in a general sharing model which has as objective finding a subset of VMs that can be hosted by a server with a given memory capacity such that the total profit derived from hosting the subset of VMs is maximized. The sharing-aware VM maximization allocation problem has been shown to be NP-hard. Therefore, we design a greedy approximation algorithm for solving it. We determine the approximation ratio of our greedy algorithm and perform extensive experiments to investigate its performance against other VM allocation algorithms.

In a non-competitive environment, sporadic real-time task scheduling on a single processor is well understood. In this paper, we consider a competitive environment comprising several real-time tasks vying for execution upon a shared single processor. Each task obtains a value if the processor successfully schedules all its jobs. Our objective is to select a feasible subset of these tasks to maximize the sum of values of selected tasks. We consider both dynamic-priority and static-priority scheduling algorithms. There are algorithms for solving these problems in non-competitive settings. However, we consider these problems in an economic setting in which each task is owned by a selfish agent. Each agent reports the characteristics of her own task to the processor owner. The processor owner uses a mechanism to allocate the processor to a subset of agents and to determine the payment of each agent. Since agents are selfish, they may try to manipulate the mechanism to obtain the processor. We are interested in truthful mechanisms in which it is always in agents’ best interest to report the true characteristics of their tasks. We design exact and approximate truthful mechanisms for this competitive environment and study their performance.

Executing large-scale application programs in grids requires resources from several grid service providers (GSPs). These providers form virtual organizations (VOs) by pooling their resources together to provide the required capabilities to execute the application. We model the VO formation in grids using concepts from the coalitional game theory and design a mechanism for VO formation. The mechanism enables the GSPs to organize into VOs reducing the cost of execution and guaranteeing maximum profit for the GSPs. Furthermore, the mechanism guarantees that the VOs are stable, that is, the GSPs do not have incentives to break away from the current VO and join some other VO. We perform extensive simulation experiments using real-workload traces to characterize the properties of the proposed mechanism. The results show that the mechanism produces VOs that are stable yielding high revenue for the participating GSPs.

Abstract—Computing Nash equilibria is a very important problem in strategic analysis of markets, conflicts and resource allocation. Unfortunately, computing these equilibria even for moderately sized games is computationally expensive. To obtain faster execution times it is essential to exploit the available parallelism offered by the currently available massively parallel architectures. To address this issue, we design a GPU-based parallel support enumeration algorithm for computing Nash equilibria in bimatrix games. The algorithm is based on a new parallelization method which achieves high degrees of parallelism suitable for massively parallel GPU architectures. We perform extensive experiments to characterize the performance of the proposed algorithm. The algorithm achieves significant speedups relative to the OpenMP-based parallel implementation of the support enumeration method running on conventional multicore machines. I.

Designing efficient mechanisms for Virtual Machine (VM) provisioning and allocation is a major challenging problem that needs to be solved by cloud providers. We formulate the VM provisioning and allocation problem in clouds as an integer program and design truthful greedy mechanisms that solve it. We show that the proposed mechanisms are truthful, that is, the users do not have incentives to lie about their requested bundles of VM instances and their valuations. We perform extensive experiments in order to investigate the performance of the proposed mechanisms.

Cloud computing providers provision their resources into different types of virtual machine (VM) instances that are then allocated to the users for specific periods of time. The allocation of VM instances to users is usually determined through fixed-price allocation mechanisms that cannot guarantee an economically efficient allocation and the maximization of cloud provider's revenue. A better alternative would be to use combinatorial auction-based resource allocation mechanisms. This argument is supported by the economic theory; when the auction costs are low, as is the case in the context of cloud computing, auctions are especially efficient over the fixed-price markets because products are matched to customers having the highest valuation. The existing combinatorial auction-based VM allocation mechanisms do not take into account the user's demand when making provisioning decisions, that is, they assume that the VM instances are statically provisioned. We design an auction-based mechanism for dynamic VM provisioning and allocation that takes into account the user demand, when making provisioning decisions. We prove that our mechanism is truthful (i.e., a user maximizes its utility only by bidding its true valuation for the requested bundle of VMs). We evaluate the proposed mechanism by performing extensive simulation experiments using real workload traces. The experiments show that the proposed mechanism yields higher revenue for the cloud provider and improves the utilization of cloud resources.

Current cloud computing providers allocate their virtual machine (VM) instances via fixed price-based or auction-like mechanisms. However, these mechanisms have one limitation, they are all offline mechanisms, therefore they need to collect information and be invoked periodically. In this paper, we address this limitation by designing an online mechanism for dynamic provisioning and allocation of VM instances in clouds. Our proposed mechanism, MOVMPA, is invoked as soon as a user places a request or some VM instances already allocated become available again. When invoked, the mechanism selects users who would be allocated VM instances for the period they requested for, and ensures that those users will continue using those VMs for the entire period requested. We prove that the mechanism is incentive compatible and also investigate its performance through extensive simulation experiments.

Current cloud providers use fixed-price based mechanisms to allocate Virtual Machine (VM) instances to their users. The fixed-price based mechanisms do not provide an efficient allocation of resources and do not maximize the revenue of the cloud providers. A better alternative would be to use combinatorial auction-based resource allocation mechanisms. In this PhD dissertation we will design, study and implement combinatorial auction-based mechanisms for efficient provisioning and allocation of VM instances in cloud computing environments. We present our preliminary results consisting of three combinatorial auction-based mechanisms for VM provisioning and allocation. We also present an efficient bidding algorithm that can be used by the cloud users to decide on how to bid for their requested bundles of VM instances.

In a non-competitive environment, sporadic real time task scheduling on a single processor is well understood. In this paper, we consider a competitive environment comprising several real-time tasks vying for execution upon a shared single processor. Each task obtains a value if the processor successfully schedules all its jobs. Our objective is to select a feasible subset of these tasks to maximize the sum of values of selected tasks. There are algorithms for solving this problem in non-competitive settings. However, we consider this problem in an economic setting in which each task is owned by a selfish agent. Each agent reports the characteristics of her own task to the processor owner. The processor owner uses a mechanism to allocate the processor to a subset of agents and to determine the payment of each agent. Since agents are selfish, they may try to manipulate the mechanism to obtain the processor. We are interested in truthful mechanisms in which it is always in agents' best interest to report the true characteristics of their tasks. We design exact and approximate truthful mechanisms for this competitive environment and study their performance.

In order to execute large scale applications programs in grids, several Grid Service Providers (GSPs) pool their resources together by forming Virtual Organizations (VOs). Forming such VOs is a challenging problem especially when the trust relationships among GSPs have to be considered. In this paper, we model the formation of VOs in grids by considering the trust and reputation of the participating GSPs. We design a mechanism for VO formation that enables the GSPs with high reputation to organize into a VO reducing the cost of execution and guaranteeing the maximum profit for the participating GSPs. Furthermore, the mechanism guarantees that the formed VO is stable, that is, the GSPs that are part of the VO do not have incentives to break away from it. We perform extensive simulation experiments using real workload traces to characterize the properties of the proposed mechanism. The results show that the mechanism produces stable VOs composed of GSPs with high reputation that obtain high individual profits.

Computing Nash equilibria is a very important problem in strategic analysis of markets, conflicts and resource allocation. Unfortunately, computing these equilibria even for moderately sized games is computationally expensive. To obtain faster execution times it is essential to exploit the available parallelism offered by the currently available massively parallel architectures. To address this issue, we design a GPU-based parallel support enumeration algorithm for computing Nash equilibria in bimatrix games. The algorithm is based on a new parallelization method which achieves high degrees of parallelism suitable for massively parallel GPU architectures. We perform extensive experiments to characterize the performance of the proposed algorithm. The algorithm achieves significant speedups relative to the OpenMP-based parallel implementation of the support enumeration method running on conventional multicore machines.

We model the Virtual Organization (VO) formation problem in grids using concepts from coalitional game theory and design a distributed mechanism for solving it. The proposed distributed mechanism enables the formation of VOs guaranteeing the maximum profit for their participating Grid Service Providers (GSPs). We show that the proposed mechanism produces stable VOs, that is, the GSPs do not have incentives to break away from the current VO and join some other VO. We perform extensive simulation experiments using real workload traces to characterize the properties of the proposed distributed mechanism. The results show that the proposed distributed mechanism not only produces VOs that are stable yielding high revenue for the participating GSPs, but also decides the structure of the VOs in a reasonable amount of time.

Modern real-time embedded systems often require the capability of switching between operating modes to adapt in dynamically changing environments. The development of such real-time multi-modal systems fundamentally relies upon effective schedulability analysis. Recently, researchers have proposed serial schedulability analysis algorithms for multi-modal systems that account for mode changes at both software level (e.g., changing the set of executing tasks) and hardware level (e.g., changing the operating speed of a processor). However, these algorithms have high runtime complexity which limits their practical usage as schedulability analysis in system design-space exploration. In this paper, we design a parallel algorithm as an efficient solution to the problem of determining the schedulability of uniprocessor multi-modal real-time systems scheduled by EDF. By emphasizing a balanced workload distribution and restricting the number of synchronizations, our parallel algorithm achieves a near-perfect speedup observable both theoretically and experimentally. Experimental results show that the runtime of our parallel algorithm is very low even for systems with large number of modes, making it a tractable choice for design-space exploration of real-time multi-modal systems.

Combinatorial auctions are efficient mechanisms for allocating Virtual Machine (VM)instances to cloud computing users. Despite the fact that in general these mechanisms lead to higher revenues than the currently employed fixed-price mechanisms, the cloud computing providers do not employ them to allocate their resources. One of the main reasons is the complexity faced by the users when determining the bid (i.e., the bundle of VM instances and the bid value). We address this issue by developing an efficient bidding strategy for the users requesting VM instances. We design new metrics for evaluating bundles of VM instances based on the characteristics of the computing tasks. These metrics allow us to determine the valuation of the requested bundles and to design algorithms for selecting the best bundles to bid for. We perform simulation experiments to evaluate the proposed strategy in a simulated cloud environment.

Efficient Virtual Machine (VM) provisioning and allocation allows the cloud providers to effectively utilize their available resources and obtain higher profits. Existing combinatorial auction-based mechanisms assume that the VM instances are already provisioned, that is they assume static VM provisioning. A better solution would be to take into account the users' demand when provisioning VM instances. We design an auction-based mechanism for dynamic VM provisioning and allocation that takes into account the user demand for VMs when making VM provisioning decisions. We perform extensive simulation experiments using real workload traces and show that the proposed mechanism can improve the utilization, increase the efficiency of allocation, and yield higher revenue for the cloud provider.

Executing large scale application programs in grids requires resources from several Grid Service Providers (GSPs). These providers form Virtual Organizations (VOs) by pooling their resources together to provide the required capabilities to execute the application. We model the VO formation in grids using concepts from coalitional game theory and design a mechanism for VO formation. The mechanism enables the GSPs to organize into VOs reducing the cost of execution and guaranteeing maximum profit for the GSPs. Furthermore, the mechanism guarantees that the VOs are stable, that is, the GSPs do not have incentives to break away from the current VO and join some other VO. We perform extensive simulations to characterize the properties of the proposed mechanism. The results show that the mechanism produces VOs that are stable yielding high revenue for the participating GSPs.

Abstract We perform a game theoretic investigation of the effects of deception on the interactions between an attacker and a defender of a computer network. The defender can employ camouflage by either disguising a normal system as a honeypot or by disguising a honeypot as a normal system. We model the interactions between defender and attacker using a signaling game, a non‐cooperative two player dynamic game of incomplete information. For this model, we determine which strategies admit perfect Bayesian equilibria. These equilibria are refined Nash equilibria in which neither the defender nor the attacker will unilaterally choose to deviate from their strategies. We discuss the benefits of employing deceptive equilibrium strategies in the defense of a computer network. Copyright © 2010 John Wiley & Sons, Ltd.

Caching and replication of popular data objects contribute significantly to the reduction of the network bandwidth usage and the overall access time to data. Our focus is to improve the efficiency of object replication within a given distributed replication group. Such a group consists of servers that dedicate certain amount of memory for replicating objects requested by their clients. The content replication problem we are solving is defined as follows: Given the request rates for the objects and the server capacities, find the replica allocation that minimizes the access time over all servers and objects. We design a distributed approximation algorithm that solves this problem and prove that it provides a 2-approximation solution. We also show that the communication and computational complexity of the algorithm is polynomial with respect to the number of servers, the number of objects, and the sum of the capacities of all servers. Finally, we perform simulation experiments to investigate the performance of our algorithm. The experiments show that our algorithm outperforms the best existing distributed algorithm that solves the replica placement problem.

The current cloud computing platforms allocate virtual machine instances to their users through fixed-price allocation mechanisms. We argue that combinatorial auction-based allocation mechanisms are especially efficient over the fixed-price mechanisms since the virtual machine instances are assigned to users having the highest valuation. We formulate the problem of virtual machine allocation in clouds as a combinatorial auction problem and propose two mechanisms to solve it. We perform extensive simulation experiments to compare the two proposed combinatorial auction-based mechanisms with the currently used fixed-price allocation mechanism. Our experiments reveal that the combinatorial auction-based mechanisms can significantly improve the allocation efficiency while generating higher revenue for the cloud providers.

We consider the online scheduling of malleable jobs on parallel systems, such as clusters, symmetric multiprocessing computers, and multi-core processor computers. Malleable jobs is a model of parallel processing in which jobs adapt to the number of processors assigned to them. This model permits the scheduler and resource manager to make more efficient use of the available resources. Each malleable job is characterized by arrival time, deadline, and value. If the job completes by its deadline, the user earns the payoff indicated by the value; otherwise, she earns a payoff of zero. The scheduling objective is to maximize the sum of the values of the jobs that complete by their associated deadlines. Complicating the matter is that users in the real world are rational and they will attempt to manipulate the scheduler by misreporting their jobs' parameters if it benefits them to do so. To mitigate this behavior, we design an incentive compatible online scheduling mechanism. Incentive compatibility assures us that the users will obtain the maximum payoff only if they truthfully report their jobs' parameters to the scheduler. Finally, we simulate and study the mechanism to show the effects of misreports on the cheaters and on the system.

Abstract Applications require the composition of resources to execute in a grid computing environment. The grid service providers (GSPs), the owners of the computational resources, must form virtual organizations (VOs) to be able to provide the composite resource. We consider grids as self‐organizing systems composed of autonomous, self‐interested GSPs that will organize themselves into VOs with every GSP having the objective of maximizing its profit. Using game theory, we formulate the resource composition among GSPs as a coalition formation problem and propose a framework to model and solve it. Using this framework, we propose a resource management system that supports the VO formation among GSPs in a grid computing system. Copyright © 2008 John Wiley & Sons, Ltd.

We perform a game theoretic investigation of the effects of deception on the interactions between an attacker and a defender of a computer network. The defender can employ camouflage by either disguising a normal system as a honeypot, or by disguising a honeypot as a normal system. We model the interactions between defender and attacker using a signaling game, a non-cooperative two player dynamic game of incomplete information. For this model, we determine which strategies admit perfect Bayesian equilibria. These equilibria are refined Nash equilibria in which neither the defender nor the attacker will unilaterally choose to deviate from their strategies. We discuss the benefits of employing deceptive equilibrium strategies in the defense of a computer network.

Equilibria computation is of great importance to many areas such as economics, control theory, and recently computer science. We focus on the computation of Nash equilibria in two-player general-sum normal form games, also called bimatrix games. One efficient method to compute these equilibria is based on enumerating the vertices of the best response polyhedrons of the two players and checking the equilibrium conditions for every pair of vertices. We design and implement a parallel algorithm for computing Nash equilibria in bimatrix games based on vertex enumeration. We analyze the performance of the proposed algorithm by performing extensive experiments on a grid computing system.

Web caching and replication techniques increase accessibility of Web contents and reduce Internet bandwidth requirements. In this paper, we are considering the replica placement problem in a distributed replication group. The replication group consists of servers dedicating certain amount of memory for replicating objects. The replica placement problem is to place the replica at the servers within the replication group such that the access time over all objects and servers is minimized. We design a distributed 2-approximation algorithm that solves this optimization problem. We show that the communication and computational complexity of the algorithm is polynomial in the number of servers and objects. We perform simulation experiments to investigate the performance of our algorithm.

The problem of sharing the cost of multicast transmissions was studied in the past, and two mechanisms, marginal cost (MC) and Shapley value (SH), were proposed to solve it. Although both of them are strategy proof mechanisms, the distributed protocols implementing them are susceptible to manipulation by autonomous nodes. We propose a distributed Shapley value mechanism in which the participating nodes do not have incentives to deviate from the mechanism specifications. We show that the proposed mechanism is a faithful implementation of the Shapley value mechanism. We experimentally investigate the performance of the existing and the proposed cost-sharing mechanisms by implementing and deploying them on PlanetLab. We compare the execution time of MC and SH mechanisms for the tamper-proof and autonomous node models. We also study the convergence and scalability of the mechanisms by varying the number of nodes and the number of users per node. We show that the MC mechanisms generate a smaller revenue compared to the SH mechanisms, and thus, they are not attractive to the content provider. We also show that increasing the number of users per node is beneficial for the systems implementing the SH mechanisms from both computational and economic perspectives.

We design an incentive-compatible mechanism for schedulingn non-malleable parallel jobs on a parallel system comprising m identical processors. Each job is owned by a selfish user who is rational: she performs actions that maximize her welfare even though doing so may cause system-wide suboptimal performance. Each job is characterized by four parameters: value, deadline, number of processors, and execution time. The user's welfare increases by the amount indicated by the value if her job can be completed by the deadline. The user declares theparameters to the mechanism which uses them to compute the schedule and the payments. The user can misreport the parameters, but since the mechanism is incentive-compatible, she chooses to truthfully declare them. We prove the properties of the mechanism and perform a study by simulation.

We consider the problem of computing all Nash equilibria in bimatrix games (i.e., nonzero-sum two-player noncooperative games). Computing all Nash equilibria for large bimatrix games using single-processor computers is not feasible due to the exponential time required by the existing algorithms. We consider the use of parallel computing which allows us to solve larger games. We design and implement a parallel algorithm for computing all Nash Equilibria in bimatrix games. The algorithm computes all Nash equilibria by searching all possible supports of mixed strategies. We perform experiments on a cluster computing system to evaluate the performance of the parallel algorithm.

Abstract A serious difficulty in concurrent programming of a distributed system is how to deal with scheduling and load balancing of such a system which may consist of heterogeneous computers. In this paper, we formulate the static load‐balancing problem in single class job distributed systems as a cooperative game among computers. The computers comprising the distributed system are modeled as M/M/1 queueing systems. It is shown that the Nash bargaining solution (NBS) provides an optimal solution (operation point) for the distributed system and it is also a fair solution. We propose a cooperative load‐balancing game and present the structure of NBS. For this game an algorithm for computing NBS is derived. We show that the fairness index is always equal to 1 using NBS, which means that the solution is fair to all jobs. Finally, the performance of our cooperative load‐balancing scheme is compared with that of other existing schemes. Copyright © 2008 John Wiley & Sons, Ltd.

The scheduling of arbitrarily divisible loads on a distributed system is studied by Divisible Load Theory (DLT). DLT has the underlying assumption that the processors will not cheat. In the real world, this assumption is unrealistic as the processors are owned and operated by autonomous rational organizations that have no a priori motivation for cooperation. Consequently, they will manipulate the algorithms if it benefits them to do so. In this work, we propose strategyproof mechanisms for scheduling divisible loads on three types of bus-connected distributed systems. These mechanisms provide incentives to the processors to obey the prescribed algorithms and to truthfully report their parameters, leading to an efficient load allocation and execution.

In this paper we investigate experimentally the performance of marginal cost (MC) and Shapley value (SH) mechanisms for sharing the cost of multicast transmissions. We implement and deploy the MC and SH mechanisms on PlanetLab and study their properties. We compare the execution time of MC and SH mechanisms for the tamper-proof and autonomous node models. We also study the convergence and scalability of the mechanisms by varying the number of nodes and the number of users per node. We show that the MC mechanisms generate a smaller revenue compared to the SH mechanisms and thus they are not favorable for the content provider. From the computational point of view as well as economic considerations, increasing the number of users per node is beneficial for the system implementing these mechanisms.

In this paper we augment DLT (divisible load theory) with incentives such that it is beneficial for processors to report their true processing capacity and compute their assignments at full capacity. We propose a strategyproof mechanism with verification for scheduling divisible loads in linear networks with boundary load origination. The mechanism provides incentives to processors for reporting deviants. The deviants are penalized which abates their willingness to deviate in the first place. We prove that the mechanism is strategyproof and satisfies the voluntary participation condition.

Sharing the cost of multicast transmissions was studied in the past and two mechanisms, Marginal Cost and Shapley Value, were proposed. Compared to the Marginal Cost Mechanism the Shapley Value mechanism has the advantage of being budget balanced. Although both of them are strategyproof mechanisms, the distributed protocols implementing them are susceptible to manipulation by autonomous nodes. We propose two protocols that implement the Shapley Value mechanism in which the nodes do not have incentives to deviate from the protocol specifications. We show that the proposed protocols are faithful implementations of the Shapley Value mechanism. We deploy these protocols on PlanetLab and analyze their performance.

Scheduling divisible loads in distributed systems is the subject of divisible load theory (DLT). In this paper we show that coalitional game theory is a natural fit for modeling DLT as the participants in the scheduling algorithm must cooperate in order to execute a job. We devise a coalitional scheduling game in which the job owners and the independent organizations that own processors form coalitions in order to maximize their profits. We examine the payoffs to the participants and show that the core of the proposed coalitional scheduling game is non-empty. Then we examine the "fair sharing" of the payoffs among the participants using the Shapley value. Finally we study by simulation the properties of the proposed coalitional scheduling game considering different distributed systems configurations.

No abstract available.

Truthful task scheduling mechanisms are designed to cope with the selfishness of the participating agents. They assume that the agents are selfish; each agent's goal is to maximize its own profit. However, this is not always the case; an agent may want to cause losses to the other agents besides maximizing its profit. Such an agent is said to be an antisocial agent. An antisocial agent will try to gain as much profit as possible relative to the other agents. This paper presents an antisocial strategy which can be used by the antisocial agents to inflict losses on the other agents participating in a task scheduling mechanism on related machines. This paper also studies, by simulation, the effect of different parameters, such as the degree of antisociality on the relative losses that can be inflicted on the participating agents.

Grid technologies enable the sharing and coordinated use of diverse resources distributed all over the world. These resources are owned by different organizations having different policies and objectives, which need to be considered in making the resource allocation decisions. In such complex environments, market-based resource allocation protocols are a better alternative to the classical ones because they take into consideration the policies and preferences of both users and resource owners. The only suitable solution for investigating the effectiveness of these resource allocation protocols over a wide range of scenarios with reproducible results is to consider simulations. Thus, in this paper we present Mercatus, a simulation toolkit that facilitates the simulation of market-based resource allocation protocols. We describe the model and the structure of Mercatus, and present experimental results obtained by simulating five types of auction-based resource allocation protocols.

Divisible load theory (DLT) considers the scheduling of arbitrarily partitionable loads in distributed systems. The underlying assumption of DLT is that the processors are obedient (i.e., they do not "cheat" the protocol), which is unrealistic when the processors are owned by autonomous, self-interested organizations that have no a priori motivation for cooperation and which strive to maximize their own welfare. In this scenario, they will manipulate the algorithm if it is beneficial to do so. In this paper, we propose a strategy proof mechanism for scheduling divisible loads in bus networks without control processors. We augment DLT with incentives so that it is to the benefit of a processor to truthfully report its processing capacity and to process its assignment at full capacity. The mechanism provides incentives to processors for reporting deviants and issues fines to deviants, which results in abated willingness to deviate

Divisible Load Theory (DLT) considers the scheduling of arbitrarily partitionable loads in distributed systems. The underlying assumption of DLT is that the processors are obedient (i.e., they do not “ cheat” the protocol), which is unrealistic when the processors are owned by autonomous, self-interested organizations that have no a priori motivation for cooperation and which strive to maximize their own welfare. In this scenario, they will manipulate the algorithm if it is beneficial to do so. In this paper we propose a strategyproof mechanism for scheduling divisible loads in bus networks without control processors. We augment DLT with incentives so that it is to the benefit of a processor to truthfully report its processing capacity and to process its assignment at full capacity. The mechanism provides incentives to processors for reporting deviants and issues fines to deviants, which results in abated willingness to deviate.

In this paper we formulate and study a new scheduling problem called selfish multi-user task scheduling. This problem assumes that there are several users, each of them having multiple tasks that need processing on a set of parallel identical machines. Each user is selfish and her goal is to minimize the makespan of her own tasks. We model this problem as a non-cooperative, extensive-form game. We use the subgame perfect equilibrium solution concept to analyze the game which provides insight into the problem's properties. We compute the price of anarchy to quantify the costs due to lack of coordination among the users

The focus of this study is how we can efficiently implement the neural network backpropagation algorithm on a network of computers (NOC) for concurrent execution. We assume a distributed system with heterogeneous computers and that the neural network is replicated on each computer. We propose an architecture model with efficient pattern allocation that takes into account the speed of processors and overlaps the communication with computation. The training pattern set is distributed among the heterogeneous processors with the mapping being fixed during the learning process. We provide a heuristic pattern allocation algorithm minimizing the execution time of backpropagation learning. The computations are overlapped with communications. Under the condition that each processor has to perform a task directly proportional to its speed, this allocation algorithm has polynomial-time complexity. We have implemented our model on a dedicated network of heterogeneous computers using Sejnowski's NetTalk benchmark for testing. Copyright © 2005 John Wiley & Sons, Ltd.

In this paper, we propose and study an auction model for resource management in Grids. We propose and investigate by simulation three types of auction-based resource-allocation protocols: (i) first-price auction protocol; (ii) Vickrey auction protocol; and (iii) double auction protocol. The goal is to find which of these is best suited to the Grid environment from the users' perspective as well as from the resources' perspective. The results showed that when we consider a mix of risk-averse and risk-neutral users, the first-price auction protocol favors resources while the Vickrey auction protocol favors users. On the other hand, the double auction protocol favors both users and resources. Copyright © 2006 John Wiley & Sons, Ltd.

An important scheduling problem is the one in which there are no dependencies between tasks and the tasks can be of arbitrary size. This is known as the divisible load scheduling problem and was studied extensively resulting in a cohesive theory called divisible load theory (DLT). In this paper, we augment the existing divisible load theory with incentives. We develop a strategyproof mechanism for scheduling divisible loads in distributed systems assuming a bus type interconnection and a linear cost model for the processors. The mechanism provides incentives to processors such that it is beneficial for them to report their true processing power and process the assigned load using their full processing capacity. We define the strategyproof mechanism and prove its properties. We simulate and study the implementation of the mechanism on systems characterized by different parameters

No abstract available.

As grids become more available and mature in real world settings, users are faced with considerations regarding the efficiency of applications and their capability of utilizing additional nodes distributed over a wide area network. When both tightly coupled clusters and loosely gathered grids are available, a cost effective organization will schedule applications that can execute with minimal performance degradation over wide-area networks on grids, while reserving clusters for applications with high communication costs. We analyze the performance of the NAS parallel benchmarks using both MPICH-G2 and MPICH with the ch/spl I.bar/p4 device. We compare the results of these communication devices on both tightly and loosely coupled systems, and present an analysis of how parallel applications perform in real-world environments. We make recommendations as to where applications run most efficiently, and under what conditions.

Computational grids are promising next-generation computing platforms for large-scale problems in science and engineering. Grids are large-scale computing systems composed of geographically distributed resources (computers, storage etc.) owned by self interested agents or organizations. These agents may manipulate the resource allocation algorithm in their own benefit, and their selfish behavior may lead to severe performance degradation and poor efficiency. In this paper, we investigate the problem of designing protocols for resource allocation involving selfish agents. Solving this kind of problems is the object of mechanism design theory. Using this theory, we design a truthful mechanism for solving the static load balancing problem in heterogeneous distributed systems. We prove that using the optimal allocation algorithm the output function admits a truthful payment scheme satisfying voluntary participation. We derive a protocol that implements our mechanism and present experiments to show its effectiveness.

In this paper we consider the problem of designing load balancing protocols in distributed systems where the participants (e.g. computers, users) are capable of manipulating the load allocation algorithm in their own interest. Using techniques from mechanism design theory we design a mechanism for fair load balancing in heterogeneous distributed systems. We prove that our mechanism is truthful and satisfies the voluntary participation condition. Based on the proposed mechanism we derive a fair load balancing protocol called FAIR-LBM. Finally, we study the effectiveness of our protocol by simulations.

Computational grids are large scale computing systems composed of geographically distributed resources (computers, storage etc.) owned by self interested agents or organizations. These agents may manipulate the resource allocation algorithm for their own benefit and their selfish behavior may lead to severe performance degradation and poor efficiency. In this paper we investigate the problem of designing protocols for resource allocation involving selfish agents. Solving this kind of problem is the object of mechanism design theory. Using this theory we design a truthful mechanism for solving the static load balancing problem in heterogeneous distributed systems. We prove that by using the optimal allocation algorithm the output function admits a truthful payment scheme satisfying voluntary participation. We derive a protocol that implements our mechanism and present experiments to show its effectiveness.

Distributed Computing Systems are a viable and less expensive alternative to parallel computers. However, a serious difficulty in concurrent programming of a distributed system is how to deal with scheduling and load balancing of such a system which may consist of heterogeneous computers. Distributed scheduling schemes suitable for parallel loops with independent iterations on heterogeneous computer clusters have been designed in the past. In this work we consider a class of Self-Scheduling schemes for parallel loops with independent iterations which have been applied to multiprocessor systems. We extend this type of schemes to heterogeneous distributed systems. We present tests that the distributed versions of these schemes maintain load balanced execution on heterogeneous systems.

In distributed simulations, the delivered performance of networks of heterogeneous computers degrades severely if the computations are not load balanced. In this work we consider the distributed simulation of TURNS (Transonic Unsteady Rotor Navier Stokes), a 3-D space CFD code. We propose a load balancing heuristic for simulations on networks of heterogeneous workstations. Our algorithm takes into account the CPU speed and memory capacity of the workstations. Test run comparisons with the equal task allocation algorithm demonstrated significant efficiency gains.