Conformal inference provides a general distribution-free method to rigorously calibrate the output of any machine learning algorithm for novelty detection. While this approach has many strengths, it has the limitation of being randomized, in the sense that it may lead to different results when analyzing twice the same data and this can hinder the interpretation of any findings. We propose to make conformal inferences more stable by leveraging suitable conformal e-values instead of p-values to quantify statistical significance. This solution allows the evidence gathered from multiple analyses of the same data to be aggregated effectively while provably controlling the false discovery rate. Further, we show that the proposed method can reduce randomness without much loss of power compared to standard conformal inference, partly thanks to an innovative way of weighting conformal e-values based on additional side information carefully extracted from the same data. Simulations with synthetic and real data confirm this solution can be effective at eliminating random noise in the inferences obtained with state-of-the-art alternative techniques, sometimes also leading to higher power.

The adoption of deduplication in storage systems has introduced significant new challenges for storage management. Specifically, the physical capacities associated with volumes are no longer readily available. In this work, we introduce a new approach to analyzing capacities in deduplicated storage environments. We provide sketch-based estimations of fundamental capacity measures required for managing a storage system: How much physical space would be reclaimed if a volume or group of volumes were to be removed from a system (the reclaimable capacity) and how much of the physical space should be attributed to each of the volumes in the system (the attributed capacity). Our methods also support capacity queries for volume groups across multiple storage systems, e.g., how much capacity would a volume group consume after being migrated to another storage system? We provide analytical accuracy guarantees for our estimations as well as empirical evaluations. Our technology is integrated into a prominent all-flash storage array and exhibits high performance even for very large systems. We also demonstrate how this method opens the door for performing placement decisions at the data-center level and obtaining insights on deduplication in the field.

Cache replacement policies comprise one of the oldest and most researched topic in computer science. But recent advances in the fields of artificial intelligence and machine learning introduce novel insight and new opportunities which can benefit prefetching and cache replacement policies.

Production and distribution are fundamental operational functions in supply chains. The main challenge is to design algorithms that optimize operational performance by jointly scheduling production and delivery of customer orders. In this paper we study a model of scheduling customer orders on multiple identical machines and their distribution to customers afterwards. The goal is to minimize the total time from release to distribution plus total distribution cost to the customers. We design the first poly-logarithmic competitive algorithm for the problem, improving upon previous algorithms with linear competitive ratios. Our model generalizes two fundamental problems: scheduling of jobs on multiple identical machines (where the goal function is to minimize the total flow time) as well as the TCP Acknowledgment problem.

It is hard to measure the reliability of a large distributed storage system, since it is influenced by low probability failure events that occur over time. Nevertheless, it is critical to be able to predict reliability in order to plan, deploy and operate the system. Existing approaches suffer from unrealistic assumptions regarding network bandwidth. This paper introduces a new framework that combines simulation and an analytic model to estimate durability for large distributed cloud storage systems. Our approach is the first that takes into account network bandwidth with a focus on the cumulative effect of simultaneous failures on repair time. Using our framework we evaluate the trade-offs between durability, network and storage costs for the OpenStack Swift object store, comparing various system configurations and resiliency schemes, including replication and erasure coding. In particular, we show that when accounting for the cumulative effect of simultaneous failures, the probability of data loss estimates can vary by two to four orders of magnitude.

One of the key enablers of a cloud provider competitiveness is ability to over-commit shared infrastructure at ratios that are higher than those of other competitors, without compromising non-functional requirements, such as performance. A widely recognized impediment to achieving this goal is so called "Virtual Machines sprawl", a phenomenon referring to the situation when customers order Virtual Machines (VM) on the cloud, use them extensively and then leave them inactive for prolonged periods of time. Since a typical cloud provisioning system treats new VM provision requests according to the nominal virtual hardware specification, an often occurring situation is that the nominal resources of a cloud/pool become exhausted fast while the physical hosts utilization remains low.We present a novel cloud resources scheduler called Pulsar that extends OpenStack Nova Filter Scheduler. The key design principle of Pulsar is adaptivity. It recognises that effective safely attainable over-commit ratio varies with time due to workloads' variability and dynamically adapts the effective over-commit ratio to these changes. We evaluate Pulsar via extensive simulations and demonstrate its performance on the actual OpenStack based testbed running popular workloads.

Optimal resource allocation is a key ingredient in the ability of cloud providers to offer agile data centers and cloud computing services at a competitive cost. In this paper we study the problem of placing images and virtual machine instances on physical containers in a way that maximizes the affinity between the images and virtual machine instances created from them. This reduces communication overhead and latency imposed by the on-going communication between the virtual machine instances and their respective images. We model this problem as a novel placement problem that extends the class constrained multiple knapsack problem (CCMK) previously studied in the literature, and present a polynomial time local search algorithm for the case where all the relevant images have the same size. We prove that this algorithm has an approximation ratio of (3 + ∈) and then evaluate its performance in a general setting where images and virtual machine instances are of arbitrary sizes, using production data from a private cloud. The results indicate that our algorithm can obtain significant improvements (up to 20%) compared to the greedy approach, in cases where local image storage or main memory resources are scarce.

In this paper we study the “price of anarchy" for the general class of (weighted and unweighted) atomic “congestion games" with the sum of players' costs as the objective function. We show that for linear resource cost functions the price of anarchy is exactly $\frac{3 + \sqrt{5}}{2} \approx 2.618$ for weighted congestion games and exactly $2.5$ for unweighted congestion games. We show that for resource cost functions that are polynomials of degree $d$ the price of anarchy is $d^{\Theta(d)}$. Our results also hold for mixed strategies. In particular, these results apply to atomic routing games where the traffic demand from a source to a destination must be satisfied by choosing a single path between source and destination.

Current trends in virtualization, green computing, and cloud computing require ever increasing efficiency in consolidating virtual machines without degrading quality of service. In this work, we consider consolidating virtual machines on the minimum number of physical containers (e.g., hosts or racks) in a cloud where the physical network (e.g., network interface or top of the rack switch link) may become a bottleneck. Since virtual machines do not simultaneously use maximum of their nominal bandwidth, the capacity of the physical container can be multiplexed. We assume that each virtual machine has a probabilistic guarantee on realizing its bandwidth Requirements-as derived from its Service Level Agreement with the cloud provider. Therefore, the problem of consolidating virtual machines on the minimum number of physical containers, while preserving these bandwidth allocation guarantees, can be modeled as a Stochastic Bin Packing (SBP) problem, where each virtual machine's bandwidth demand is treated as a random variable. We consider both offline and online versions of SBP. Under the assumption that the virtual machines' bandwidth consumption obeys normal distribution, we show a 2-approximation algorithm for the offline version and improve the previously reported results by presenting a (2 +∈)-competitive algorithm for the online version. We also observe that a dual polynomial-time approximation scheme (PTAS) for SBP can be obtained via reduction to the two-dimensional vector bin packing problem. Finally, we perform a thorough performance evaluation study using both synthetic and real data to evaluate the behavior of our proposed algorithms, showing their practical applicability.

Elastic services comprise multiple virtualized resources that can be added and deleted on demand to match variability in the workload. A Service owner profiles the service to determine its most appropriate sizing under different workload conditions. This variable sizing is formalized through a service level agreement (SLA) between the service owner and the cloud provider. The Cloud provider obtains maximum benefit when it succeeds to fully allocate the resource set demanded by the elastic service subject to its SLA. Failure to do so may result in SLA breach and financial losses to the provider. We define a novel combinatorial optimization problem called elastic services placement problem (ESPP) to maximize the provider's benefit from SLA compliant placement. We observe that ESPP extends the generalized assignment problem (GAP), which is a well studied combinatorial optimization problem. However, ESPP turns out to be considerably harder to solve as it does not admit a constant factor approximation. We show that using a simple transformation, ESPP can be presented as a multi-unit combinatorial auction. We further present a column generation method to obtain near optimal solutions for ESPP for large data centers where exact solutions cannot be obtained in a reasonable amount of time using a direct integer programming formulation. We demonstrate the feasibility of our approach through an extensive simulation study. Our results show that we are capable of consistently obtaining good solutions in a time efficient manner. Moreover, if one is willing to trade precision to gain in computation time, our method allows to explicitly manage this tradeoff.

Cloud Computing in general and Virtualized Infrastructure Provisioning in particular, are significant trends with the potential to increase agility and lower costs of IT. An emerging cloud service is a virtual server shop, that allows cloud customers to order virtual appliances to be delivered virtually on the cloud. Like physical shops, customers want to customize the ordered products, e.g., have them pre-installed with their desired applications and pre-configured. Global cloud providers need to create customized virtual-server disk images and deliver them on time to meet the customer reservations and service level. This framework creates a new flavor of content distribution over the web, where large virtual server images need to be delivered to the target compute farms (either on the global cloud or on customer private clouds). In order to reduce provisioning time and meet reservation deadlines, one approach is to stage images on storage near the customer. This introduces an optimization problem of finding an optimal staging schedule, according to network bandwidth, pending reservations schedule, and customer value. This problem has some similarities to cache pre-filling and production-line scheduling. It combines scheduling, bandwidth considerations, and storage capacity constraints. In this paper we study the fundamental properties of this approach and formalize several flavors of the related optimization problem. We prove useful properties of the problem and then use those properties to provide exact efficient algorithms to solve it. We also derive efficient approximate solutions with proven error bounds.

We study the speed of convergence of decentralized dynamics to approximately optimal solutions in potential games. We consider α-Nash dynamics in which a player makes a move if the improvement in his payoff is more than an α factor of his own payoff. Despite the known polynomial convergence of α-Nash dynamics to approximate Nash equilibria in symmetric congestion games [7], it has been shown that the convergence time to approximate Nash equilibria in asymmetric congestion games is exponential [25]. In contrast to this negative result, and as the main result of this paper, we show that for asymmetric congestion games with linear and polynomial delay functions, the convergence time of α-Nash dynamics to an approximate optimal solution is polynomial in the number of players, with approximation ratio that is arbitrarily close to the price of anarchy of the game. In particular, we show this polynomial convergence under the minimal liveness assumption that each player gets at least one chance to move in every T steps. We also prove that the same polynomial convergence result does not hold for (exact) best-response dynamics, showing the α-Nash dynamics is required. We extend these results for congestion games to other potential games including weighted congestion games with linear delay functions, cut games (also called party affiliation games) and market sharing games.

In this work we study cost sharing connection games, where each player has a source and sink he would like to connect, and the cost of the edges is either shared equally (fair connection games) or in an arbitrary way (general connection games).We study the graph topologies that guarantee the existence of a strong equilibrium (where no coalition can improve the cost of eachof its members) regardless of the specific costs on the edges.Our main existence results are the following: (1) For a single source and sink we show that there is always a strong equilibrium (both for fair and general connection games). (2) For a single source multiple sinks we show that for a series parallel graph a strong equilibrium always exists (both for fair and general connection games). (3) For multi source and sink we show that an extension parallel graph always admits a strong equilibrium in fair connection games.As for the quality of the strong equilibrium we show that in any fair connection games the cost of a strong equilibrium is Θ(log n) from the optimal solution, where n is the number of players. (This should be contrasted with the Ω(n) price of anarchy for the same setting.) For single source general connection games and single source single sink fair connection games, we show that a strong equilibrium is always an optimal solution.

We study the Unsplittable Flow Problem (UFP) on line graphs and cycles, focusing on the long-standing open question of whether the problem is APX-hard. We describe a deterministic quasi-polynomial time approximation scheme for UFP on line graphs, thereby ruling out an APX-hardness result, unless NP ⊆ DTIME(2polylog(n)). Our result requires a quasi-polynomial bound on all edge capacities and demands in the input instance. We extend this result to undirected cycle graphs.Earlier results on this problem included a polynomial time (2+ε)-approximation under the assumption that no demand exceeds any edge capacity (the "no-bottleneck assumption") and a super-constant integrality gap if this assumption did not hold. Unlike most earlier work on UFP, our results do not require a no-bottleneck assumption.

The essence of the routing problem in real networks is that the traffic demand from a source to destination must be satisfied by choosing a single path between source and destination. The splittable version of this problem is when demand can be satisfied by many paths, namely a flow from source to destination. The unsplittable, or discrete version of the problem is more realistic yet is more complex from the algorithmic point of view; in some settings optimizing such unsplittable traffic flow is computationally intractable.In this paper, we assume this more realistic unsplittable model, and investigate the "price of anarchy", or deterioration of network performance measured in total traffic latency under the selfish user behavior. We show that for linear edge latency functions the price of anarchy is exactly $2.618 for weighted demand and exactly $2.5 for unweighted demand. These results are easily extended to (weighted or unweighted) atomic "congestion games", where paths are replaced by general subsets. We also show that for polynomials of degree d edge latency functions the price of anarchy is dδ(d). Our results hold also for mixed strategies.Previous results of Roughgarden and Tardos showed that for linear edge latency functions the price of anarchy is exactly 4/3 under the assumption that each user controls only a negligible fraction of the overall traffic (this result also holds for the splittable case). Note that under the assumption of negligible traffic pure and mixed strategies are equivalent and also splittable and unsplittable models are equivalent.

Abstract We consider the classical problem of scheduling parallel unrelated machines. Each job is tobe processed by exactly one machine. Processing job j on machine i requires time pij. The goalis to find a schedule that minimizes the `p norm. Previous work showed a 2-approximation algo-rithm for the problem with respect to the `1 norm. For any fixed `p norm the previously knownapproximation algorithm has a performance of `(p). We provide a 2-approximation algorithmfor any fixed `p norm (p> 1). This algorithm uses convex programming relaxation. We alsogive a p 2-approximation algorithm for the `2 norm. This algorithm relies on convex quadraticprogramming relaxation. To the best of our knowledge, this is the first time that general convex programming techniques (apart from SDPs and CQPs) are used in the area of scheduling. Weshow for any given `p norm a PTAS for any fixed number of machines. We also consider themultidimensional generalization of the problem in which the jobs are d-dimensional. Here thegoal is to minimize the `p norm of the generalized load vector, which is a matrix where the rowsrepresent the machines and the columns represent the jobs dimension. For this problem we give a (d + 1)-approximation algorithm for any fixed `p norm (p> 1). 1 Introduction We consider the classical problem of scheduling jobs on parallel unrelated machines. Lenstra et. al[14] and Shmoys and Tardos [16] provided a 2-approximation algorithm for minimizing the makespan (`1 norm). However, for the `p norm only `(p)-approximation algorithm was known (see [2]). Weprovide a 2-approximation algorithm for any `p norm. In addition we show a p2-approximationalgorithm for the