The substantial memory demands of model weights and key-value (KV) caches often lead to severe memory bottlenecks in LLM serving. Existing systems address this by offloading KV caches to host memory and rapidly restoring them on demand before decoding. However, these approaches are too coarse-grained and fail to fully exploit the combined computational and storage capabilities of GPUs.

While spot instances offer a cost-effective alternative to on-demand cloud resources, they introduce reliability challenges for latency-sensitive microservices due to preemption risks and unpredictable provisioning delays. Conventional resource management systems, which often rely on assumptions of immediate instance availability, fail to account for these operational realities—resulting in increased risk of SLO violations when deployed in spot-based environments.

The recent surge in popularity of cloud-native applications using microservice architectures has led to a focus on accurate end-to-end latency prediction for proactive resource allocation. Existing models leverage Graph Transformers to Microservice Call Graphs or the Program Evaluation and Review Technique (PERT) graphs to capture complex temporal dependencies between microservices. However, these models incur a high computational cost during both training and inference phases. This paper introduces FastPERT, an efficient model for predicting end-to-end latency in microservice applications. FastPERT dissects an execution trace into several microservices tasks, using observations from prior execution traces of the application, akin to the PERT approach. Subsequently, a prediction model is constructed to estimate the completion time for each individual task. This information, coupled with the computational and structural inductive bias of the PERT graph, facilitates the efficient computation of the end-to-end latency of an execution trace. As a result, FastPERT can efficiently capture the complex temporal causality of different microservice tasks without relying on Graph Neural Networks, leading to more accurate and robust latency predictions across a variety of applications. An evaluation based on datasets generated from large-scale Alibaba microservice traces reveals that FastPERT significantly improves training and inference efficiency without compromising performance, demonstrating its potential as a superior solution for real-time end-to-end latency prediction in cloud-native microservice applications.

In a unified resource scheduling architecture, containers within the same microservice often encounter temporal and spatial performance imbalance when deployed in large-scale shared clusters. As a result, the commonly employed load-balancing approach often leads to substantial resource wastage as applications are frequently over-provisioned to meet service level agreements (SLAs).

Federated Learning (FL) is a rising distributed learning paradigm that facilitates multiple devices to jointly train a shared model. Given the presence of heterogeneous devices with distinct data distributions, it is critical to select an optimal subset of devices for engagement in the collaborative training process. However, the dynamic nature of FL, encompassing aspects like dynamic device availability and inherent training dynamics, significantly complicates participant selection, and current systems routinely fall short in adapting effectively to such dynamic environments.

Deep learning (DL) inference services are widely recognized as crucial workloads in large-scale cloud clusters. However, due to the stringent latency requirements, cloud providers often over-provision GPU resources, resulting in underutilization of the available GPU potential. Although co-locating tasks on the same device can enhance utilization, ensuring Service Level Objectives (SLOs) guarantees for multiplexing highly dynamic inference services becomes extremely challenging due to significant resource interference.

Microservice applications are commonly deployed alongside other services to enhance resource utilization. However, this practice also leads to notable resource contention. While existing studies primarily focus on scaling critical microservices responsible for performance degradation to mitigate violations of SLAs regarding end-to-end latency in highly interfered environments, they often overlook the potential advantages of scaling non-critical microservices for optimized resource efficiency. In this paper, we introduce Grad, an intelligent microservice scaling framework by harnessing resource fungibility between critical and non-critical microservices. Addressing the challenges posed by the dynamic nature of resource fungibility during scaling, Grad incorporates three key components. First, Grad employs a modular learning approach to profile individual microservice latency in relation to environmental conditions. Utilizing gradient extracts from this profile, Grad designs a scalable optimization module to dynamically select the optimal set of microservices for scaling. To rapidly mitigate SLA violations, Grad also deploys an accurate end-to-end latency predictor, serving as an simulator to obtain real-time feedback. We evaluate Grad in our cluster using real microservice benchmarks and production traces, demonstrating its ability to reduce resource usage by $\mathbf{4 9. 1 \%}$ and lower the probability of SLA violations by $3.7 \times$ when compared to state-of-the-art solutions.

The GPU device heterogeneity in accelerating deep learning training workloads poses significant challenges for job scheduling in datacenters.Existing heterogeneity-aware job schedulers, however, cannot effectively reduce the overall job completion time (JCT) or provide fairness guarantees due to their coarse-grained resource allocation and poor integration of conflicting objectives.This paper presents FFT, a novel scheduling system designed for Fast and Fair deep learning Training in heterogeneous GPU clusters.FFT incorporates two key designs.First, it incorporates a resource allocation scheme in each round to enable fine-grained control over resource utilization.Second, it seamlessly integrates a fairness compensation mechanism that dynamically evaluates fairness in real-time.Building upon these designs, FFT formulates a cost minimization problem to determine the optimal schedule, striking a delicate balance between efficiency and fairness.Extensive experiments conducted in physical clusters as well as large-scale testbed demonstrate that FFT can significantly accelerate the overall JCT by up to 5.2× while improving job finishtime-fairness by more than 2.2× compared to state-of-the-art heterogeneity-aware solutions.

The significant resource demands in LLM serving prompts production clusters to fully utilize heterogeneous hardware by partitioning LLM models across a mix of high-end and low-end GPUs. However, existing parallelization approaches often struggle to scale efficiently in heterogeneous environments due to their coarse-grained and static parallelization strategies.

The problem of multi-armed bandit (MAB) with fairness constraints has emerged as an important research topic recently. For such problems, one common objective is to maximize the total rewards within a fixed number of pull rounds, while satisfying the fairness requirement of a minimum selection fraction for each individual arm in the long run. Previous works have made substantial advancements in designing various online selection solutions for MAB, however, when incorporating such fairness constraints, they fail to achieve a sublinear regret bound. In this paper, we study a combinatorial MAB problem with concave objective and fairness constraints. In particular, we design a new selection algorithm that solves MAB problems from an online convex optimization perspective. Our algorithm is computationally efficient, and more importantly, manages to achieve a sublinear regret bound of O( √ T ln T) with high probability guarantees in T selection rounds. We also extend our framework to include more general knapsack constraints. Finally, we assess the performance of our algorithm through extensive simulations and real dataset applications, demonstrating its significant advantages over baseline schemes.

Modern GPU clusters inherently exhibit heterogeneity, encompassing various aspects such as computation and communication. This heterogeneity poses a significant challenge for the elastic scheduling of deep learning workloads. Unfortunately, existing elastic schedulers often overlook the impact of heterogeneity on scaling efficiency, resulting in considerably prolonged job completion times.

Ensuring efficient resource allocation while providing service level agreement (SLA) guarantees for end-to-end (E2E) latency is crucial for microservice applications. Although existing studies have made significant contributions towards achieving this objective, they primarily concentrate on static graphs. However, microservice graphs are inherently dynamic during runtime in production environments, necessitating more effective and scalable resource management solutions.In this paper, we present Derm, a new resource management system designed for microservice applications with highly dynamic graphs. Our principal finding is that prioritizing different microservice graphs can lead to a substantial reduction in resource allocation. To take advantage of this opportunity, we develop three main components. The first is a performance model that describes uncertainties of microservice latency through a conditional exponential distribution. The second is a probabilistic quantification of the dynamics of microservice graphs. The third is an optimization method for adjusting the resource allocation of microservices to minimize resource usage. We evaluate Derm in our cluster using real microservice benchmarks and production traces. The results highlight that Derm reduces the resource usage by $68.4 \%$ and lowers SLA violation probability by $6.7 \times$, compared to existing approaches.

Ensuring the highest training throughput to maximize resource efficiency, while maintaining fairness among users, is critical for deep learning (DL) training in heterogeneous GPU clusters. However, current DL schedulers provide only limited fairness properties and suboptimal training throughput, impeding tenants from effectively leveraging heterogeneous resources. The underlying design challenge stems from inherent conflicts between efficiency and fairness properties.

The deployment of ML serving applications, featuring multiple inference functions on serverless platforms, has gained substantial popularity, leading to numerous developments of new systems. However, these systems often focus on optimizing resource provisioning and cold start management separately, ultimately resulting in higher monetary costs. This paper introduces SMIless, a highly efficient serverless system tailored for serving DAG-based ML inference in heterogeneous environments. SMIless effectively co-optimizes resource configuration and cold-start management in the context of dynamic invocations. This is achieved by seamlessly integrating adaptive pre-warming windows, striking an effective balance between performance and cost. We have implemented SMIless on top of OpenFaaS and conducted extensive evaluations using real-world ML serving applications. The experimental results demonstrate that SMIless can achieve up to a $5.73 \times$ reduction in the overall costs while meeting the SLA requirements for all user requests, surpassing the performance of state-of-the-art solutions.

A significant proportion of energy consumed in modern data centers and clouds is dedicated to provisioning idle servers for maintaining Quality of Service guarantees. Various studies have been conducted exploring dynamic provisioning in data centers with the objective of reducing overall energy consumption. However, many of these studies assume a fixed energy cost per operating server where each server can only handle one job within a given time slot. In this paper, we address a new and practical problem that involves speed scaling of multiple servers within a data center. Specifically, we consider a scenario where each server can handle multiple jobs simultaneously, and the energy consumed is a piece-wise convex function that depends on processing speed. In addition, turning on a server incurs a substantial energy cost.

Today, pharmaceutical industry faces great pressure to employ more efficient and systematic ways in drug discovery and development process. However, conventional formulation studies still strongly rely on personal experiences by trial-and-error experiments, resulting in a labor-consuming, tedious and costly pipeline. Thus, it is highly required to develop intelligent and efficient methods for formulation development to keep pace with the progress of the pharmaceutical industry. Here, we developed a comprehensive web-based platform (FormulationAI) for in silico formulation design. First, the most comprehensive datasets of six widely used drug formulation systems in the pharmaceutical industry were collected over 10 years, including cyclodextrin formulation, solid dispersion, phospholipid complex, nanocrystals, self-emulsifying and liposome systems. Then, intelligent prediction and evaluation of 16 important properties from the six systems were investigated and implemented by systematic study and comparison of different AI algorithms and molecular representations. Finally, an efficient prediction platform was established and validated, which enables the formulation design just by inputting basic information of drugs and excipients. FormulationAI is the first freely available comprehensive web-based platform, which provides a powerful solution to assist the formulation design in pharmaceutical industry. It is available at https://formulationai.computpharm.org/.

A common approach to improving resource utilization in data centers is to adaptively provision resources based on the actual workload. One fundamental challenge of doing this in microservice management frameworks, however, is that different components of a service can exhibit significant differences in their impact on end-to-end performance. To make resource management more challenging, a single microservice can be shared by multiple online services that have diverse workload patterns and SLA requirements. We present an efficient resource management system, namely Erms, for guaranteeing SLAs with high probability in shared microservice environments. Erms profiles microservice latency as a piece-wise linear function of the workload, resource usage, and interference. Based on this profiling, Erms builds resource scaling models to optimally determine latency targets for microservices with complex dependencies. Erms also designs new scheduling policies at shared microservices to further enhance resource efficiency. Experiments across microservice benchmarks as well as trace-driven simulations demonstrate that Erms can reduce SLA violation probability by 5× and more importantly, lead to a reduction in resource usage by 1.6×, compared to state-of-the-art approaches.

A common approach to improving resource utilization in data centers is to adaptively provision resources based on the actual workload. One fundamental challenge of doing this in microservice management frameworks, however, is that different components of a service can exhibit significant differences in their impact on end-to-end performance. To make resource management more challenging, a single microservice can be shared by multiple online services that have diverse workload patterns and SLA requirements.

To fully utilize computing resources, cloud providers such as Google and Alibaba choose to co-locate online services with batch processing applications in their data centers. By implementing unified resource management policies, different types of complex computing jobs request resources in a consistent way, which can help data centers achieve global optimal scheduling and provide computing power with higher quality. To understand this new scheduling paradigm, in this paper, we first present an in-depth study of Alibaba's unified scheduling workloads. Our study focuses on the characterization of resource utilization, the application running performance, and scheduling scalability. We observe that although computing resources are significantly over-committed under unified scheduling, the resource utilization in Alibaba data centers is still low. In addition, existing resource usage predictors tend to make severe overestimations. At the same time, tasks within the same application behave fairly consistently, and the running performance of tasks can be well-profiled with respect to resource contention on the corresponding physical host.

Cloud-native applications using microservice architectures are rapidly replacing traditional monolithic applications. To meet end-to-end QoS guarantees and enhance user experience, each component microservice must be provisioned with sufficient resources to handle incoming API calls. Accurately predicting the latency of microservices-based applications is critical for optimizing resource allocation, which turns out to be extremely challenging due to the complex dependencies between microservices and the inherent stochasticity. To tackle this problem, various predictors have been designed based on the Microservice Call Graph. However, Microservice Call Graphs do not take into account the API-specific information, cannot capture important temporal dependencies, and cannot scale to large-scale applications.

A common strategy for improving efficiency in training deep learning entails multiplexing tasks on a single GPU. To mitigate the interference caused by multiplexing, existing approaches primarily employ kernel-level solutions to regulate GPU kernel execution, or harness hardware-level techniques to explicitly restrict GPU streaming multiprocessors and memory. Nevertheless, none of them perform satisfactorily in optimizing the completion time of tasks.

Recognizing the diversity of Big Data analytic jobs, cloud providers offer a wide range of VM instance types or even clusters to cater for different use cases. The choice of cloud configurations can have a significant impact on the response time and running cost of batch-processing applications, which may need to be re-run regularly with cloud-scale resources. However, identifying the best cloud configuration with a low search cost is quite challenging due to i) the large and high-dimensional configuration space, ii) the time-varying cloud service cost (e.g., AWS Spot instances), and iii) job response time variation even given the same configuration. To tackle these challenges, we design and implementAccordia, a system that enables Adaptive Cloud Configuration Optimization for Recurring Data-Intensive Applications. By leveraging recent algorithmic advances in Gaussian Process UCB techniques,Accordiacan unearth the cost-optimal configuration with a deadline constraint (i.e., maximum tolerated running time) under the time-varying cloud service cost. More importantly,Accordiamanages to achieve a theoretical performance guarantee,sub-linearly increasing dynamic regretof the job completion cost. Using extensive trace-driven simulations and empirical measurements of our Kubernetes-based implementation, we demonstrate thatAccordiacan identify a near-cost-optimal configuration (i.e., within 10% of the optimum) after fewer than 20 runs from over 7000 candidate choices, which translates to a 2X-speedup and up to 17.9% cost-savings, when comparing to the state-of-the-art approach,CherryPick.

When deploying microservices in production clusters, it is critical to automatically scale containers to improve cluster utilization and ensure service level agreements (SLA). Although reactive scaling approaches work well for monolithic architectures, they are not necessarily suitable for microservice frameworks due to the long delay caused by complex microservice call chains. In contrast, existing proactive approaches leverage end-to-end performance prediction for scaling, but cannot effectively handle microservice multiplexing and dynamic microservice dependencies.

Recognizing the explosion of large-scale real-time analytics needs, a plethora of stream processing systems, such as Apache Storm and Flink, have been developed to support such applications. Under these systems, a stream processing application is realized as a directed acyclic graph (DAG) of operators, where the resource configuration of each operator has a significant impact on its overall throughput and latency performance. However, there is a lack of dynamic resource allocation schemes, which are theoretically sound and practically implementable, especially under the drastically changing offered load. To address this challenge, we present Dragster1, an online-optimization-based dynamic resource allocation scheme for elastic stream processing. By combining the online optimization framework with upper confidence bound (UCB) techniques, Dragster can guarantee, in expectation, a sub-linear increase in the throughput regret w.r.t. time. To demonstrate the efficacy, we implement Dragster to improve the throughput of Flink applications over Kubernetes. Compared to the state-of-the-art algorithm Dhalion, Dragster can achieve a 1.8X-2.2X speed-up in converging to the optimal configuration. It can contribute to 20.0%-25.8% gain in tuple-processing goodput and 14.6%-15.6% cost-savings.

To mitigate the straggler effect, today’s systems and computing frameworks have adopted redundancy to launch extra copies for stragglers. Two limitations of the existing straggler-mitigation techniques, however, are that resource demand of tasks is only considered in the context of slots and, moreover, redundancy is seldom coordinated with job scheduling. To tackle these issues, in this paper, we present DollyMP, a job scheduler that addresses multi-resource scheduling with task cloning in heterogeneous clusters. DollyMP carefully combines SRPT (Shortest Remaining Processing Time) and SVF (Smallest Volume First) via knapsack optimization to schedule tasks with multi-resource demands and, in the meanwhile, dynamically launches task clones to yield a small job completion time. DollyMP is built on a strong mathematical foundation to guarantee near-optimal performance. The deployment of our Hadoop YARN prototype on a 30-node cluster demonstrates that DollyMP can reduce job response time by 50% under different cluster loads.

Nearest neighbor query processing is a fundamental problem that arises in many fields such as spatial databases and machine learning. This article aims to address the Secure Nearest Neighbor (SNN) problem in cloud computing. Prior SNN schemes are both insecure and inefficient. In this article, we formally prove and experimentally demonstrate that the SNN scheme ASPE is actually insecure against even ciphertext only attacks. Although prior work proved that it is impossible to construct an SNN scheme even in much relaxed standard security models, we point out the flaws of the hardness proof. We propose an SNN scheme and prove that it is secure against adaptive chosen keyword attacks. Our scheme is efficient as its query processing complexity is logarithmic. To evaluate the efficiency of our SNN scheme, we implemented our scheme in C++ and compared its performance with a plain text scheme, binary scheme, and a PIR scheme on a large set of over 10 million real-world data points. Experimental results show that our scheme is fast (0.124 millisecond per query when data set size is 10 million) and scalable in terms of the number of data points.

Loosely-coupled and light-weight microservices running in containers are replacing monolithic applications gradually. Understanding the characteristics of microservices is critical to make good use of microservice architectures. However, there is no comprehensive study about microservice and its related systems in production environments so far. In this paper, we present a solid analysis of large-scale deployments of microservices at Alibaba clusters. Our study focuses on the characterization of microservice dependency as well as its runtime performance. We conduct an in-depth anatomy of microservice call graphs to quantify the difference between them and traditional DAGs of data-parallel jobs. In particular, we observe that microservice call graphs are heavy-tail distributed and their topology is similar to a tree and moreover, many microservices are hot-spots. We also discover that the structure of call graphs for long-term developed applications is much simpler so as to provide better performance. Our investigation on microservice runtime performance indicates most microservices are much more sensitive to CPU interference than memory interference. Moreover, we design resource management policies to efficiently tune memory resources.

Loosely-coupled and light-weight microservices running in containers are replacing monolithic applications gradually. Understanding the characteristics of microservices is critical to make good use of microservice architectures. However, there is no comprehensive study about microservice and its related systems in production environments so far. In this paper, we present a solid analysis of large-scale deployments of microservices at Alibaba clusters. Our study focuses on the characterization of microservice dependency as well as its runtime performance. We conduct an in-depth anatomy of microservice call graphs to quantify the difference between them and traditional DAGs of data-parallel jobs. In particular, we observe that microservice call graphs are heavy-tail distributed and their topology is similar to a tree and moreover, many microservices are hot-spots. We reveal three types of meaningful call dependency that can be utilized to optimize microservice designs. Our investigation on microservice runtime performance indicates most microservices are much more sensitive to CPU interference than memory interference. To synthesize more representative microservice traces, we build a mathematical model to simulate call graphs. Experimental results demonstrate our model can well preserve those graph properties observed from Alibaba traces.

Jobs in modern computing clusters have highly diverse processing duration and heterogeneous resource requirements. In this paper, we consider the problem of job scheduling for a computing cluster comprised of multiple servers with heterogeneous computation resources, while taking the different resource demands of the jobs into account. Our focus is to achieve a low overall job response time for the system (which is also referred to as the job flowtime) while providing fairness between small and large jobs. Since the job flowtime minimization problem under multiple (even homogeneous) servers are known to be NP-hard, we propose an approximation algorithm to tackle the original online scheduling problem by adopting the recently-proposed notion of fractional job flowtime as a surrogate objective for minimization. For the general online job arrival case with multi-dimensional resource requirements, we apply Online Convex Optimization (OCO) techniques to design the corresponding scheduling algorithm with performance guarantees. In the single-dimensional resource setting, we show that the dynamic fit of the online version of our approximate algorithm grows only sublinearly with respect to time and derive a bound for its dynamic regret when comparing to its offline counterpart. While the baseline version of our proposed scheduling algorithm assumes the possibilities of job preemption and job migration across different servers, we show that the extent of job preemption and migration can be well controlled by augmenting the objective function with the corresponding switching costs.

Recognizing the diversity of big data analytic jobs, cloud providers offer a wide range of virtual machine (VM) instances or even clusters to cater for different use cases. The choice of cloud configurations can have a significant impact on the response time and running cost of data-intensive, production batch-jobs, which need to be re-run regularly using cloud-scale resources. However, identifying the best cloud configuration with a low search cost is quite challenging due to i) the large and high-dimensional configuration-parameters space, ii) the time-varying price of some instance types (e.g. spot-price ones), iii) job execution-time variation even given the same configuration, and iv) gradual drifts / unexpected changes of the characteristics of a recurring job. To tackle these challenges, we have designed and implemented Accordia, a system that enables Adaptive Cloud Configuration Optimization for Recurring Data-Intensive Applications. By leveraging recent algorithmic advances in Gaussian Process UCB (Upper Confidence Bound) techniques, the design of Accordia can handle time-varying instance pricing while providing a performance guarantee of sub-linearly increasing regret when comparing with the static, offline optimal solution. Using extensive trace-driven simulations and empirical measurements of our Kubernetes-based implementation, we demonstrate that Accordia can dynamically learn a near-cost-optimal cloud configuration (i.e. within 10% of the optimum) after fewer than 20 runs from over 7000 candidate choices within a 5-dimension search space, which translates to a 2X-speedup and 17.9% cost-savings, when comparing to CherryPick.

The problem of multi-armed bandit (MAB) with fairness constraint has emerged as an important research topic recently. For such problems, one common objective is to maximize the total rewards within a fixed round of pulls, while satisfying the fairness requirement of a minimum selection fraction for each individual arm in the long run. Previous works have made substantial advancements in designing efficient online selection solutions, however, they fail to achieve a sublinear regret bound when incorporating such fairness constraints. In this paper, we study a combinatorial MAB problem with concave objective and fairness constraints. In particular, we adopt a new approach that combines online convex optimization with bandit methods to design selection algorithms. Our algorithm is computationally efficient, and more importantly, manages to achieve a sublinear regret bound with probability guarantees. Finally, we evaluate the performance of our algorithm via extensive simulations and demonstrate that it outperforms the baselines substantially.

Approximation jobs that allow partial execution of their many tasks to achieve valuable results have played an important role in today's large-scale data analytics. This fact can be utilized to maximize the system utility of a big data computing cluster by choosing proper tasks in scheduling for each approximation job. A fundamental challenge herein, however, is that the machine service capacity may fluctuate substantially during a job's lifetime, which makes it difficult to assign valuable tasks to well-performing machines. In addition, the cluster scheduler needs to make online scheduling decisions without knowing future job arrivals according to machine availabilities. In this paper, we tackle this online resource allocation problem for approximation jobs in parallel computing clusters. In particular, we model a cluster with heterogeneous machines as a multi-armed bandit where each machine is treated as an arm. By making estimations on machine service rates while balancing the exploration-exploitation trade-off, we design an efficient online resource allocation algorithm from a bandit perspective. The proposed algorithm extends existing online convex optimization techniques and yields a sublinear regret bound. Moreover, we also examine the performance of the proposed algorithm via extensive trace-driven simulations and demonstrate that it outperforms the baselines substantially.

Recognizing the diversity of big data analytic jobs, cloud providers offer a wide range of virtual machine (VM) instances for different use cases. The choice of cloud instance configurations can have significant impact on the response time and running cost of data-intensive, recurring jobs for production. A poor choice of cloud instance-type/configuration can substantially degrade the response time by 5x, or increase the cost by 10x. Identifying the best cloud configuration under low search budget is a challenging problem due to i) the large and high-dimensional configuration-parameters space, ii) the dynamically varying price of some instance types, iii) job response time variation even given the same configuration, and iv) gradual drifts/ unexpected changes of the characteristics of the recurring jobs. To tackle this problem, we have designed and implemented Accordia, a system which enables Adaptive Cloud Configuration Optimization for Recurring Data-Intensive Applications.

Nearest neighbor query processing is a fundamental problem that arises in many fields such as spatial databases and machine learning. ASPE, which uses invertible matrices to encrypt data, is a widely adopted Secure Nearest Neighbor (SNN) query scheme. Encrypting data by matrices is actually a linear combination of the multiple dimensions of the data, which is completely consistent with the relationship between the source signals and observed signals in the signal processing. By viewing dimensions of the data and the encrypted data as source signals and observed signals, respectively, we formally prove and experimentally demonstrate that ASPE is actually insecure against even ciphertext only attacks, using signal processing theory. Prior work proved that it is impossible to construct an SNN scheme even in much relaxed standard security models, we invalidate this hardness understanding by pointing out the incorrectness of the hardness proof.

Jobs in modern computing clusters have highly diverse processing durations and heterogeneous resource requirements. In this paper, we consider the problem of online job scheduling for a computing cluster comprised of multiple servers with heterogeneous computation resources, while taking the diversity of resource demands for different jobs into account. Our focus is to achieve a low overall job response time for the system (which is also referred to as the job flowtime) while providing fairness between small and large jobs. Since the job flowtime minimization problem under multiple (even homogeneous) servers are known to be NP-hard, we propose an approximation algorithm to tackle the original online scheduling problem by adopting the notion of fractional job flowtime as a surrogate objective for minimization. We apply Online Convex optimization (OCO) techniques to design the corresponding online scheduling algorithm. More importantly, we show that the dynamic fit of the online version of our approximate algorithm grows only sublinearly with respect to time and derive a bound for its dynamic regret when comparing to its offline counterpart. While the baseline version of our proposed scheduling algorithm assumes the possibilities of job preemption and job migration across different servers, we show that the extent of job preemption and migration can be well controlled by augmenting the objective function of our online convex optimization formulation with the corresponding switching costs.

Approximation jobs that allow partial execution of their many tasks to achieve valuable results have played an important role in today’s large-scale data analytics [1], [2]. This fact can be utilized to maximize the system utility of a big data computing cluster by choosing proper tasks in scheduling for each approximation job. A fundamental challenge herein, however, is that the machine service capacity may fluctuate substantially during a job’s lifetime, which makes it difficult to assign valuable tasks to well-performed machines. In addition, the cluster scheduler needs to make online scheduling decisions without knowing future job arrivals according to machine availabilities. In this paper, we tackle this online resource allocation problem for approximation jobs in parallel computing clusters. In particular, we model a cluster with heterogeneous machines as a multi-armed bandit where each machine is treated as an arm. By making estimations on machine service rates while balancing the exploration-exploitation trade-off, we design an efficient online resource allocation algorithm from a bandit perspective. The proposed algorithm extends existing online convex optimization techniques and yields a sublinear regret bound. Moreover, we also examine the performance of the proposed algorithm via extensive trace-driven simulations and demonstrate that it outperforms the baselines substantially.

In a large-scale computing cluster, the job completions can be substantially delayed due to two sources of variability, namely, variability in the job size and that in the machine service capacity. To tackle this issue, existing works have proposed various scheduling algorithms which exploit redundancy wherein a job runs on multiple servers until the first completes. In this paper, we explore the impact of variability in the machine service capacity and adopt a rigorous analytical approach to design scheduling algorithms using redundancy and checkpointing. We design several online algorithms which can dynamically vary the number of redundant copies for jobs. We also provide new theoretical performance bounds for these algorithms in terms of the overall job flowtime by introducing the notion of a speedup function, based on which a novel potential function can be defined to enable the corresponding competitive ratio analysis. In particular, by adopting the online primal-dual fitting approach, we prove that our SRPT+R Algorithm in a non-multitasking cluster is$(1+\epsilon)$-speed,$\ O(\frac{1}{\epsilon })$-competitive. We also show that our proposed Fair+R and LAPS+R($\beta$) Algorithms for a multitasking cluster are$(4+\epsilon)$-speed,$\ O(\frac{1}{\epsilon })$-competitive and ($2 + 2\beta + 2\epsilon)$-speed$O(\frac{1}{\beta \epsilon })$-competitive respectively. We demonstrate via extensive simulations that our proposed algorithms can significantly reduce job flowtime under both the non-multitasking and multitasking modes.

The use of color in QR codes brings extra data capacity, but also inflicts tremendous challenges on the decoding process due to chromatic distortion-cross-channel color interference and illumination variation. Particularly, we further discover a new type of chromatic distortion in high-density color QR codes-cross-module color interference-caused by the high density which also makes the geometric distortion correction more challenging. To address these problems, we propose two approaches, LSVM-CMI and QDA-CMI, which jointly model these different types of chromatic distortion. Extended from SVM and QDA, respectively, both LSVM-CMI and QDA-CMI optimize over a particular objective function and learn a color classifier. Furthermore, a robust geometric transformation method and several pipeline refinements are proposed to boost the decoding performance for mobile applications. We put forth and implement a framework for high-capacity color QR codes equipped with our methods, called HiQ. To evaluate the performance of HiQ, we collect a challenging large-scale color QR code dataset, CUHK-CQRC, which consists of 5390 high-density color QR code samples. The comparison with the baseline method [2] on CUHK-CQRC shows that HiQ at least outperforms [2] by 188% in decoding success rate and 60% in bit error rate. Our implementation of HiQ in iOS and Android also demonstrates the effectiveness of our framework in real-world applications.

The completion times of jobs in a computing cluster may be influenced by a variety of factors including job size and machine processing variability. In this paper, we explore online resource allocation policies which combine size-dependent scheduling with redundant execution and opportunistic checkpointing to minimize the overall job flowtime. We introduce a simplified model for the job service capacity of a computing cluster while leveraging redundant execution/checkpointing. In this setting, we propose two resource allocation algorithms, SRPT+R and LAPS+R(β) subject to checkpointing overhead not exceeding the number of jobs which are processed. We provide new theoretical performance bounds for these algorithms: SRPT+R is shown to be O(1/∊) competitive under (1 + ∊)-speed resource augmentation, while LAPS+R(β) is shown to be O(1/β∊) competitive under (2+ 2β + 2∊)-speed resource augmentation.

A big parallel processing job can be delayed substantially as long as one of its many tasks is being assigned to an unreliable or congested machine. To tackle this so-called straggler problem, most parallel processing frameworks such as MapReduce have adopted various strategies under which the system may speculatively launch additional copies of the same task if its progress is abnormally slow when extra idling resource is available. In this paper, we focus on the design of speculative execution schemes for parallel processing clusters from an optimization perspective under different loading conditions. For the lightly loaded case, we analyze and propose one cloning scheme, namely, the Smart Cloning Algorithm (SCA) which is based on maximizing the overall system utility. We also derive the workload threshold under which SCA should be used for speculative execution. For the heavily loaded case, we propose the Enhanced Speculative Execution (ESE) algorithm which is an extension of the Microsoft Mantri scheme to mitigate stragglers. Our simulation results show SCA reduces the total job flowtime, i.e., the job delay/ response time by nearly$6$percent comparing to the speculative execution strategy of Microsoft Mantri. In addition, we show that the ESE Algorithm outperforms the Mantri baseline scheme by$71$percent in terms of the job flowtime while consuming the same amount of computation resource.

Measurement traces from real-world production environment show that the execution time of tasks within a MapReduce job varies widely due to the variability in machine service capacity. This variability issue makes efficient job scheduling over large-scale MapReduce clusters extremely challenging. To tackle this problem, we adopt the task cloning approach to mitigate the effect of machine variability and design corresponding scheduling algorithms so as to minimize the overall job flowtime in different scenarios. For offline scheduling where all jobs arrive at the same time, we design an$O(1)$-competitive algorithm, which gives priorities to jobs with small effective workload. We then extend this offline algorithm to yield the so-called Smallest Remaining Effective Workload based$\beta$-fraction Sharing plus Cloning algorithm (SREW+C($\beta$)) for the online case. We also show that SREW+C($\beta$) is$(1+ 2\beta + \epsilon)$-speed$O(\frac{1}{\beta \epsilon })$-competitive with respect to the sum of job flowtime within a cluster. We demonstrate via trace-driven simulations that SREW+C($\beta$) can significantly reduce the overall job flowtime by cutting down the elapsed time of small jobs substantially. In particular, SREW+C($\beta$) reduces the total job flowtime by 14, 10 and 11 percent respectively when comparing to Mantri, Dolly and Grass.

The seminal works by Karger [13], [14] have shown that one can use Uniform Random Edge (URE) sampling to generate a graph skeleton which accurately approximates all cut-values in the original graph with high probability under some specific assumptions. As such, the random subgraphs resulted from URE sampling can often be used as substitutes for the original graphs in cut/flow-related graph-optimization problems [14]. In this paper, we extend the results of Karger to show that, besides the value (weight) of the cut-set, the weights of four additional types of edge-set, namely, Volume, Association, Complement Volume and Complement Association, are all well-preserved under URE sampling. More importantly, we show that these well-preserved edge-set metrics have dominant impact on the outcome of common graph-mining tasks including PageRank computation and Community Detection. As a result, URE sampling can be used to accelerate the corresponding graph-mining algorithms with small approximation errors. Via extensive experiments with large-scale graphs in practice, we demonstrate that URE sampling can achieve over 90% accuracy for PageRank computation and Modularity-based Community Detection by sampling only 20% edges of the original graph.

Job scheduling for a MapReduce cluster has been an active research topic in recent years. However, measurement traces from real-world production environment show that the duration of tasks within a job vary widely. The overall elapsed time of a job, i.e. The so-called flow time, is often dictated by one or few slowly-running tasks within a job, generally referred as the "stragglers". The cause of stragglers include tasks running on partially/intermittently failing machines or the existence of some localized resource bottleneck(s) within a MapReduce cluster. To tackle this online job scheduling challenge, we adopt the task cloning approach and design the corresponding scheduling algorithms which aim at minimizing the weighted sum of job flow times in a MapReduce cluster based on the Shortest Remaining Processing Time scheduler (SRPT). To be more specific, we first design a 2-competitive offline algorithm when the variance of task-duration is negligible. We then extend this offline algorithm to yield the so-called SRPTMS+C algorithm for the online case and show that SRPTMS+C is (1+∊) -- speed o(1/∊2) -- competitive in reducing the weighted sum of job flow times within a cluster. Both of the algorithms explicitly consider the precedence constraints between the two phases within the MapReduce framework. We also demonstrate via trace-driven simulations that SRPTMS+C can significantly reduce the weighted/unweighted sum of job flow times by cutting down the elapsed time of small jobs substantially. In particular, SRPTMS+C beats the Microsoft Mantri scheme by nearly 25% according to this metric.

Social Networking Service has become an essential part of our life today. However, many privacy concerns have recently been raised due to the centralized nature of such services. Decentralized Social Network (DSN) is believed to be a viable solution for these problems. In this paper, we design a protocol to coordinate the pulling operation of DSN nodes. The protocol is the result of forward engineering via utility maximization that takes communication layer congestion level as well as social network layer centrality into consideration. We solve the pulling rate control problem using the primal-dual approach and prove that the protocol can converge quickly when executed in a decentralized manner. Furthermore, we develop a novel “drumbeats” algorithm to estimate node centrality purely based on passively-observed information. Simulation results show that our protocol reduces the average message propagation delay by 15% when comparing to the baselined Fixed Equal Gap Pull protocol. In addition, the estimated node centrality matches well with the ground-truth derived from the actual topology of the social network.

A parallel processing job can be delayed substantially as long as one of its many tasks is being assigned to an unreliable machine. To tackle this so-called straggler problem, most parallel processing frameworks such as MapReduce have adopted various strategies under which the system may speculatively launch additional copies of the same task if its progress is abnormally slow or simply because extra idling resource is available. In this paper, we focus on the design of speculative execution schemes for a parallel processing cluster under different loading conditions. For the lightly loaded case, we analyze and propose two optimization-based schemes, namely, the Smart Cloning Algorithm (SCA) which is based on maximizing the job utility. We also derive the workload threshold under which SCA should be used for speculative execution. Our simulation results show SCA can reduce the total job flowtime by nearly 22% comparing to the speculative execution strategy of Microsoft Mantri. For the heavily loaded case, we propose the Enhanced Speculative Execution (ESE) algorithm which is an extension of the Microsoft Mantri scheme. We show that the ESE algorithm can beat the Mantri baseline scheme by 35% in terms of job flowtime while consuming the same amount of resource.

Parallel processing plays an important role for large-scale data analytics. It breaks a job into many small tasks which run parallel on multiple machines such as MapReduce framework. One fundamental challenge faced to such parallel processing is the straggling tasks as they can delay the completion of a job seriously. In this paper, we focus on the speculative execution issue which is used to deal with the straggling problem in the literature. We present a theoretical framework for the optimization of a single job which differs a lot from the previous heuristics-based work. More precisely, we propose two schemes when the number of parallel tasks the job consists of is smaller than cluster size. In the first scheme, no monitoring is needed and we can provide the job deadline guarantee with a high probability while achieve the optimal resource consumption level. The second scheme needs to monitor the task progress and makes the optimal number of duplicates when the straggling problem happens. On the other hand, when the number of tasks in a job is larger than the cluster size, we propose an Enhanced Speculative Execution (ESE) algorithm to make the optimal decision whenever a machine is available for a new scheduling. The simulation results show the ESE algorithm can reduce the job flow time by 50% while consume fewer resources comparing to the strategy without backup.

We present a design framework of regenerating codes for distributed storage systems which employ binary additions and bit-wise cyclic shifts as the basic operations. The proposed coding method can be regarded as a concatenation coding scheme with the outer code being a binary cyclic code, and the inner code a regenerating code utilizing the binary cyclic code as the alphabet set. The advantage of this approach is that encoding and repair of failed node can be done with low computational complexity. It is proved that the proposed coding method can achieve the fundamental tradeoff curve between the storage and repair bandwidth asymptotically when the size of the data file is large.

The MapReduce paradigm is now the de facto standard for large-scale data analytics. In this paper we address the resource management issues in MapReduce Cluster. Speculative execution (task backup) plays an important role in resource management. We propose two different strategies and build two models to formulate the backup issue as an optimization problem when the cluster is lightly loaded. Moreover, we present an Enhanced Speculative Execution (ESE) algorithm when the cluster is heavily loaded and adopt the approximate analysis to get an optimal value for the parameter in the algorithm. The simulation results show that the algorithm can reduce the job completion time by 50% while consuming much less resource compared to the naive method without backup.