Beyond an emerging popular web applications runtime supported in almost all commodity browsers, WebAssembly (WASM) is further regarded to be the next-generation execution environment for blockchain-based applications. Indeed, many popular blockchain platforms such as EOSIO and NEAR have adopted WASM-based execution engines. Most recently, WASM has been favored by Ethereum, the largest smart contract platform, to replace the state-of-the-art EVM. However, whether and how well current WASM outperforms EVM on blockchain clients is still unknown. This article conducts the first measurement study to understand the performance on WASM VMs and EVM for executing smart contracts for blockchain-based applications. To our surprise, the current WASM VM does not provide expected satisfactory performance. The overhead introduced by WASM is really non-trivial. Our results shed the light on challenges when deploying WASM in practice, and provide insightful implications for improvement space.

Many cloud service providers (CSPs) offer an on-demand service with a small delay. Motivated by the reality of cloud ecosystems, we study non-interruptible services and consider a differentiated service model to complement the existing market by offering multiple service level agreements (SLAs) to satisfy users with different delay tolerance. The model itself is incentive compatible by construction. Two typical architectures are considered to fulfill SLAs: (i) non-preemptive priority queues and (ii) multiple independent groups of servers. We leverage queueing theory to establish guidelines for the resultant market: (a) Under the first architecture, the service model can only improve the revenue marginally over the pure on-demand service model and (b) under the second architecture, we give a closed-form expression of the revenue improvement when a CSP offers two SLAs and derive a condition under which the market is viable. Additionally, under the second architecture, we give an exhaustive search procedure to find the optimal SLA delays and prices when a CSP generally offers multiple SLAs. Numerical results show that the achieved revenue improvement can be significant even if two SLAs are offered. Our results can help CSPs design optimal delay-differentiated services and choose appropriate serving architectures.

Many mission- and time-critical cyber-physical systems deploy an isolated power system for their power supply. Under extreme conditions, the power system must process critical missions by maximizing the Pulsed Power Load (PPL) utility while maintaining the normal loads in the cyber-physical system. Optimal operation requires careful coordination of PPL deployment and power supply processes. In this work, we formulate the coordination problem for maximizing PPL utility under available resources, capacity, and demand constraints. The coordination problem has two scenarios for different use cases, fixed and general normal loads. We develop an exact pseudo-polynomial time dynamic programming algorithm for each scenario with a proven guarantee to produce an optimal coordination schedule. The performance of the algorithms is also experimentally evaluated, and the results agree with our theoretical analysis, showing the practicality of the solutions.

Online algorithms are an important branch in algorithm design. Designing online algorithms with a bounded competitive ratio (in terms of worst-case performance) can be hard and usually relies on problem-specific assumptions. Inspired by adversarial training from Generative Adversarial Net and the fact that the competitive ratio of an online algorithm is based on worst-case input, we adopt deep neural networks (NNs) to learn an online algorithm for a resource allocation and pricing problem from scratch, with the goal that the performance gap between offline optimum and the learned online algorithm can be minimized for worst-case input. Specifically, we leverage two NNs as the algorithm and the adversary, respectively, and let them play a zero sum game, with the adversary being responsible for generating worst-case input while the algorithm learns the best strategy based on the input provided by the adversary. To ensure better convergence of the algorithm network (to the desired online algorithm), we propose a novel per-round update method to handle sequential decision making to break complex dependency among different rounds so that update can be done for every possible action instead of only sampled actions. To the best of our knowledge, our work is the first using deep NNs to design an online algorithm from the perspective of worst-case performance guarantee. Empirical studies show that our updating methods ensure convergence to Nash equilibrium and the learned algorithm outperforms state-of-the-art online algorithms under various settings.

Consider a setting where Willie generates a Poisson stream of jobs and routes them to a single server that follows the first-in first-out discipline. Suppose there is an adversary Alice, who desires to receive service without being detected. We ask the question: What is the number of jobs that she can receive covertly, i.e., without being detected by Willie? In the case where both Willie and Alice jobs have exponential service times with respective rates μ 1 and μ 2 , we demonstrate a phase-transition when Alice adopts the strategy of inserting a single job probabilistically when the server idles: over n busy periods, she can achieve a covert throughput, measured by the expected number of jobs covertly inserted, of O (√ n ) when μ 1 < 2 μ 2 , O (√ n log n ) when μ 1 = 2μ 2 , and O ( n μ 2 /μ 1 ) when μ 1 > 2μ 2 . When both Willie and Alice jobs have general service times, we establish an upper bound for the number of jobs Alice can execute covertly. This bound is related to the Fisher information. More general insertion policies are also discussed.

Distributed/parallel file systems commonly suffer from load imbalance and resource contention due to the bursty characteristic exhibited in scientific applications. This article presents an adaptive scheme supporting dynamic block data replication and an efficient replica placement policy to improve the I/O performance of a distributed file system. Our goal is not only to yield a balanced data replication among storage servers but also a high degree of data access parallelism for the applications. We first present mathematical cost models to formulate the cost of data block replication by considering both the overhead and reduced data access time to the replicated data. To verify the validity and feasibility of the proposed cost model, we implement our proposal in a prototype distributed file system and evaluate it using a set of representative database-relevant application benchmarks. Our results demonstrate that the proposed approach can boost the usage efficiency of the data replicas with acceptable overhead of data replication management. Consequently, the overall data throughput of storage system can be noticeably improved. In summary, the proposed replication management scheme works well, especially for the database-relevant applications that exhibit an uneven access frequency and pattern to different parts of files.

Cloud computing delivers value to users by facilitating their access to servers at any time period needed. An approach is to provide both on-demand and spot services on shared servers. The former allows users to access servers on demand at a fixed price and users occupy different time periods on servers. The latter allows users to bid for the remaining unoccupied time periods via dynamic pricing; however, without appropriate design, such time periods may be arbitrarily short since on-demand users arrive randomly. This is also the current service model adopted by Amazon Elastic Cloud Compute. In this article, we provide the first integral framework for sharing time on servers between on-demand and spot services while optimally pricing spot service. It guarantees that on-demand users can get served quickly while spot users can stably use servers for a properly long period once accepted, which is a key feature in making both on-demand and spot services accessible. Simulation results show that, by complementing the on-demand market with a spot market, a cloud provider can improve revenue by up to 461.5%. The framework is designed under assumptions that are met in real environments. It is a new tool that other cloud operators can use to quantify the advantage of a hybrid spot and on-demand service, making the case for eventually integrating this service model into their own infrastructures.

Cloud storage services such as Dropbox and OneDrive provide users with a convenient and reliable way to store and share data from anywhere, on any device, and at any time. Their cornerstone is the data synchronization (sync) operation, which automatically maps the changes in users’ local file systems to the cloud via a series of network communications in a timely manner. Without careful design and implementation, however, the data sync mechanisms could generate overwhelming traffic, causing tremendous financial overhead and performance penalties to both service providers and end users. This article addresses a simple yet critical question: Is the current data sync traffic of cloud storage services efficiently used? We first define a novel metric TUE to quantify the T raffic U sage E fficiency of data synchronization. Then, by conducting comprehensive benchmark experiments and reverse engineering the data sync processes of eight widely used cloud storage services, we uncover their manifold practical endeavors for optimizing the TUE, including three intra-file approaches (compression, incremental sync, and interrupted transfer resumption), two cross-file/-user approaches ( i.e., deduplication and peer-assisted offloading), two batching approaches (file bundling and sync deferment), and two web-specific approaches (thumbnail views and dynamic content loading). Our measurement results reveal that a considerable portion of the data sync traffic is, in a sense, wasteful and can be effectively avoided or significantly reduced via carefully designed data sync mechanisms. Most importantly, our study not only offers practical, actionable guidance for providers to build more efficient, traffic-economic services, but also helps end users pick appropriate services that best fit their use cases and budgets.

Datacenters are major energy consumers and dissipate an enormous amount of waste heat. Simple outdoor discharging of datacenter heat is energy-consuming and environmentally unfriendly. By harvesting datacenter waste heat and selling to the district heating system (DHS), both energy cost compensation and environment protection can be achieved. To realize such benefits in practice, an efficient market mechanism is required to incentivize the participation of datacenters. This work proposes CloudHeat, an online reverse auction mechanism for the DHS to solicit heat bids from datacenters. To minimize long-term social operational cost of the DHS and the datacenters, we apply a RFHC approach for decomposing the long-term problem into a series of one-round auctions, guaranteeing a small loss in competitive ratio. The one-round optimization is still NP-hard, and we employ a randomized auction framework to simultaneously guarantee truthfulness, polynomial running time, and an approximation ratio of 2. The performance of CloudHeat is validated through theoretical analysis and trace-driven simulation studies.

To improve energy efficiency and comply with the power budgets, it is important to be able to measure the power consumption of cloud computing servers. Intel’s Running Average Power Limit (RAPL) interface is a powerful tool for this purpose. RAPL provides power limiting features and accurate energy readings for CPUs and DRAM, which are easily accessible through different interfaces on large distributed computing systems. Since its introduction, RAPL has been used extensively in power measurement and modeling. However, the advantages and disadvantages of RAPL have not been well investigated yet. To fill this gap, we conduct a series of experiments to disclose the underlying strengths and weaknesses of the RAPL interface by using both customized microbenchmarks and three well-known application level benchmarks: Stream , Stress-ng , and ParFullCMS . Moreover, to make the analysis as realistic as possible, we leverage two production-level power measurement datasets from the Taito , a supercomputing cluster of the Finnish Center of Scientific Computing and also replicate our experiments on Amazon EC2. Our results illustrate different aspects of RAPL and document the findings through comprehensive analysis. Our observations reveal that RAPL readings are highly correlated with plug power, promisingly accurate enough, and have negligible performance overhead. Experimental results suggest RAPL can be a very useful tool to measure and monitor the energy consumption of servers without deploying any complex power meters. We also show that there are still some open issues, such as driver support, non-atomicity of register updates, and unpredictable timings that might weaken the usability of RAPL in certain scenarios. For such scenarios, we pinpoint solutions and workarounds.

This article studies emergency demand response (EDR) mechanisms from a data center perspective, where a cloud participates in a mandatory EDR program while receiving computing job bids from cloud users in an online fashion. We target a realistic EDR mechanism where (i) the cloud provider dynamically packs different types of resources on servers into requested VMs and computes job schedules to meet users’ requirements, (ii) the power consumption of servers in the cloud is limited by the grid through the EDR program, and (iii) the operation cost of the cloud is considered in the calculation of social welfare, measured by an electricity cost that consists of both volume charge and peak charge. We propose an online auction for dynamic cloud resource provisioning that is under the control of the EDR program, runs in polynomial time, achieves truthfulness, and close-to-optimal social welfare for the cloud ecosystem. In the design of the online auction, we first propose a new framework, compact exponential LPs, to handle job scheduling constraints in the time domain. We then develop a posted pricing auction framework toward the truthful online auction design, which leverages the classic primal-dual technique for approximation algorithm design. We evaluate our online auctions through both theoretical analysis and empirical studies driven by real-world traces.

In this article, we focus on request scheduling with performance guarantees of all users in cloud computing. Each cloud user submits requests with average response time requirement, and the cloud provider tries to find a scheduling scheme, i.e., allocating user requests to limited servers, such that the average response times of all cloud users can be guaranteed. We formulate the considered scenario into a cooperative game among multiple users and try to find a Nash bargaining solution (NBS), which can simultaneously satisfy all users’ performance demands. We first prove the existence of NBS and then analyze its computation. Specifically, for the situation when all allocating substreams are strictly positive, we propose a computational algorithm ( CA ), which can find the NBS very efficiently. For the more general case, we propose an iterative algorithm ( IA ), which is based on duality theory. The convergence of our proposed IA algorithm is also analyzed. Finally, we conduct some numerical calculations. The experimental results show that our IA algorithm can find an appropriate scheduling strategy and converges to a stable state very quickly.

The rising popularity of data calls and the slowed global economy have posed a challenge to voice data networking—how to satisfy the growing user demand for VoIP calls under limited network resources. In a bandwidth-constrained network in particular, raising the bitrate for one call implies a lowered bitrate for another. Therefore, knowing whether it is worthwhile to raise one call's bitrate while other users might complain is crucial to the design of a user-centric rate control mechanism. To this end, previous work (Chen et al. 2012) has reported a log-like relationship between bitrate and user experience (i.e., QoE) in Skype calls. To show that the relationship extends to more general VoIP calls, we conduct a 60-participant user study via the Amazon Mechanical Turk crowdsourcing platform and reaffirm the log-like relationship between the call bitrate and user experience in widely used AMR-WB. The relationship gives rise to a simple and practical rate control scheme that exponentially quantizes the steps of rate change, therefore the name—exponential quantization (EQ). To support that EQ is effective in addressing the challenge, we show through a formal analysis that the resulting bandwidth allocation is optimal in both the overall QoE and the number of calls served. To relate EQ to existing rate control mechanisms, we show in a simulation study that the bitrates of calls administered by EQ converge over time and outperform those controlled by a (naïve) greedy mechanism and the mechanism implemented in Skype.

Many video-on-demand (VoD) providers are relying on public cloud providers for video storage, access, and streaming services. In this article, we investigate how a VoD provider may make optimal bandwidth reservations from a cloud service provider to guarantee the streaming performance while paying for the bandwidth, storage, and transfer costs. We propose a predictive resource auto-scaling system that dynamically books the minimum amount of bandwidth resources from multiple servers in a cloud storage system to allow the VoD provider to match its short-term demand projections. We exploit the anti-correlation between the demands of different videos for statistical multiplexing to hedge the risk of under-provisioning. The optimal load direction from video channels to cloud servers without replication constraints is derived with provable performance. We further study the joint load direction and sparse content placement problem that aims to reduce bandwidth reservation cost under sparse content replication requirements. We propose several algorithms, and especially an iterative L 1 -norm penalized optimization procedure, to efficiently solve the problem while effectively limiting the video migration overhead. The proposed system is backed up by a demand predictor that forecasts the expectation, volatility, and correlation of the streaming traffic associated with different videos based on statistical learning. Extensive simulations are conducted to evaluate our proposed algorithms, driven by the real-world workload traces collected from a commercial VoD system.

This article proposes a model to study the interaction of price competition and congestion in the cloud computing marketplace. Specifically, we propose a three-tier market model that captures a marketplace with users purchasing services from Software-as-a-Service (SaaS) providers, which in turn purchase computing resources from either Provider-as-a-Service (PaaS) or Infrastructure-as-a-Service (IaaS) providers. Within each level, we define and characterize market equilibria. Further, we use these characterizations to understand the relative profitability of SaaSs and PaaSs/IaaSs and to understand the impact of price competition on the user experienced performance, that is, the “price of anarchy” of the cloud marketplace. Our results highlight that both of these depend fundamentally on the degree to which congestion results from shared or dedicated resources in the cloud.

OpenFOAM is a widely used open source framework for simulation in several areas of computational fluid dynamics and engineering. As a partial differential equation (PDE)-based framework, OpenFOAM suffers from a performance bottleneck in solving large-scale sparse linear systems of equations. To address the problem, this article proposes a novel OpenFOAM-PETSc framework by inserting PETSc, a dedicated numerical solving package, into the OpenFOAM to speed up the process of solving linear equation systems. The design of the OpenFOAM-PETSc framework is described, and the implementation of an efficient matrix conversion algorithm is given as a case study. Validation tests on a high-performance computing cluster show that OpenFOAM-PETSc reduces the time of solving PDEs by about 27% in the lid-driven cavity flow case and by more than 50% in flow around the cylinder case in comparison with OpenFOAM, without compromising the scalability. In addition, this article also gives a preliminary performance analysis of different numerical solution methods, which may provide guidelines for further optimizations.

Modern memory systems are structured under hierarchy and concurrency. The combined impact of hierarchy and concurrency, however, is application dependent and difficult to describe. In this article, we introduce C 2 -Bound, a data-driven analytical model that serves the purpose of optimizing many-core design. C 2 -Bound considers both memory capacity and data access concurrency. It utilizes the combined power of the newly proposed latency model, concurrent average memory access time, and the well-known memory-bounded speedup model (Sun-Ni’s law) to facilitate computing tasks. Compared to traditional chip designs that lack the notion of memory capacity and concurrency, the C 2 -Bound model finds that memory bound factors significantly impact the optimal number of cores as well as their optimal silicon area allocations, especially for data-intensive applications with a non-parallelizable sequential portion. Therefore, our model is valuable to the design of next-generation many-core architectures that target big data processing, where working sets are usually larger than the conventional scientific computing. These findings are evidenced by our detailed simulations, which show, with C 2 -Bound, the design space of chip design can be narrowed down significantly up to four orders of magnitude. C 2 -Bound analytic results can be either used in reconfigurable hardware environments or, by software designers, applied to scheduling, partitioning, and allocating resources among diverse applications.

Although the Infrastructure-as-a-Service (IaaS) cloud offers diverse instance types to users, a significant portion of cloud users, especially those with small and short demands, cannot find an instance type that exactly fits their needs or fully utilize purchased instance-hours. In the meantime, cloud service providers are also faced with the challenge to consolidate small, short jobs, which exhibit strong dynamics, to effectively improve resource utilization. To handle such inefficiencies and improve cloud resource utilization, we propose Cocoa (COmputing in COntAiners) , a novel group buying mechanism that organizes jobs with complementary resource demands into groups and allocates them to group buying deals predefined by cloud providers. Each group buying deal offers a resource pool for all the jobs in the deal, which can be implemented as either a virtual machine or a physical server. By running each user job on a virtualized container, our mechanism allows flexible resource sharing among different users in the same group buying deal, while improving resource utilization for cloud providers. To organize jobs with varied resource demands and durations into groups, we model the initial static group organization as a variable-sized vector bin packing problem, and the subsequent dynamic group organization problem as an online multidimensional knapsack problem. Through extensive simulations driven by a large amount of real usage traces from a Google cluster, we evaluate the potential cost reduction achieved by Cocoa . We show that through the effective combination and interaction of the proposed static and dynamic group organization strategies, Cocoa greatly outperforms the existing cloud workload consolidation mechanism, substantiating the feasibility of group buying in cloud computing.

Analyzing and modeling social network dynamics are key to accurately predicting resource needs and system behavior in online social networks. The presence of statistical scaling properties, that is, self-similarity, is critical for determining how to model network dynamics. In this work, we study the role that self-similarity scaling plays in a social network edge creation (that is, links created between users) process, through analysis of two detailed, time-stamped traces, a 199 million edge trace over 2 years in the Renren social network, and 876K interactions in a 4-year trace of Facebook. Using wavelet-based analysis, we find that the edge creation process in both networks is consistent with self-similarity scaling, once we account for periodic user activity that makes edge creation process non-stationary. Using these findings, we build a complete model of social network dynamics that combines temporal and spatial components. Specifically, the temporal behavior of our model reflects self-similar scaling properties, and accounts for certain deterministic non-stationary features. The spatial side accounts for observed long-term graph properties, such as graph distance shrinkage and local declustering. We validate our model against network dynamics in Renren and Facebook datasets, and show that it succeeds in producing desired properties in both temporal patterns and graph structural features.

Data centers are key participants in demand response programs, including emergency demand response (EDR), in which the grid coordinates consumers of large amounts of electricity for demand reduction in emergency situations to prevent major economic losses. While existing literature concentrates on owner-operated data centers, this work studies EDR in geo-distributed multitenant colocation data centers in which servers are owned and managed by individual tenants. EDR in colocation data centers is significantly more challenging due to lack of incentives to reduce energy consumption by tenants who control their servers and are typically on fixed power contracts with the colocation operator. Consequently, to achieve demand reduction goals set by the EDR program, the operator has to rely on the highly expensive and/or environmentally unfriendly on-site energy backup/generation. To reduce cost and environmental impact, an efficient incentive mechanism is therefore needed, motivating tenants’ voluntary energy reduction in the case of EDR. This work proposes a novel incentive mechanism, Truth-DR, which leverages a reverse auction to provide monetary remuneration to tenants according to their agreed energy reduction. Truth-DR is computationally efficient, truthful, and achieves 2-approximation in colocation-wide social cost. Trace-driven simulations verify the efficacy of the proposed auction mechanism.

Bloom filters are frequently used to to check the membership of an item in a set. However, Bloom filters face a dilemma: the transmission bandwidth and the accuracy cannot be optimized simultaneously. This dilemma is particularly severe for transmitting Bloom filters to remote nodes when the network bandwidth is limited. We propose a novel Bloom filter called BloomTree that consists of a tree-structured organization of smaller Bloom filters, each using a set of independent hash functions. BloomTree spreads items across levels that are compressed to reduce the transmission bandwidth need. We show how to find optimal configurations for BloomTree and investigate in detail by how much BloomTree outperforms the standard Bloom filter or the compressed Bloom filter. Finally, we use the intersection of BloomTrees to predict the set intersection, decreasing the false-positive probabilities by several orders of magnitude compared to both the compressed Bloom filter and the standard Bloom filter.

One of the main problems in deep submicron designs of high-speed buses is propagation delay due to the crosstalk effect. To alleviate the crosstalk effect, there are several types of crosstalk avoidance codes proposed in the literature. In this article, we analyze the coding rates of forbidden overlap codes (FOCs) that avoid “010 → 101” transition and “101 → 010” transition on any three adjacent wires in a bus. We first compute the maximum achievable coding rate of FOCs and the maximum coding rate of memoryless FOCs. Our numerical results show that there is a significant gap between the maximum coding rate of memoryless FOCs and the maximum achievable rate. We then analyze the coding rates of FOCs generated from the bit-stuffing algorithm. Our worst-case analysis yields a tight lower bound of the coding rate of the bit-stuffing algorithm. Under the assumption of Bernoulli inputs, we use a Markov chain model to compute the coding rate of a bus with n wires under the bit-stuffing algorithm. The main difficulty of solving such a Markov chain model is that the number of states grows exponentially with respect to the number of wires n . To tackle the problem of the curse of dimensionality, we derive an approximate analysis that leads to a recursive closed-form formula for the coding rate over the n th wire. Our approximations match extremely well with the numerical results from solving the original Markov chain for n ⩽ 10 and the simulation results for n ⩽ 3000. Our analysis of coding rates of FOCs could be helpful in understanding the trade-off between propagation delay and coding rate among various crosstalk avoidance codes in the literature. In comparison with the forbidden transition codes (FTCs) that have shorter propagation delay than that of FOCs, our numerical results show that the coding rates of FOCs are much higher than those of FTCs.