Reinforcement Learning (RL) learns optimal decision-making policies from experiential (transition) datasets and maximizes the RL agent’s cumulative rewards. In order to improve the RL training efficiency, prior works have studied how to selectively sample certain critical transitions that ultimately lead to better policies and rewards. However, RL workloads still face significant challenges from a systems perspective, particularly when the agent iteratively accesses batches of data from transition datasets, whose growing sizes continue to challenge the memory hierarchy. This results in frequent and costly memory transfers between caches and Dynamic Random Access Memory (DRAM), which negatively impacts the overall training time.In this paper, we propose RACER, our novel caching layerbased optimization for RL training workloads. Firstly, recognizing that the RL agent repeatedly accesses large transition batches from growing datasets, we design a storage-cache that prioritizes critical transitions to fit within the hardware cache hierarchies. This design reduces the memory access times by sampling from a subset of critical transitions and minimizes the costly memory trips to DRAM. Second, we demonstrate how to smartly leverage key metrics (viz., temporal difference error and advantage weighting) to quantify the importance/relevance of transitions during policy optimization and to identify the transition data that would need to be spilled out of (or filled into) the caching system. We also introduce dynamic optimizations to our caching system that minimize the prospect of discarding the critical transitions. Our performance evaluation across three state-of-the-art RL algorithms, under various task environments, and on three different systems, demonstrates that RACER achieves significant optimization time improvements to the RL transition data sampling phase (a speedup of $6 \times$) and end-to-end training time (up to $2 \times$) with comparable rewards.

Spectrum sharing is a key enabler for 5G/6G. We model decentralized spectrum access as a noncooperative, stochastic, imperfect-information extensive-form game and show that running standard Counterfactual Regret Minimization (CFR) independently at each user can exhibitpersistent cyclingrather than converging to a stable equilibrium. We provide a constructive multi-player example and a mapping analysis explaining why the induced regret-matching update need not be contractive in general multi-player, non-zero-sum settings. To address this, we propose CFR-M2, a lightweightregret-mixingscheme that periodically aggregates a small amount ofcumulative regret(not policy parameters) across users at a configurable communication interval. Our analysis shows that inserting an infrequent regret-consensus step over any connected communication graph preserves no-(counterfactual)-regret whilecontracting inter-agent disagreement in regrets. Consequently, the C´esaro-averaged play converges to an ε–extensive-form coarse correlated equilibrium (EFCCE) with ε=Õ(1/√T)+O(RMAXTCOMM/(1-ρ)T) where ρ is the second-largest eigenvalue modulus of the mixing matrix. Under additional structure (e.g., a strongly monotone pseudo-gradient or a strongly convex potential), the EFCCE collapses to a unique Nash equilibrium. Experiments on synthetic networks and a 5G Dynamic Spectrum Sharing (DSS) scenario (WINNER II channel model and practical parameter settings) show that CFR-M2improves convergence stability and system reward over CFR and several learning/game-theoretic baselines, while requiring onlyinfrequentcommunications.

With the advancements of artificial intelligence (AI), emerging scenarios involving close collaboration between AI and other unknown agents are becoming increasingly common. This requires sometimes training AI agents to collaborate with unknown agents in the absence of a reward function -- which may be unavailable to the AI agents or even undefined by the unknown agents themselves -- thus posing news challenges to existing learning algorithms that often require knowing the shared reward. In this paper, we show that effective teaming with unknown agents can be achieved in the absence of a reward function, through actively modeling other unknown agents and reasoning about their latent rewards from available interaction/observation history. In particular, we propose a novel framework that leverages a kernel density Bayesian inverse learning method for active reward/goal inference and prove that multi-agent reinforcement learning guided by the inferred reward signals can converge to an optimal policy teaming with unknown agents. The result enables us to develop an adaptive policy update strategy, through the use of a family of pre-trained, goal-conditioned policies, further eliminating the need for online retraining. The proposed solution is evaluated using a wide range of diverse unknown agents of latent and even non-stationary reward. Our solution significantly increases the teaming performance between AI and unknown agents in the absence of reward.

As rapidly growing AI computational demands accelerate the need for new hardware installation and maintenance, this work explores optimal data center resource management by balancing operational efficiency with fault tolerance through strategic rack positioning considering diverse resources and locations. Traditional mixed-integer programming (MIP) approaches often struggle with scalability, while heuristic methods may result in significant sub-optimality. To address these issues, this paper presents a novel two-tier optimization framework using a high-level deep reinforcement learning (DRL) model to guide a low-level gradient-based heuristic for local search. The high-level DRL agent employs Leader Reward for optimal rack type ordering, and the low-level heuristic efficiently maps racks to positions, minimizing movement counts and ensuring fault-tolerant resource distribution. This approach allows scalability to over 100,000 positions and 100 rack types. Our method outperformed the gradient-based heuristic by 7% on average and the MIP solver by over 30% in objective value. It achieved a 100% success rate versus MIP's 97.5% (within a 20-minute limit), completing in just 2 minutes compared to MIP's 1630 minutes (i.e., almost 4 orders of magnitude improvement). Unlike the MIP solver, which showed performance variability under time constraints and high penalties, our algorithm consistently delivered stable, efficient results—an essential feature for large-scale data center management.

Skills are effective temporal abstractions established for sequential decision making, which enable efficient hierarchical learning for long-horizon tasks and facilitate multi-task learning through their transferability. Despite extensive research, research gaps remain in multi-agent scenarios, particularly for automatically extracting subgroup coordination patterns in a multi-agent task. In this case, we propose two novel auto-encoder schemes: VO-MASD-3D and VO-MASD-Hier, to simultaneously capture subgroup- and temporal-level abstractions and form multi-agent skills, which firstly solves the aforementioned challenge. An essential algorithm component of these schemes is a dynamic grouping function that can automatically detect latent subgroups based on agent interactions in a task. Further, our method can be applied to offline multi-task data, and the discovered subgroup skills can be transferred across relevant tasks without retraining. Empirical evaluations on StarCraft tasks indicate that our approach significantly outperforms existing hierarchical multi-agent reinforcement learning (MARL) methods. Moreover, skills discovered using our method can effectively reduce the learning difficulty in MARL scenarios with delayed and sparse reward signals. The codebase is available at: https://github.com/LucasCJYSDL/VOMASD.

Cybersickness remains a major challenge in virtual and mixed reality (VR/MR), yet existing methods primarily focus on predicting its onset without offering formal guarantees regarding its occurrence or effective mitigation. As VR/MR applications expand into safety-critical domains like healthcare, defense, verifiable safety assurances become essential to protect users from adverse physiological and psychological effects. This paper introduces a probabilistic verification framework leveraging Bayesian Networks (BN) to explicitly model the interactions among system parameters, human physiological responses, and cybersickness severity. Unlike deep learning approaches that lack interpretability and formal verification capabilities, the proposed BN model explicitly captures how environmental and system-level factors (e.g., luminance, spectral entropy, and image gradient complexity via HoG features) influence physiological responses (e.g., heart rate, reaction time, eye tracking), ultimately affecting cybersickness severity. By learning the joint probability distribution of these factors, our approach provides rigorous formal guarantees on cybersickness risk under specified operational conditions. If these guarantees are not met, automated adaptive adjustments are recommended to restore safe conditions. Experimental validation involving physiological and systemlevel data demonstrates that Bayesian Networks provide an interpretable and efficient framework, uniquely enabling formal probabilistic verification of cybersickness risks. This capability makes the proposed approach particularly suitable for designing and deploying VR/MR systems with explicitly verified safety constraints.

Augmented reality (AR) systems are increasingly deployed in tactical environments, but their reliance on seamless human-computer interaction makes them vulnerable to cognitive attacks that manipulate a user's perception and severely compromise user decisionmaking. To address this challenge, we introduce the Perception Graph, a novel model designed to reason about human perception within these systems. Our model operates by first mimicking the human process of interpreting key information from an MR environment and then representing the outcomes using a semantically meaningful structure. We demonstrate how the model can compute a quantitative score that reflects the level of perception distortion, providing a robust and measurable method for detecting and analyzing the effects of such cognitive attacks.

Cognitive attacks in mixed reality (MR), e.g., latency perturbations that induce frame-time jitter, can divert visual attention and degrade task performance. We study 2D gaze prediction under such disturbances and propose a time-aware sequence model that handles irregular sampling by supplying elapsed times Δt between observations and conditions on sparse event/object context available at prediction time via learned token embeddings. Using time-based windows, we evaluate within-user and cross-user temporal generalization on MR recordings spanning multiple attack intensities. Results indicate accurate, time-robust gaze regression under latency perturbations, supporting adaptive MR interfaces in adversarial settings.

Ensuring the safety of neural network (NN) models in mixed reality (MR) systems is challenging due to adversarial manipulation of system parameters. We present PolySafe, which extends DeepPoly and Prover to validate safety of LSTM-based MR models. PolySafe unrolls temporal dependencies, introduces multi-plane abstractions for tighter bounds, and establishes probabilistic safety guarantees. It further includes an adaptive search that identifies minimal sets of critical parameters required to be constrained for defense. Evaluation on an MR engagement prediction model shows that PolySafe provides rigorous and actionable safety assurances for deployment.

Personal characteristics fundamentally shape virtual reality (VR) experiences, yet their integration into predictive models remains underexplored. This paper studies how to incorporate personal attributes (age, gender, prior VR experience) into Bayesian networks for cybersickness prediction via: (i) direct inclusion as root nodes, (ii) a two-stage model that learns a susceptibility score from personal attributes, and (iii) a stratified model. Using 26,040 samples from VR maze-navigation experiments, direct inclusion attains 82.53% accuracy (+14.02 percentage points over a 68.51% no-personal baseline). The two-stage approach reaches 77.32% while supporting cold-start prediction for unseen users, and stratified models achieve 73.62%. Using participant-level cross-validation to avoid subject leakage, we find that personalization consistently improves cybersickness prediction. These results argue that personal attributes should be treated as first-class signals in cybersickness models, with clear design trade-offs between maximal accuracy and deployability for unseen users, informing personalized VR systems and adaptive content delivery.

Monte Carlo Tree Search (MCTS), which leverages Upper Confidence Bound for Trees (UCTs) to balance exploration and exploitation through randomized sampling, is instrumental to solving complex planning problems. However, for multi-agent planning, MCTS is confronted with a large combinatorial action space that often grows exponentially with the number of agents. As a result, the branching factor of MCTS during tree expansion also increases exponentially, making it very difficult to efficiently explore and exploit during tree search. To this end, we propose MALinZero, a new approach to leverage low-dimensional representational structures on joint-action returns and enable efficient MCTS in complex multi-agent planning. Our solution can be viewed as projecting the joint-action returns into the low-dimensional space representable using a contextual linear bandit problem formulation. We solve the contextual linear bandit problem with convex and $\mu$-smooth loss functions -- in order to place more importance on better joint actions and mitigate potential representational limitations -- and derive a linear Upper Confidence Bound applied to trees (LinUCT) to enable novel multi-agent exploration and exploitation in the low-dimensional space. We analyze the regret of MALinZero for low-dimensional reward functions and propose an $(1-\tfrac1e)$-approximation algorithm for the joint action selection by maximizing a sub-modular objective. MALinZero demonstrates state-of-the-art performance on multi-agent benchmarks such as matrix games, SMAC, and SMACv2, outperforming both model-based and model-free multi-agent reinforcement learning baselines with faster learning speed and better performance.

Many emerging applications in edge computing require processing of huge volumes of data generated by end devices, using the freshest available information. In this paper, we address the distributed optimization of multi-user long-term average Age-of-Information (AoI) objectives in edge networks that use NOMA transmission. This poses a challenge of non-convex online optimization, which in existing work often requires either decision making in a combinatorial space or a global view of entire network states. To overcome this challenge, we propose a reinforcement learning-based framework that adopts a novel hierarchical decomposition of decision making. Specifically, we propose three different types of distributed agents to learn with respect to efficiency of AoI scheduling, fairness of AoI scheduling, as well as a high-level policy balancing these potentially conflicting design objectives. Not only does the proposed decomposition improve learning performance due to disentanglement of different design objectives/rewards, but it also enables the algorithm to learn the best policy while also learning the explanations – as actions can be directly compared in terms of the design objectives. Our evaluations show that the proposed algorithm improves the long-term average AoI by$200\%{-}300\%$and 400% compared to prior works with NOMA and the optimal solution without NOMA, respectively.

Online optimization of resource management for large-scale data centers and infrastructures to meet dynamic capacity reservation demands and various practical constraints (e.g., feasibility and robustness) is a very challenging problem. Mixed Integer Programming (MIP) approaches suffer from recognized limitations in such a dynamic environment, while learning-based approaches may face with prohibitively large state/action spaces. To this end, this paper presents a novel two-tiered online optimization to enable a learning-based Resource Allowance System (RAS). To solve optimal server-to-reservation assignment in RAS in an online fashion, the proposed solution leverages a reinforcement learning (RL) agent to make high-level decisions, e.g., how much resource to select from the Main Switch Boards (MSBs), and then a low-level Mixed Integer Linear Programming (MILP) solver to generate the local server-to-reservation mapping, conditioned on the RL decisions. We take into account fault tolerance, server movement minimization, and network affinity requirements and apply the proposed solution to large-scale RAS problems. To provide interpretability, we further train a decision tree model to explain the learned policies and to prune unreasonable corner cases at the low-level MILP solver, resulting in further performance improvement. Extensive evaluations show that our two-tiered solution outperforms baselines such as pure MIP solver by over 15% while delivering$100\times $speedup in computation.

The integration of Large Language Models (LLMs) like GPT-4 with Extended Reality (XR) technologies offers the potential to build truly immersive XR environments that interact with human users through natural language, e.g., generating and animating 3D scenes from audio inputs. However, the complexity of XR environments makes it difficult to accurately extract relevant contextual data and scene/object parameters from an overwhelming volume of XR artifacts. It leads to not only increased costs with pay-per-use models, but also elevated levels of generation errors. Moreover, existing approaches focusing on coding script generation are often prone to generation errors, resulting in flawed or invalid scripts, application crashes, and ultimately a degraded user experience. To overcome these challenges, we introduce LLMER, a novel framework that creates interactive XR worlds using JSON data generated by LLMs. Unlike prior approaches focusing on coding script generation, LLMER translates natural language inputs into JSON data, significantly reducing the likelihood of application crashes and processing latency. It employs a multi-stage strategy to supply only the essential contextual information adapted to the user's request and features multiple modules designed for various XR tasks. Our preliminary user study reveals the effectiveness of the proposed system, with over 80% reduction in consumed tokens and around 60% reduction in task completion time compared to state-of-the-art approaches. The analysis of users' feedback also illuminates a series of directions for further optimization.

Communication is crucial for solving cooperative Multi-Agent Reinforcement Learning tasks in partially observable Markov Decision Processes. Existing works often rely on black-box methods to encode local information/features into messages shared with other agents, leading to the generation of continuous messages with high communication overhead and poor interpretability. Prior attempts at discrete communication methods generate one-hot vectors trained as part of agents' actions and use the Gumbel softmax operation for calculating message gradients, which are all heuristic designs that do not provide any quantitative guarantees on the expected return. This paper establishes an upper bound on the return gap between an ideal policy with full observability and an optimal partially observable policy with discrete communication. This result enables us to recast multi-agent communication into a novel online clustering problem over the local observations at each agent, with messages as cluster labels and the upper bound on the return gap as clustering loss. To minimize the return gap, we propose the Return-Gap-Minimization Communication (RGMComm) algorithm, which is a surprisingly simple design of discrete message generation functions and is integrated with reinforcement learning through the utilization of a novel Regularized Information Maximization loss function, which incorporates cosine-distance as the clustering metric. Evaluations show that RGMComm significantly outperforms state-of-the-art multi-agent communication baselines and can achieve nearly optimal returns with few-bit messages that are naturally interpretable.

Value function factorization has achieved great success in multi-agent reinforcement learning by optimizing joint action-value functions through the maximization of factorized per-agent utilities. To ensure Individual-Global-Maximum property, existing works often focus on value factorization using monotonic functions, which are known to result in restricted representation expressiveness. In this paper, we analyze the limitations of monotonic factorization and present ConcaveQ, a novel non-monotonic value function factorization approach that goes beyond monotonic mixing functions and employs neural network representations of concave mixing functions. Leveraging the concave property in factorization, an iterative action selection scheme is developed to obtain optimal joint actions during training. It is used to update agents’ local policy networks, enabling fully decentralized execution. The effectiveness of the proposed ConcaveQ is validated across scenarios involving multi-agent predator-prey environment and StarCraft II micromanagement tasks. Empirical results exhibit significant improvement of ConcaveQ over state-of-the-art multi-agent reinforcement learning approaches.

Bayesian optimization (BO) has established itself as a leading strategy for efficiently optimizing expensive-to-evaluate functions. Existing BO methods mostly rely on Gaussian process (GP) surrogate models and are not applicable to (doubly-stochastic) Gaussian Cox processes, where the observation process is modulated by a latent intensity function modeled as a GP. In this paper, we propose a novel maximum *a posteriori* inference of Gaussian Cox processes. It leverages the Laplace approximation and change of kernel technique to transform the problem into a new reproducing kernel Hilbert space, where it becomes more tractable computationally. It enables us to obtain both a functional posterior of the latent intensity function and the covariance of the posterior, thus extending existing works that often focus on specific link functions or estimating the posterior mean. Using the result, we propose a BO framework based on the Gaussian Cox process model and further develop a Nyström approximation for efficient computation. Extensive evaluations on various synthetic and real-world datasets demonstrate significant improvement over state-of-the-art inference solutions for Gaussian Cox processes, as well as effective BO with a wide range of acquisition functions designed through the underlying Gaussian Cox process model.

Reinforcement Learning (RL) is the process by which an agent learns optimal behavior through interactions with experience datasets, all of which aim to maximize the reward signal. RL algorithms often face performance challenges in real-world applications, especially when training with extensive and diverse datasets. For instance, applications like autonomous vehicles include sensory data, dy-namic traffic information (including movements of other vehicles and pedestrians), critical risk assessments, and varied agent actions. Consequently, RL training is significantly memory-bound due to sampling large experience datasets that may not fit entirely into the hardware caches and frequent data transfers needed between memory and the computation units (e.g., CPU, GPU), especially during batch updates. This bottleneck results in significant execution latencies and impacts the overall training time. To alleviate such is-sues, recently proposed memory-centric computing paradigms, like Processing-In-Memory (PIM), can address memory latency-related bottlenecks by performing the computations inside the memory devices. In this paper, we present SwiftRL, which explores the potential of real-world PIM architectures to accelerate popular RL workloads and their training phases. We adapt RL algorithms, namely Tab-ular Q-learning and SARSA, on UPMEM PIM systems and first observe their performance using two different environments and three sampling strategies. We then implement performance opti-mization strategies during RL adaptation to PIM by approximating the Q-value update function (which avoids high performance costs due to runtime instruction emulation used by runtime libraries) and incorporating certain PIM-specific routines specifically needed by the underlying algorithms. Moreover, we develop and assess a multi-agent version of Q-learning optimized for hardware and illustrate how PIM can be leveraged for algorithmic scaling with multiple agents. We experimentally evaluate RL workloads on OpenAI GYM environments using UPMEM hardware. Our results demonstrate a near-linear scaling of 15x in performance when the number of PIM cores increases by 16x (125 to 2000). We also compare our PIM implementation against Intel(R) Xeon(R) Silver 4110 CPU and NVIDIA RTX 3090 GPU and observe superior performance on the UPMEM PIM System for different implementations.

Deep Reinforcement Learning (DRL) algorithms have achieved great success in solving many challenging tasks while their black-box nature hinders interpretability and real-world applicability, making it difficult for human experts to interpret and understand DRL policies. Existing works on interpretable reinforcement learning have shown promise in extracting decision tree (DT) based policies from DRL policies with most focus on the single-agent settings while prior attempts to introduce DT policies in multi-agent scenarios mainly focus on heuristic designs which do not provide any quantitative guarantees on the expected return. In this paper, we establish an upper bound on the return gap between the oracle expert policy and an optimal decision tree policy. This enables us to recast the DT extraction problem into a novel non-euclidean clustering problem over the local observation and action values space of each agent, with action values as cluster labels and the upper bound on the return gap as clustering loss. Both the algorithm and the upper bound are extended to multi-agent decentralized DT extractions by an iteratively-grow-DT procedure guided by an action-value function conditioned on the current DTs of other agents. Further, we propose the Return-Gap-Minimization Decision Tree (RGMDT) algorithm, which is a surprisingly simple design and is integrated with reinforcement learning through the utilization of a novel Regularized Information Maximization loss. Evaluations on tasks like D4RL show that RGMDT significantly outperforms heuristic DT-based baselines and can achieve nearly optimal returns under given DT complexity constraints (e.g., maximum number of DT nodes).

Cybersecurity at the edge requires fast computing in energy-constrained environments. Decision trees can provide an explainable solution for network intrusion detection with high detection accuracy at the packet level. However, their hardware implementation needs to support efficient real-time operation. In this paper, we propose a spatially distributed decision tree for network intrusion detection, using memristor-based chiplet leaves. Each chiplet processes an input by comparing it to a predefined boundary stored in the memristor cell and provides a binary output to select one of the interconnected leaves on the lower level, with an estimated power consumption in a 130nm node design of 389$\mu$W. The delay is 2.5$\mu$s for one inference decision. This chiplet approach is reconfigurable and in line with the natural architecture of decision trees. It also supports the prototyping with known good dies, overcoming the non-idealities challenge prevalent in memristor technologies. Our memristor-based decision trees show high intrusion detection accuracy of 82%, 84%, and 73% on the benchmark UNSW, CIC-IDS, and ACI-IoT datasets respectively, considering 6-bit device precision in one memristor vs. three memristor per boundary configurations. This distributed approach opens the way to utilizing memristor technology despite device defects for applications in need of local real-time computing.

Federated learning (FL) enables edge devices to collaboratively learn a model in a distributed fashion. Many existing researches have focused on improving communication efficiency of high-dimensional models and addressing bias caused by local updates. However, most FL algorithms are either based on reliable communications or assuming fixed and known unreliability characteristics. In practice, networks could suffer from dynamic channel conditions and non-deterministic disruptions, with time-varying and unknown characteristics. To this end, in this paper we propose a sparsity-enabled FL framework with both improved communication efficiency and bias reduction, termed as SAFARI. It makes use of similarity among client models to rectify and compensate for bias that results from unreliable communications. More precisely, sparse learning is implemented on local clients to mitigate communication overhead, while to cope with unreliable communications, a similarity-based compensation method is proposed to provide surrogates for missing model updates. With respect to sparse models, we analyze SAFARI under bounded dissimilarity. It is demonstrated that SAFARI under unreliable communications is guaranteed to converge at the same rate as the standard FedAvg with perfect communications. Implementations and evaluations on the CIFAR-10 dataset validate the effectiveness of SAFARI by showing that it can achieve the same convergence speed and accuracy as FedAvg with perfect communications, with up to 60% of the model weights being pruned and a high percentage of client updates missing in each round of model updates.

The widespread adoption of Federated Learning (FL), a privacy-preserving distributed learning methodology, has been impeded by the challenge of high communication overheads, typically arising from the transmission of large-scale models. Existing adaptive quantization methods, designed to mitigate these overheads, operate under the impractical assumption of uniform device participation. Additionally, these methods are limited in their adaptability due to the necessity of manual quantization level selection and often overlook biases inherent in local devices' data, thereby affecting the robustness of the global model. In response, this paper introduces AQUILA (adaptivequantization in device selection strategy), a novel adaptive framework devised to effectively handle these issues, enhancing the efficiency and robustness of FL. AQUILA integrates a sophisticated device selection method that prioritizes the quality and usefulness of device updates. Utilizing the exact global model stored by devices enables a more precise device selection criterion, reduces model deviation, and limits the need for hyperparameter adjustments. Furthermore, AQUILA presents an innovative quantization criterion, optimized to improve communication efficiency while assuring model convergence. Our experiments demonstrate that AQUILA significantly decreases communication costs compared to existing methods, while maintaining comparable model performance across diverse non-homogeneous FL settings, such as Non-IID data and heterogeneous model architectures.

Imitation learning (IL) has been proposed to recover the expert policy from demonstrations. However, it would be difficult to learn a single monolithic policy for highly complex long-horizon tasks of which the expert policy usually contains subtask hierarchies. Therefore, hierarchical IL (HIL) has been developed to learn a hierarchical policy from expert demonstrations through explicitly modeling the activity structure in a task with the option framework. Existing HIL methods either overlook the causal relationship between the subtask structure and the learned policy, or fail to learn the high-level and low-level policy in the hierarchical framework in conjuncture, which leads to suboptimality. In this work, we propose a novel HIL algorithm-hierarchical adversarial inverse reinforcement learning (H-AIRL), which extends a state-of-the-art (SOTA) IL algorithm-AIRL, with the one-step option framework. Specifically, we redefine the AIRL objectives on the extended state and action spaces, and further introduce a directed information term to the objective function to enhance the causality between the low-level policy and its corresponding subtask. Moreover, we propose an expectation-maximization (EM) adaption of our algorithm so that it can be applied to expert demonstrations without the subtask annotations which are more accessible in practice. Theoretical justifications of our algorithm design and evaluations on challenging robotic control tasks are provided to show the superiority of our algorithm compared with SOTA HIL baselines. The codes are available at https://github.com/LucasCJYSDL/HierAIRL.

Robust network design, which aims to guarantee network availability under various failure scenarios while optimizing performance/cost objectives, has received significant attention. Existing approaches often rely on model-based mixed-integer optimization that is hard to scale or employ deep learning to solve specific engineering problems yet with limited generalizability. In this paper, we show that failure evaluation provides a common kernel to improve the tractability and scalability of existing solutions. By providing a neural network function approximation of this common kernel using graph attention networks, we develop a unified learning-based framework, FERN, for scalable Failure Evaluation and Robust Network design. FERN represents rich problem inputs as a graph and captures both local and global views by attentively performing feature extraction from the graph. It enables a broad range of robust network design problems, including robust network validation, network upgrade optimization, and fault-tolerant traffic engineering that are discussed in this paper, to be recasted with respect to the common kernel and thus computed efficiently using neural networks and over a small set of critical failure scenarios. Extensive experiments on real-world network topologies show that FERN can efficiently and accurately identify key failure scenarios for both OSPF and optimal routing scheme, and generalizes well to different topologies and input traffic patterns. It can speed up multiple robust network design problems by more than 80x, 200x, 10x, respectively with negligible performance gap.

In this paper, we propose De-RPOTA, a novel algorithm designed for decentralized learning, equipped with mechanisms for resource adaptation and privacy protection through over-the-air computation. We theoretically analyze the combined effects of limited resources and lossy communication on decentralized learning, showing it converges towards a contraction region defined by a scaled errors version. Remarkably, De-RPOTA achieves a convergence rate of$\mathcal {O}\left ({{\frac {1}{\sqrt {nT}}}}\right)$in scenarios devoid of errors, matching the state-of-the-arts. Additionally, we tackle a power control challenge, breaking it down into transmitter and receiver sub-problems to hasten the De-RPOTA algorithm’s convergence. We also offer a quantifiable privacy assurance for our over-the-air computation methodology. Intriguingly, our findings suggest that network noise can actually strengthen the privacy of aggregated information, with over-the-air computation providing extra security for individual updates. Comprehensive experimental validation confirms De-RPOTA’s efficacy in communication resources limited environments. Specifically, the results on the CIFAR-10 dataset reveal nearly 30% reduction in communication costs compared to the state-of-the-arts, all while maintaining similar levels of learning accuracy, even under resource restrictions.

Multi-Agent Experience Replay (MER) is a key component of off-policy reinforcement learning (RL) algorithms. By remembering and reusing experiences from the past, experience replay significantly improves the stability of RL algorithms and their learning efficiency. In many scenarios, multiple agents interact in a shared environment during online training under centralized training and decentralized execution (CTDE) paradigm. Current multi-agent reinforcement learning (MARL) algorithms consider experience replay with uniform sampling or based on priority weights to improve transition data sample efficiency in the sampling phase. However, moving transition data histories for each agent through the processor memory hierarchy is a performance limiter. Also, as the agents' transitions continuously renew every iteration, the finite cache capacity results in increased cache misses. To this end, we propose AccMER, that repeatedly reuses the transitions (experiences) for a window of$n$steps in order to improve the cache locality and minimize the transition data movement, instead of sampling new transitions at each step. Specifically, our optimization uses priority weights to select the transitions so that only high-priority transitions will be reused frequently, thereby improving the cache performance. Our experimental results on the Predator- Prey environment demonstrate the effectiveness of reusing the essential transitions based on the priority weights, where we observe an end-to-end training time reduction of 25.4% (for 32 agents) compared to existing prioritized MER algorithms without notable degradation in the mean reward.

Bayesian optimization (BO) is a popular global optimization scheme for sample-efficient optimization in domains with expensive function evaluations. The existing BO techniques are capable of finding a single global optimum solution. However, finding a set of global and local optimum solutions is crucial in a wide range of real-world problems, as implementing some of the optimal solutions might not be feasible due to various practical restrictions (e.g., resource limitation, physical constraints, etc.). In such domains, if multiple solutions are known, the implementation can be quickly switched to another solution, and the best possible system performance can still be obtained. This paper develops a multimodal BO framework to effectively find a set of local/global solutions for expensive-to-evaluate multimodal objective functions. We consider the standard BO setting with Gaussian process regression representing the objective function. We analytically derive the joint distribution of the objective function and its first-order derivatives. This joint distribution is used in the body of the BO acquisition functions to search for local optima during the optimization process. We introduce variants of the well-known BO acquisition functions to the multimodal setting and demonstrate the performance of the proposed framework in locating a set of local optimum solutions using multiple optimization problems.

Multi-task Imitation Learning (MIL) aims to train a policy capable of performing a distribution of tasks based on multi-task expert demonstrations, which is essential for general-purpose robots. Existing MIL algorithms suffer from low data efficiency and poor performance on complex long-horizontal tasks. We develop Multi-task Hierarchical Adversarial Inverse Reinforcement Learning (MH-AIRL) to learn hierarchically-structured multi-task policies, which is more beneficial for compositional tasks with long horizons and has higher expert data efficiency through identifying and transferring reusable basic skills across tasks. To realize this, MH-AIRL effectively synthesizes context-based multi-task learning, AIRL (an IL approach), and hierarchical policy learning. Further, MH-AIRL can be adopted to demonstrations without the task or skill annotations (i.e., state-action pairs only) which are more accessible in practice. Theoretical justifications are provided for each module of MH-AIRL, and evaluations on challenging multi-task settings demonstrate superior performance and transferability of the multi-task policies learned with MH-AIRL as compared to SOTA MIL baselines.

Hierarchical Imitation Learning (HIL) has been proposed to recover highly-complex behaviors in long-horizon tasks from expert demonstrations by modeling the task hierarchy with the option framework. Existing methods either overlook the causal relationship between the subtask and its corresponding policy or cannot learn the policy in an end-to-end fashion, which leads to suboptimality. In this work, we develop a novel HIL algorithm based on Adversarial Inverse Reinforcement Learning and adapt it with the Expectation-Maximization algorithm in order to directly recover a hierarchical policy from the unannotated demonstrations. Further, we introduce a directed information term to the objective function to enhance the causality and propose a Variational Autoencoder framework for learning with our objectives in an end-to-end fashion. Theoretical justifications and evaluations on challenging robotic control tasks are provided to show the superiority of our algorithm. The codes are available at https://github.com/LucasCJYSDL/HierAIRL.

In this paper, we propose an adaptive learning paradigm for resource-constrained cross-device federated learning, in which heterogeneous local submodels with varying resources can be jointly trained to produce a global model. Different from existing studies, the submodel structures of different clients are formed by arbitrarily assigned neurons according to their local resources. Along this line, we first design a general resource-adaptive federated learning algorithm, namely RA-Fed, and rigorously prove its convergence with asymptotically optimal rate O(1/√Γ*TQ) under loose assumptions. Furthermore, to address both submodels heterogeneity and data heterogeneity challenges under non-uniform training, we come up with a new server aggregation mechanism RAM-Fed with the same theoretically proved convergence rate. Moreover, we shed light on several key factors impacting convergence, such as minimum coverage rate, data heterogeneity level, submodel induced noises. Finally, we conduct extensive experiments on two types of tasks with three widely used datasets under different experimental settings. Compared with the state-of-the-arts, our methods improve the accuracy up to 10% on average. Particularly, when submodels jointly train with 50% parameters, RAM-Fed achieves comparable accuracy to FedAvg trained with the full model.

Optimizing distributional utilities (such as mitigating performance tails and maximizing risk-aware objectives) is crucial for online network slice management to meet the diverse requirements of different services and applications. While Reinforcement Learning (RL) has been successfully applied to autonomous online decision-making in many network slice management problems, existing solutions often focus on maximizing the expected cumulative reward or are limited to specific distributional utilities. This paper proposes a new RL algorithm for general Distributional Utilities Optimization (DUO) in an actor-critic framework for online network slice management. In particular, we derive a DUO Temporal Difference Learning algorithm for updating distributional utilities in the critic through stochastic gradient descent. It is proven that the Distributional Optimal Bellman Operator for distributional utilities is a γ-contraction and thus is guaranteed to converge. In addition, we parameterize the policy by another neural network and prove a revised policy gradient theorem for distributional utilities, which shows that the derived policy update converges to at least a stationary point of the DUO problem. Our proposed algorithm works with arbitrary smooth utility functions on the return distributions, making it suitable for optimizing various network slice performance objectives in an online setting. Our solution is implemented and validated by building a hybrid trace-driven network simulator, which was built using an open-source O-RAN dataset, along with data collected from a 5G O-RAN testbed. Results demonstrate a significant improvement over heuristic and RL baselines.

In this paper, we propose a novel decentralized learning algorithm, namely DLLR-OA, for resource-constrained over-the-air computation with formal privacy guarantee. Theoretically, we characterize how the limited resources induced model-components selection error and compound communication errors jointly impact decentralized learning, making the iterates of DLLR-OA converge to a contraction region centered around a scaled version of the errors. In particular, the convergence rate of the DLLR-OA algorithm in the error-free case [EQUATION] achieves the state-of-the-arts. Besides, we formulate a power control problem and decouple it into two sub-problems of transmitter and receiver to accelerate the convergence of the DLLR-OA algorithm. Furthermore, we provide quantitative privacy guarantee for the proposed over-the-air computation approach. Interestingly, we show that network noise can indeed enhance privacy of aggregated updates while over-the-air computation can further protect individual updates. Finally, the extensive experiments demonstrate that DLLR-OA performs well in the communication resources constrained setting. In particular, numerical results on CIFAR-10 dataset shows nearly 30% communication cost reduction over state-of-the-art baselines with comparable learning accuracy even in resource constrained settings.

Learning rich skills under the option framework without supervision of external rewards is at the frontier of reinforcement learning research. Existing works mainly fall into two distinctive categories: variational option discovery that maximizes the diversity of the options through a mutual information loss (while ignoring coverage) and Laplacian-based methods that focus on improving the coverage of options by increasing connectivity of the state space (while ignoring diversity). In this paper, we show that diversity and coverage in unsupervised option discovery can indeed be unified under the same mathematical framework. To be specific, we explicitly quantify the diversity and coverage of the learned options through a novel use of Determinantal Point Process (DPP) and optimize these objectives to discover options with both superior diversity and coverage. Our proposed algorithm, ODPP, has undergone extensive evaluation on challenging tasks created with Mujoco and Atari. The results demonstrate that our algorithm outperforms state-of-the-art baselines in both diversity- and coverage-driven categories.

Cross-device Federated Learning (FL) faces significant challenges where low-end clients that could potentially make unique contributions are excluded from training large models due to their resource bottlenecks. Recent research efforts have focused on model-heterogeneous FL, by extracting reduced-size models from the global model and applying them to local clients accordingly. Despite the empirical success, general theoretical guarantees of convergence on this method remain an open question. This paper presents a unifying framework for heterogeneous FL algorithms with online model extraction and provides a general convergence analysis for the first time. In particular, we prove that under certain sufficient conditions and for both IID and non-IID data, these algorithms converge to a stationary point of standard FL for general smooth cost functions. Moreover, we introduce the concept of minimum coverage index, together with model reduction noise, which will determine the convergence of heterogeneous federated learning, and therefore we advocate for a holistic approach that considers both factors to enhance the efficiency of heterogeneous federated learning.

Inter-DataCenter Wide Area Network (Inter-DC WAN) that connects geographically distributed data centers is becoming one of the most critical network infrastructures. Due to limited bandwidth and inevitable link failures, it is highly challenging to guarantee network availability for services, especially those with stringent bandwidth demands, over inter-DC WAN. We present$\mathsf {TEDAT}$, a novel Traffic Engineering (TE) framework for Diverse Availability Targets (DAT), where a Service Level Agreement (SLA) is defined to ensure that each bandwidth demand must be satisfied with a stipulated probability, when subjected to the network capacity and possible failures of the inter-DC WAN.$\mathsf {TEDAT}$has two core components, i.e., traffic scheduling and failure recovery, which are crystalized through different mathematical models and theoretically analyzed. They are also extensively compared against state-of-the-art TE schemes, using a testbed as well as real trace driven simulations across different topologies, traffic matrices and failure scenarios. Our evaluations show that, compared with the optimal admission strategy,$\mathsf {TEDAT}$can speed up the online admission control by$30\times $at the expense of less than 4% false rejections. On the other hand, compared with the latest TE schemes like FFC and TEAVAR,$\mathsf {TEDAT}$can meet the bandwidth availability SLAs for 23%~60% more demands under normal loads, and when network failure causes SLA violations, it can retain 10%~20% more profit under a pricing and refunding model.

Gradient-based training in federated learning is known to be vulnerable to faulty/malicious clients, which are often modeled as Byzantine clients. To this end, previous work either makes use of auxiliary data at parameter server to verify the received gradients (e.g., by computing validation error rate) or leverages statistic-based methods (e.g. median and Krum) to identify and remove malicious gradients from Byzantine clients. In this paper, we remark that auxiliary data may not always be available in practice and focus on the statistic-based approach. However, recent work on model poisoning attacks has shown that well-crafted attacks can circumvent most of median- and distance-based statistical defense methods, making malicious gradients indistinguishable from honest ones. To tackle this challenge, we show that the element-wise sign of gradient vector can provide valuable insight in detecting model poisoning attacks. Based on our theoretical analysis of the Little is Enough attack, we propose a novel approach called SignGuard to enable Byzantine-robust federated learning through collaborative malicious gradient filtering. More precisely, the received gradients are first processed to generate relevant magnitude, sign, and similarity statistics, which are then collaboratively utilized by multiple filters to eliminate malicious gradients before final aggregation. Finally, extensive experiments of image and text classification tasks are conducted under recently proposed attacks and defense strategies. The numerical results demonstrate the effectiveness and superiority of our proposed approach.

Covering option discovery has been developed to improve the exploration of RL in single-agent scenarios with sparse reward signals, through connecting the most distant states in the embedding space provided by the Fiedler vector of the state transition graph. Given that joint state space grows exponentially with the number of agents in multi-agent systems, existing researches still relying on single-agent option discovery either become prohibitive or fail to directly discover joint options that improve the connectivity of the joint state space. In this paper, we show how to directly compute multi-agent options with collaborative exploratory behaviors while still enjoying the ease of decomposition. Our key idea is to approximate the joint state space as a Kronecker graph, based on which we can directly estimate its Fiedler vector using the Laplacian spectrum of individual agents' transition graphs. Further, considering that directly computing the Laplacian spectrum is intractable for tasks with infinite-scale state spaces, we further propose a deep learning extension of our method by estimating eigenfunctions through NN-based representation learning techniques. The evaluation on multi-agent tasks built with simulators like Mujoco, shows that the proposed algorithm can successfully identify multi-agent options, and significantly outperforms the state-of-the-art. Codes are available at: https://github.itap.purdue.edu/Clan-labs/ScalableMAODvia_KP.

Multi-agent reinforcement learning (MARL) has witnessed significant progress with the development of value function factorization methods. It allows optimizing a joint action-value function through the maximization of factorized per-agent utilities. In this paper, we show that in partially observable MARL problems, an agent's ordering over its own actions could impose concurrent constraints (across different states) on the representable function class, causing significant estimation errors during training. We tackle this limitation and propose PAC, a new framework leveraging Assistive information generated from Counterfactual Predictions of optimal joint action selection, which enable explicit assistance to value function factorization through a novel counterfactual loss. A variational inference-based information encoding method is developed to collect and encode the counterfactual predictions from an estimated baseline. To enable decentralized execution, we also derive factorized per-agent policies inspired by a maximum-entropy MARL framework. We evaluate the proposed PAC on multi-agent predator-prey and a set of StarCraft II micromanagement tasks. Empirical results demonstrate improved results of PAC over state-of-the-art value-based and policy-based multi-agent reinforcement learning algorithms on all benchmarks.

Gradient compression (e.g., gradient quantization and gradient sparsification) is a core technique in reducing communication costs in distributed learning systems. The recent trend of gradient compression is to use a varying number of bits across iterations, however, relying on empirical observations or engineering heuristics without a systematic treatment and analysis. To the best of our knowledge, a general dynamic gradient compression that leverages both quantization and sparsification techniques is still far from understanding. This paper proposes a novel Adaptively-Compressed Stochastic Gradient Descent (AC-SGD) strategy to adjust the number of quantization bits and the sparsification size with respect to the norm of gradients, the communication budget, and the remaining number of iterations. In particular, we derive an upper bound, tight in some cases, of the convergence error for arbitrary dynamic compression strategy. Then we consider communication budget constraints and propose an optimization formulation - denoted as theAdaptive Compression Problem (ACP)- for minimizing the deep model’s convergence error under such constraints. By solving the ACP, we obtain an enhanced compression algorithm that significantly improves model accuracy under given communication budget constraints. Finally, through extensive experiments on computer vision and natural language processing tasks on MNIST, CIFAR-10, CIFAR-100 and AG-News datasets, respectively, we demonstrate that our compression scheme significantly outperforms the state-of-the-art gradient compression methods in terms of mitigating communication costs.

Federated learning (FL) has attracted tremendous attentions in recent years due to its privacy-preserving measures and great potential in some distributed but privacy-sensitive applications, such as finance and health. However, high communication overloads for transmitting high-dimensional networks and extra security masks remain a bottleneck of FL. This article proposes a communication-efficient FL framework with an Adaptive Quantized Gradient (AQG), which adaptively adjusts the quantization level based on a local gradient’s update to fully utilize the heterogeneity of local data distribution for reducing unnecessary transmissions. In addition, client dropout issues are taken into account and an Augmented AQG is developed, which could limit the dropout noise with an appropriate amplification mechanism for transmitted gradients. Theoretical analysis and experiment results show that the proposed AQG leads to 18% to 50% of additional transmission reduction as compared with existing popular methods, including Quantized Gradient Descent (QGD) and Lazily Aggregated Quantized (LAQ) gradient-based methods without deteriorating convergence properties. Experiments with heterogenous data distributions corroborate a more significant transmission reduction compared with independent identical data distributions. The proposed AQG is robust to a client dropping rate up to 90% empirically, and the Augmented AQG manages to further improve the FL system’s communication efficiency with the presence of moderate-scale client dropouts commonly seen in practical FL scenarios.

Inter-DataCenter Wide Area Network (Inter-DC WAN) that connects geographically distributed data centers is becoming one of the most critical network infrastructures. Due to limited bandwidth and inevitable link failures, it is highly challenging to guarantee network availability for services, especially those with stringent bandwidth demands, over inter-DC WAN. We present BATE, a novel Traffic Engineering (TE) framework for bandwidth availability (BA) provision, which aims to ensure that each bandwidth demand must be satisfied with a stipulated probability, when subjected to the network capacity and possible failures of the inter-DC WAN. The three core components of BATE, i.e., admission control, traffic scheduling and failure recovery, are formulated through different mathematical models and theoretically analyzed. They are also extensively compared against state-of-the-art TE schemes, using a testbed as well as real trace driven simulations across different topologies, traffic matrices and failure scenarios. Our evaluations show that, compared with the optimal admission strategy, BATE can speed up the online admission control by 30x at the expense of less than 4% false rejections. On the other hand, compared with the latest TE schemes like FFC and TEAVAR, BATE can meet the bandwidth availability targets for 23%~60% more demands under normal loads, and when network failure causes BA targets violations.

Fairness is a crucial design objective in virtually all network optimization problems, where limited system resources are shared by multiple agents. Recently, reinforcement learning has been successfully applied to autonomous online decision making in many network design and optimization problems. However, most of them try to maximize the long-term (discounted) reward of all agents, without taking fairness into account. In this paper, we propose a family of algorithms that bring fairness to actor-critic reinforcement learning for optimizing general fairness utility functions. In particular, we present a novel method for adjusting the rewards in standard reinforcement learning by a multiplicative weight depending on both the shape of fairness utility and some statistics of past rewards. It is shown that for proper choice of the adjusted rewards, a policy gradient update converges to at least a stationary point of general αfairness utility optimization. It inspires the design of fairness optimization algorithms in actor-critic reinforcement learning. Evaluations show that the proposed algorithm can be easily deployed in real-world network optimization problems, such as wireless scheduling and video QoE optimization, and can significantly improve the fairness utility value over previous heuristics and learning algorithms.

The training efficiency of distributed learning systems is vulnerable to stragglers, namely, those slow worker nodes. A naive strategy is performing the distributed learning by incor-porating the fastest K workers and ignoring these stragglers, which may induce high deviation for non-IID data. To tackle this, we develop a Live Gradient Compensation (LGC) strategy to incorporate the one-step delayed gradients from stragglers, aiming to accelerate learning process and utilize the stragglers simultaneously. In LGC framework, mini-batch data are divided into smaller blocks and processed separately, which makes the gradient computed based on partial work accessible. In addition, we provide theoretical convergence analysis of our algorithm for non-convex optimization problem under non-IID training data to show that LGC-SGD has almost the same convergence error as full synchronous SGD. The theoretical results also allow us to quantify a novel tradeoff in minimizing training time and error by selecting the optimal straggler threshold. Finally, extensive simulation experiments of image classification on CIFAR-10 dataset are conducted, and the numerical results demonstrate the effectiveness of our proposed strategy.

Gradient quantization is an emerging technique in reducing communication costs in distributed learning. Existing gradient quantization algorithms often rely on engineering heuristics or empirical observations, lacking a systematic approach to dynamically quantize gradients. This paper addresses this issue by proposing a novel dynamically quantized SGD (DQ-SGD) framework, enabling us to dynamically adjust the quantization scheme for each gradient descent step by exploring the trade-off between communication cost and convergence error. We derive an upper bound, tight in some cases, of the convergence error for a restricted family of quantization schemes and loss functions. We design our DQSGD algorithm via minimizing the communication cost under the convergence error constraints. Finally, through extensive experiments on large-scale natural language processing and computer vision tasks on AG-News, CFAR-10, and CIFAR-100 datasets, we demonstrate that our quantization scheme achieves better tradeoffs between the communication cost and learning performance than other state-of-the-art gradient quantization methods.

A combination of mobile edge computing (MEC) and cloud computing paradigms has the potential to greatly alleviate the challenges facing Internet of Things (IoT). We consider a tiered IoT infrastructure in which data generated by an IoT sensor/device is delivered to a data center for processing through an intermediate MEC server. The MEC server can either directly transmit the data to the data center or pre-process the data and then transmit it to the data center over a shared channel. The goal is to maintain the freshness of the data delivered to the data center. In this paper, we assume a probabilistic model for pre-processing by the MEC server. Sensor data is assumed to be generated as a Poisson process and the transmission times over the two paths are assumed to have general distributions.We use Age of Information (AoI) as a measure of data freshness at the data center. We perform stationary distribution analysis in this system and obtain closed form expressions for average AoI and average peak AoI. We focus on selecting the offloading probabilities in conjunction with the mean service times for each server for optimal operation determined by average AoI and peak AoI. Our numerical results show the effect of path diversity in the selection of best offloading probability and service times.

Traffic for internet video streaming has been rapidly increasing and is further expected to increase with the higher definition videos and IoT applications, such as 360 degree videos and augmented virtual reality applications. While efficient management of heterogeneous cloud resources to optimize the quality of experience is important, existing work in this problem space often left out important factors. In this paper, we present a model for describing a today’s representative system architecture for video streaming applications, typically composed of a centralized origin server and several CDN sites. Our model comprehensively considers the following factors: limited caching spaces at the CDN sites, allocation of CDN for a video request, choice of different ports from the CDN, and the central storage and bandwidth allocation. With the model, we focus on minimizing a performance metric, stall duration tail probability (SDTP), and present a novel, yet efficient, algorithm to solve the formulated optimization problem. The theoretical bounds with respect to the SDTP metric are also analyzed and presented. Our extensive simulation results demonstrate that the proposed algorithms can significantly improve the SDTP metric, compared to the baseline strategies. Small-scale video streaming system implementation in a real cloud environment further validates our results.

Distributed computing systems often need to consider the scheduling problem involving a collection of highly dependent data-processing tasks that must work in concert to achieve mission-critical objectives. This paper considers the unrelated machine scheduling problem for minimizing weighted sum completion time under arbitrary precedence constraints and on heterogeneous machines with different processing speeds. The problem is known to be strongly NP-hard even in the single machine setting. By making use of Queyranne’s constraint set and constructing a novel Linear Programming relaxation for the scheduling problem under arbitrary precedence constraints, our results in this paper advance the state of the art. We develop a 2(1+(m-1)/D)-approximation algorithm (and 2(1+(m-1)/D)+1-approximation) for the scheduling problem with zero release time (and arbitrary release time), where m is the number of servers and D is the task-skewness product. The algorithm can be efficiently computed in polynomial time using the Ellipsoid method and achieves nearly optimal performance in practice as D>O(m) when the number of tasks per job to schedule is sufficiently larger than the number of machines available. Our implementation and evaluation using a heterogeneous testbed and real-world benchmarks confirms significant improvement in weighted sum completion time for dependent computing tasks.

A datacenter that consists of hundreds or thousands of servers can provide virtualized environments to a large number of cloud applications and jobs that value the requirement of reliability very differently. Checkpointing a virtual machine (VM) is a proven technique to improve reliability. However, existing checkpoint scheduling techniques for enhancing reliability of distributed systems fails to achieve satisfactory results, either because they tend to offer the same, fixed reliability to all jobs, or because their solutions are tied up to specific applications and rely on centralized checkpoint control mechanisms. In this work, we first show that reliability can be significantly improved through contention-free scheduling of checkpoints. Then, inspired by the Carrier Sense Multiple Access (CSMA) protocol in wireless congestion control, we propose a novel framework for distributed and contention-free scheduling of VM checkpointing to provide reliability as a transparent, elastic service. We quantify reliability in closed form by studying system stationary behaviours, and maximize job reliability through utility optimization. Our design is validated via a proof-of-concept prototype that leverages readily available implementations in Xen hypervisors. The proposed checkpoint scheduling is shown to significantly reduce checkpointing interference and improve reliability by as much as one order of magnitude over contention-oblivious checkpoint schemes.

Traffic engineering (TE) in multi-region networks is a challenging problem due to the requirement that each region must independently compute its routing decisions based on local observations, yet with the goal of optimizing global TE objectives. Traditional approaches often lack the agility to adapt to changing traffic patterns and thus may suffer hefty performance loss under highly dynamic traffic demands. In this paper, we propose a data-driven framework for multi-region TE problems, which makes novel use of multi-agent deep reinforcement learning. In particular, we propose two reinforcement learning agents for each region, namely T-agents and O-agents, to control the terminal traffic and outgoing traffic, respectively. These distributed agents collect local link utilization statistics within their regions, optimize local routing decisions, and observe the resulting congestion-related reward. To facilitate these agents for optimizing global TE objectives, we tailor the agent design carefully including input, output, and reward functions. The proposed framework is evaluated extensively using real-world network topologies (e.g., Telstra and Google Cloud) and synthetic traffic patterns (e.g., the Gravity model). Numerical results show that comparing with existing protocols and single-agent learning algorithms, our solution can significantly reduce congestion and achieve nearly-optimal performance with both superior scalability and robustness. Throughout our simulations, over 90% of tests limit congestion within 1.2 times the global optimal solution.

The rapid growth of computing capabilities at network edge calls for efficient management frameworks that not only considers placing hot data on edge storage for best accessibility and performance, but also makes optimal utilization of edge storage space. In this paper, we solve a joint optimization problem by exploiting both data popularity (for optimal data access performance) and data similarity (for optimal storage space efficiency). We show that the proposed optimization is NP- hard and develop a 2⌈2Γ⌉ - 1 + ϵ-approximation algorithm by (i) making novel use of δ-similarity graph to capture pairwise data similarity and (ii) leveraging the k-MST algorithm to solve a Prize Collecting Steiner Tree problem on the graph. The proposed algorithm is prototyped using an open-source distributed storage system, Cassandra. We evaluate its performance extensively on a real-world testbed and with respect to real-world IoT datasets. The algorithm is shown to achieve over 55% higher edge service rate and reduces request response time by about 30%.

Unsafe memory accesses in programs written using popular programming languages like C/C++ have been among the leading causes for software vulnerability. Prior memory safety checkers such as SoftBound enforce memory spatial safety by checking if every access to array elements are within the corresponding array bounds. However, it often results in high execution time overhead due to the cost of executing the instructions associated with bounds checking. To mitigate this problem, redundant bounds check elimination techniques are needed. In this paper, we propose CHOP, a Convex Hull Optimization based framework, for bypassing redundant memory bounds checking via profile-guided inferences. In contrast to existing check elimination techniques that are limited by static code analysis, our solution leverages a model-based inference to identify redundant bounds checking based on runtime data from past program executions. For a given function, it rapidly derives and updates a knowledge base containing sufficient conditions for identifying redundant array bounds checking. We evaluate CHOP on real-world applications and benchmark (such as SPEC) and the experimental results show that on average 80.12% of dynamic bounds check instructions can be avoided, resulting in improved performance up to 95.80% over SoftBound.

With the growing deadline-sensitivity of cloud applications, adherence to specific deadlines is becoming increasingly crucial, particularly in shared clusters. A few slow tasks called stragglers can potentially adversely affect job execution times. Equally, inadequate slotting of data analytics applications could result in inappropriate resource deployment, ultimately damaging system performance. Against this backdrop, one effective way of tackling stragglers is by making extra attempts (or clones)1 for every single straggler after the submission of a job. This paper proposes Shed+, which is an optimization framework utilizing dynamic speculation that aims to maximize the jobs' PoCD (Probability of Completion before Deadline) by making full use of available resources. Notably, our work encompasses a new online scheduler that dynamically recomputes and reallocates resources during the course of a job's execution. According to our findings, Shed+ successfully leverages cloud resources and maximizes the percentage of jobs meeting their deadlines. In our experiments, we have seen this percentage for heavy load going up to 98% for Shed+ as opposed to nearly 68%, 40%, 35% and 37% for Shed, Dolly, Hopper and Hadoop with speculation enabled, respectively.

The advent of IoT and edge computing will lead to massive amounts of data that need to be collected and transmitted to online storage systems. To address this problem, we push data deduplication to the network edge. Specifically, we propose a new technique for collaborative edge-facilitated deduplication (EF-dedup), wherein we partition the resource-constrained edge nodes into disjoint clusters, maintain a deduplication index structure for each cluster using a distributed key-value store and perform decentralized deduplication within those clusters. This is a challenging partitioning problem that addresses a novel tradeoff: edge nodes with highly correlated data may not always be within the same edge cloud, with non-trivial network cost among them. We address this challenge by first formulating an optimization problem to partition the edge nodes, considering both the data similarities across the nodes and the inter-node network cost. We prove that the problem is NP-Hard, provide bounded heuristics to solve it and build a prototype EF-dedup system. Our experiments on EF-dedup, performed on edge nodes in AT&T research lab and a central cloud at AWS, demonstrate that EF-dedup achieves 38.3-118.5% better deduplication throughput than sole cloud-based techniques and achieves 43.4-60.2% lesser aggregate cost in terms of the network-storage tradeoff as compared to approaches that solely favor one over the other.

We consider the problem of optimally mapping an edge computing service that is modeled as a tree with multiple processing sub-tasks and data flows onto the underlying physical network. As new computing and data analytics applications require more complicated data processing structures, and different types of data (e.g., images, videos, and numbers) sensed at geographically distributed locations must be collected and processed to obtain a complex and comprehensive result, highly intelligent algorithms are needed to solve this challenging problem. In this paper, we propose a learning-based hierarchical service tree placement strategy that aims to optimize the net utility, defined as achieved utility minus network congestion. The key idea is to decouple a service tree into appropriate sub-trees each containing a single computing sub-task as well as associated data flows and to recursively leverage Q-learning to place each sub-tree while maintaining the dependencies of sub-tasks in the service tree structure. It enables a scalable solution for large networks with unknown arrival statistics and complex service structures. Numerical results show that our solution can significantly outperform baseline heuristics in online service tree placement.

This paper proposes an algorithm to minimize weighted service latency for different classes of tenants (or service classes) in a data center network where erasure-coded files are stored on distributed disks/racks and access requests are scattered across the network. Due to the limited bandwidth available at both top-of-the-rack and aggregation switches, and differentiated service requirements of the tenants, network bandwidth must be apportioned among different intra- and inter-rack data flows for different service classes in line with their traffic statistics. We formulate this problem as weighted queuing and employ a class of probabilistic request scheduling policies to derive a closed-form upper-bound of service latency for erasure-coded storage with arbitrary file access patterns and service time distributions. The result enables us to propose a joint weighted latency (over different service classes) optimization over three entangled “control knobs”: the bandwidth allocation at top-of-the-rack and aggregation switches for different service classes, dynamic scheduling of file requests, and the placement of encoded file chunks (i.e., data locality). The joint optimization is shown to be a mixed-integer problem. We develop an iterative algorithm which decouples and solves the joint optimization as 3 sub-problems, which are either convex or solvable via bipartite matching in polynomial time. The proposed algorithm is prototyped in an open-source, distributed file system, Tahoe, and evaluated on a cloud testbed with 16 separate physical hosts in an OpenStack cluster using Cisco switches. Experiments validate our theoretical latency analysis and show significant latency reduction for diverse file access patterns. The results provide valuable insights on designing low-latency data center networks with erasure coded storage.

Accurately determining the network energy consumption of each software principal when multiple ones are active is the key to mobile energy optimization. Tail energy accounting, which attributes tail energy to individual software principals, remains an open problem. Besides, tail energy has also become a major energy drain, especially in mobile ad modules that generate frequent, intermittent network traffics by on-demand ad downloading. In this paper, we propose a systematic framework for mobile ad prefetching and energy optimization, based on a novel tail energy accounting policy using cooperative game theory. In particular, we maximize the sum of deadline- and energy-aware ad utility, by jointly determining apps' aggressiveness in ad prefetching. The proposed tail energy accounting not only characterizes the energy profile of each app's ad module, a crucial input in energy optimization, but also enables an efficient solution by decoupling decision making of individual apps. The proposed framework is implemented on Android with negligible performance/network overhead. Using real-world apps and usage traces, we demonstrate a significant reduction in mobile network energy consumption by up to 45 percent compared with existing approaches. To the best of our knowledge, it is the first fully implemented ad management system transparent to apps and ad ecosystem.

Distributed storage systems are known to be susceptible to long tails in response time. In modern online storage systems such as Bing, Facebook, and Amazon, the long tails of the service latency are of particular concern, with 99.9th percentile response times being orders of magnitude worse than the mean. As erasure codes emerge as a popular technique to achieve high data reliability in distributed storage while attaining space efficiency, taming tail latency still remains an open problem due to the lack of mathematical models for analyzing such systems. To this end, we propose a framework for quantifying and optimizing tail latency in erasure-coded storage systems. In particular, we derive upper bounds on tail latency in closed-form for arbitrary service time distribution and heterogeneous files. Based on the model, we formulate an optimization problem to jointly minimize weighted latency tail probability of all files over the placement of files on the servers, and the choice of servers to access the requested files. The non-convex problem is solved using an efficient, alternating optimization algorithm. Further, we mathematically quantify, in closed form, the tail index, i.e., the exponent at which latency tail probability diminishes to zero, of the service latency for arbitrary erasure-coded storage, by characterizing the asymptotic behavior of latency distribution tails. We further show that probabilistic scheduling-based algorithms are (asymptotically) optimal since they are able to achieve the exact tail index. Evaluation results show significant reduction of tail latency for erasure-coded storage systems with realistic workload. Based on the offline algorithm, an online version is developed and its superiority over the state-of-the-art algorithms, e.g., join-shortest-queue (JSQ), power-of-d [Pof(d))], least-load [LL(d)], is shown. Finally, a cloud storage system is implemented in a real cloud environment to show the superiority of our approach as compared to the considered baselines.

In cloud storage, the digital data is stored in logical storage pools, backed by heterogeneous physical storage media and computing infrastructure that are managed by a cloud service provider (CSP). One of the key advantages of cloud storage is its elastic pricing mechanism, in which the users need only pay for the resources/services they actually use, e.g., depending on the storage capacity consumed, the number of file accesses per month, and the negotiated service level agreement. To balance the tradeoff between service performance and cost, CSPs often employ different storage tiers, for instance, cold storage and hot storage. Storing data in hot storage incurs high storage cost yet delivers low access latency, whereas cold storage is able to inexpensively store massive amounts of data and thus provides lower cost with higher latency. In this paper, we address a major challenge confronting the CSPs utilizing such tiered storage architecture-how to maximize their overall profit over a variety of storage tiers that offer distinct characteristics, as well as file placement and access request scheduling policies. To this end, we propose a scheme where the CSP offers a two-stage auction process for: 1) requesting storage capacity and 2) requesting accesses with latency requirements. Our two-stage bidding scheme provides a hybrid storage and access optimization framework with the objective of maximizing the CSP's total net profit over four dimensions: file acceptance decision, placement of accepted files, file access decision and access request scheduling policy. The proposed optimization is a mixed-integer nonlinear program that is hard to solve. We propose an efficient heuristic to relax the integer optimization and to solve the resulting nonlinear stochastic programs. The algorithm is evaluated under different scenarios and with different storage system parameters, and insightful numerical results are reported by comparing the proposed approach with other profit-maximization models. We see a profit increase of over 60% of our proposed method compared to other baseline algorithms in certain simulation scenarios.

The ongoing expansion and addition of new features in software development bring inefficiency and vulnerabilities into programs, resulting in an increased attack surface with higher possibility of exploitation. Creating customized software systems that contain just-enough features and yet satisfy specific user needs is currently an extremely slow, build-to-order process. In this paper, we propose MORPH, an Interactive Program Feature Customization framework to provide broad capabilities for automated program feature identification and feature customization. Our preliminary results show that MORPH can identify program features at an average accuracy of 92.7% and swiftly generate variations of self-contained, customized programs in an unsupervised fashion.

Mobile Edge Computing has quickly become a promising paradigm to meet the ever-increasing data-processing demands imposed by emerging applications, by shifting computations to network edge. In this paper, we address two problems unique in edge computing: How to determine the execution cost contributed by each computing task in an edge environment, and how to distributively assign tasks to heterogeneous edge nodes to minimize total execution cost? Cost accounting is a long-standing hard problem for multiprocessing systems, e.g., when edge nodes jointly process tasks from different users. We propose a new framework that models the problem as a multichoice cooperative game, and use Shapley Value for cost accounting. The result enables us to decouple the cost of concurrent task executions and to efficiently solve the task assignment problem through a distributive Hungarian algorithm. To evaluate the performance, we conduct hybrid experiments by collecting trace from a fully implemented edge testbed and generating cost profiles to drive extensive simulations. Numerical results show that our solution guided by multichoice Shapley value is able to consistently outperform two baseline strategies using oblivious cost accounting policies, for task assignment in heterogeneous edge networks. Our solution's advantages become more significant for edge networks with higher levels of heterogeneity (either computation- or network-wise).

As cloud applications are becoming increasingly deadline-sensitive, meeting desired deadlines is more critical, especially in shared clusters. It has been shown that a few slow tasks, called stragglers, could significantly adversely impact job execution times. Moreover, poor scheduling of data analytics applications can lead to inefficient resource usage, and eventually hurt system performance. One way to mitigate stragglers is by launching extra attempts (clones) for each task upon job submission. In this paper, we propose Shed, an optimization framework that leverages dynamic cloning to jointly maximize jobs' Probability of Completion before Deadline (PoCD) by fully utilizing the available resources. Our work includes a novel online scheduler that dynamically recomputes and reallocates resources during a job's execution for PoCD maximization. The results show that Shed is able to leverage cloud resources and maximize the percentage of jobs that meet their deadlines - up to 100% in our experiments compared to typically around 60% and 40% for another cloning approach called Dolly, and Hadoop with speculation enabled, respectively.

Meeting desired application deadlines in cloud processing systems such as MapReduce is crucial as the nature of cloud applications is becoming increasingly mission-critical and deadline-sensitive. It has been shown that the execution times of MapReduce jobs are often adversely impacted by a few slow tasks, known as stragglers, which result in high latency and deadline violations. While a number of strategies have been developed in existing work to mitigate stragglers by launching speculative or clone task attempts, none of them provide a quantitative framework that optimizes the speculative execution for offering guaranteed Service Level Agreements (SLAs) to meet application deadlines. In this paper, we bring several speculative scheduling strategies together under a unifying optimization framework, called Chronos, which defines a new metric, Probability of Completion before Deadlines (PoCD), to measure the probability that MapReduce jobs meet their desired deadlines. We systematically analyze PoCD for popular strategies including Clone, Speculative-Restart, and Speculative-Resume, and quantify their PoCD in closed-form. The results illuminate an important tradeoff between PoCD and the cost of speculative execution, measured by the total (virtual) machine time required under different strategies. We propose an optimization problem to jointly optimize PoCD and execution cost in different strategies, and develop an algorithmic solution that is guaranteed to be optimal. Chronos is prototyped on Hadoop MapReduce and evaluated against three baseline strategies using both experiments and trace-driven simulations, and achieves 50% net utility increase with up to 80% PoCD and 88% cost improvements.

Erasure-coded storage systems have gained considerable adoption recently since they can provide the same level of reliability with significantly lower storage overhead compared to replicated systems. However, background traffic of such systems – e.g., repair, rebalance, backup and recovery traffic – often has large volume and consumes significant network resources. Independently scheduling such tasks and selecting their sources can easily create interference among data flows, causing severe deadline violation. We show that the well-known heuristic scheduling algorithms fail to consider important constraints, thus resulting in unsatisfactory performance. In this paper, we claim that an optimal scheduling algorithm, which aims to maximize the number of background tasks completed before deadlines, must simultaneously consider task deadline, network topology, chunk placement, and time-varying resource availability. We first show that the corresponding optimization problem is NP-hard. Then we propose a novel algorithm, called Linear Programming for Selected Tasks (LPST) to maximize the number of successful tasks and improve overall utilization of the datacenter network. It jointly schedules tasks and selects their sources based on a notion of Remaining Time Flexibility, which measures the slackness of the starting time of a task. We evaluated the efficacy of our algorithm using extensive simulations and validate the results with experiments in a real cloud environment. Our results show that, under certain scenarios, LPST can perform 7x$\sim$10x better than the heuristics which blindly treat the infrastructure as a collection of homogeneous resources, and 21.7$\sim$65.9 percent better than the algorithms that only take the network topology into account.

Identifying vulnerabilities in software systems is crucial to minimizing the damages that result from malicious exploits and software failures. This often requires proper identification of vulnerable execution paths that contain program vulnerabilities or bugs. However, with rapid rise in software complexity, it has become notoriously difficult to identify such vulnerable paths through exhaustively searching the entire program execution space. In this paper, we propose StatSym, a novel, automated Statistics-Guided Symbolic Execution framework that integrates the swiftness of statistical inference and the rigorousness of symbolic execution techniques to achieve precision, agility and scalability in vulnerable program path discovery. Our solution first leverages statistical analysis of program runtime information to construct predicates that are indicative of potential vulnerability in programs. These statistically identified paths, along with the associated predicates, effectively drive a symbolic execution engine to verify the presence of vulnerable paths and reduce their time to solution. We evaluate StatSym on four real-world applications including polymorph, CTree, Grep and thttpd that come from diverse domains. Results show that StatSym is able to assist the symbolic executor, KLEE, in identifying the vulnerable paths for all of the four cases, whereas pure symbolic execution fails in three out of four applications due to memory space overrun.

With the proliferation of the Internet of Things (IoT), the current "cloud-only" architectures cannot efficiently handle IoT's data processing and communications needs, while providing satisfactory service latency to support emerging mobile applications on the horizon that require almost real-time responses. fog computing is introduced as a new computing paradigm that distributes computation, communication, control, and storage closer to the end users along the "cloud- to-things" continuum. In this paper, we present a deadline-aware task scheduling mechanism for fog computing in a tiered IoT infrastructure, where service providers exploit the collaboration between their own fog nodes and the rented cloud resources to efficiently execute users' offloaded tasks, at large geographical scale. We first formulate the task-scheduling problem in such a cloud-fog environment as a multi-dimensional 0-1 knapsack problem that is NP-hard, and then propose an efficient algorithmic solution based on ant colony optimization heuristic. The main objective is to maximize the profits of fog service provider while meeting the tasks' deadline constraint. Extensive experimental results show that our proposed optimization and solution significantly improves the system performance compared with existing heuristics.

Meeting desired application deadlines is crucial as the nature of cloud applications is becoming increasingly mission-critical and deadline-sensitive. Empirical studies on large-scale clusters reveal that a few slow tasks, known as stragglers, could significantly stretch job execution times. A number of strategies are proposed to mitigate stragglers by launching speculative or clone (task) attempts. These strategies often rely on a model-based approach to optimize key operating parameters and are prone to inaccuracy/incompleteness in the underlying models. In this paper, we present LASER, a deep learning approach for speculative execution and replication of deadline-critical jobs. Machine learning has been successfully used to solve a large variety of classification and prediction problems. In particular, the deep neural network (DNN), consisting of multiple hidden layers of units between input and output layers, can provide more accurate regression (prediction) than traditional machine learning algorithms. We compare LASER with SRQuant, a speculative- resume strategy that is based on quantitative analysis. Both these scheduling algorithms aim to improve Probability of Completion before Deadlines (PoCD), i.e., the probability that MapReduce jobs meet their desired deadlines, and reduce the cost of speculative execution, measured by the total (virtual) machine time. We evaluate and compare the two strategies through testbed experiments. The results show that our two strategies outperform Hadoop without speculation (Hadoop-NS) and Hadoop with speculation (Hadoop-S) by up to 89% in PoCD and 13% in cost.

Mobile edge computing aims at improving application response time and energy efficiency by deploying data processing at the edge of the network. Due to the proliferation of Internet of Things and interactive applications, the ever-increasing demand for low latency calls for novel approaches to further pushing the envelope of mobile edge computing beyond existing task offloading and distributed processing mechanisms. In this paper, we identify a new tradeoff between Quality-of-Result (QoR) and service response time in mobile edge computing. Our key idea is motivated by the observation that a growing set of edge applications involving media processing, machine learning, and data mining can tolerate some level of quality loss in the computed result. By relaxing the need for highest QoR, significant improvement in service response time can be achieved. Toward this end, we present a novel optimization framework, MobiQoR, which minimizes service response time and app energy consumption by jointly optimizing the QoR of all edge nodes and the offloading strategy. The proposed MobiQoR is prototyped using Parse, an open source mobile back-end tool, on Android smartphones. Using representative applications including face recognition and movie recommendation, our evaluation with real-world datasets shows that MobiQoR reduces response time and energy consumption by up to 77% (in face recognition) and 189.3% (in movie recommendation) over existing strategies under the same level of QoR relaxation.

Erasure-coded storage systems have gained considerable adoption recently since they can provide the same level of reliability with significantly lower storage overhead compared to replicated systems. However, background traffic of such systems - e.g. repair, rebalance, backup and recovery traffic - often has large volume and consumes significant network resources. Independently scheduling such tasks and selecting their sources can easily create interference among data flows, causing severe deadline violation. We show that the well-known heuristic scheduling algorithms fail to consider important constraints, thus resulting in unsatisfactory performance. In this paper, we claim that an optimal scheduling algorithm that aims to maximizethe number of background tasks completed before deadlines must simultaneously consider deadline-aware scheduling, network topology, chunk placement, and time-varying resource availability. To solve this problem, we propose a novel algorithm, called Linear Programming for Selected Tasks (LPST) to maximize the number of successful tasks and improve overallutilization of the datacenter network. It jointly schedules tasks and selects their sources based on a notion of Remaining Time Flexibility, which measures the slackness of the starting time of a task. We evaluated the efficacy of our algorithm using extensive simulations. Our results show that, under certain scenarios, LPST can perform 7x~70x better than the heuristics which blindly treat the infrastructure as a collection of homogeneous resources, and 46.6%~65.9% better than the algorithms that take into accountthe network topology.

Distributed storage systems are known to be susceptible to long tails in response time. It has been shown that in modern online applications such as Bing, Facebook, and Amazon, the long tail of latency is of particular concern, with 99.9th percentile response times being orders of magnitude worse than the mean. As erasure codes emerge as a popular technique in distributed storage to achieve high data reliability while attaining space efficiency, taming tail latency remains an open problem due to the lack of mathematical models for analyzing such erasure-coded storage systems. In this paper, we quantify tail latency in distributed storage systems that employ erasure coding. In particular, we derive upper bounds on tail latency in closed-form for arbitrary service time distribution and heterogeneous files. Based on the model, we formulate an optimization problem to jointly minimize weighted latency tail probability of all files. The non-convex problem is solved using an efficient, alternating optimization algorithm. Simulation results show significant reduction of tail latency for erasure-coded storage systems with realistic workload.

In cellular networks, tail states are designed for a tradeoff between energy efficiency and latency. However, the energy consumed during tail states becomes a huge energy drainer itself. Traditional energy saving techniques by content prefetching cannot be directly applied to mobile ads, due to the deadline requirements of ads, randomness in user behaviors, different usage patterns of mobile apps and system services. In this paper, considering several significant runtime factors, we make a novel use of Markov Decision Process to model the energy minimization problem for ad prefetching (EMAP), and propose an algorithmic solution to the EMAP problem. Further, we implement the first mobile ad prefetching system that is fully compatible with contemporary ad libraries and mobile apps. By replaying real-world user traces on Android devices, we show our proposed solution consistently outperforms existing On-Demand policy on Android by up to 59% in saving ad-related energy, while a simple Fill-Up-Buffer policy can be even 2 times worse than the default On-Demand policy. Such findings provide critical insights regarding the promise of saving energy by ad prefetching in real-world mobile systems.

Erasure codes are widely used in distributed storage systems since they provide space-optimal data redundancy to protect against data loss. Despite recent progress on quantifying average service latency when erasure codes are employed, there is very little work on providing differentiated latency among multiple tenants that may have different latency requirements. This paper proposes a novel framework for providing and optimizing differentiated latency in erasure-coded storage by investigating two policies, weighted queue and priority queue, for scheduling tenant requests. For both policies, we quantify service latency for different tenant classes for homogeneous files with arbitrary placement and service time distributions. We develop an optimization framework that jointly minimizes differentiated latency over three decision spaces: 1) data placement; 2) request scheduling; and 3) resource management. Efficient algorithms harnessing bipartite matching and convex optimization techniques are developed to solve the proposed optimization. Our solution enables elastic service-level agreements to meet heterogeneous application requirements. We further prototype our solution with both queuing models applied in an open-source, cloud storage deployment that simulates three geographically distributed data centers through bandwidth reservations. Experimental results validate our theoretical delay analysis and show significant joint latency reduction for different classes of files, providing valuable insights into service differentiation and elastic quality of service in erasure-coded storage systems.

Modern distributed storage systems often use erasure codes to protect against disk and node failures to increase reliability, while trying to meet the latency requirements of the applications and clients. Storage systems may have caches at the proxy or client ends in order to reduce the latency. In this paper, we consider a novel caching framework with erasure code called functional caching. Functional caching involves using erasure-coded chunks in the cache such that the code formed by the chunks in storage nodes and cache combined are maximal-distance-separable erasure codes. Based on the arrival rates of different files, placement of file chunks on the servers, and the service time distribution of storage servers, an optimal functional caching placement and the access probabilities of the file request from different disks are considered. The proposed algorithm gives significant latency improvement in both simulations and a prototyped solution in an open-source, cloud storage deployment.

As demands for cloud-based data processing continue to grow, cloud providers seek effective techniques that deliver value to the businesses without violating Service Level Agreements (SLAs). Cloud right-sizing has emerged as a very promising technique for making cloud services more cost-effective. In this paper, we present CRED, a novel framework for cloud right-sizing with execution deadlines and data locality constraints. CRED jointly optimizes data placement and task scheduling in data centers with the aim of minimizing the number of nodes needed while meeting users' SLA requirements. We formulate CRED as an integer optimization problem and present a heuristic algorithm with provable performance guarantees to solve the problem. Competitive ratios of the proposed algorithm are quantified in closed form for arbitrary task parameters and cloud configurations. We also extend our work to obtain a resilient solution, which allows successful recovery at run time from any single node failure and is guaranteed to meet both deadline and locality constraints. Simulation results using Google trace show that our proposed algorithm significantly outperforms existing heuristics such as first-fit by reducing the number of required active servers by up to 47 percent, and achieves near-optimal performance. We also show that our algorithm can significantly improve utilization of both computational resources and storage space by up to 28 and 15 percent, respectively.

Modern day data centers coordinate hundreds of thousands of heterogeneous tasks and aim at delivering highly reliable cloud computing services. Although offering equal reliability to all users benefits everyone at the same time, users may find such an approach either inadequate or too expensive to fit their individual requirements, which may vary dramatically. In this paper, we propose a novel method for providing elastic reliability optimization in cloud computing. Our scheme makes use of peer-to-peer checkpointing and allows user reliability levels to be jointly optimized based on an assessment of their individual requirements and total available resources in the data center. We show that the joint optimization can be efficiently solved by a distributed algorithm using dual decomposition. The solution improves resource utilization and presents an additional source of revenue to data center operators. Our validation results suggest a significant improvement of reliability over existing schemes.

As demands for cloud-based data processing continue to grow, cloud providers seek effective techniques that deliver value to the business without violating Service Level Agreements (SLAs). Cloud right-sizing has emerged as a very promising technique for making cloud services more cost-effective. In this paper, we present CRED, a novel framework for cloud right-sizing with execution deadlines and data locality constraints. CRED jointly optimizes data placement and task scheduling in data centers with the aim of minimizing the number of nodes needed while meeting users' SLA requirements. We formulate CRED as an integer optimization problem and present a heuristic algorithm with provable performance guarantees to solve the problem. Competitive ratios of the proposed algorithm are quantified in closed form for arbitrary task parameters and cloud configurations. Simulation results using Google trace show that our proposed algorithm significantly outperforms existing heuristics such as first-fit by reducing up to 47% of required active servers, and achieves nearly-optimal performance in terms of cloud-right sizing.

The rapid growth of data traffic in storage systems has put a significant burden on the underlying networks of cloud storage systems. Historically, a key solution to relieve this traffic burden is caching [1]. Many companies have adopted erasure-coded storage systems. However, caching for data centers when the files are encoded with an erasure code has not been studied to the best of our knowledge. This paper proposes a new functional caching approach called Sprout that can efficiently capitalize on existing file coding in erasure-coded storage systems. In contrast to exact caching that stores chunks identical to original copies, our functional caching approach forms d new data chunks, which together with the existing n chunks satisfy the property of being an (n + d, k) MDS code. Thus, the file can now be recovered from any out of n + d chunks (rather than k out of n under exact caching), effectively extending coding redundancy, as well system diversity for scheduling file access requests. The proposed functional caching approach saves latency due to more flexibility to obtain k-d chunks from the storage system a very minimal additional computational cost of creating the coded cached chunks. While quantifying service latency erasure-coded storage systems is an open problem, we generalize previous results on probabilistic scheduling policy [2,3] that distributes file requests to cache and storage nodes with optimized probabilities, and derive a closed-form upper bound on mean service latency for the proposed functional caching approach.

We address the problem of scheduling jobs with utilities that depend solely upon their completion-times in a shared cloud that imposes considerable uncertainty on the jobs' runtime. However, it is very hard to estimate the jobs' runtime in a shared cloud where jobs are often delayed due to reasons such as slow I/O performance and variations in memory availability. Unlike prior works, we acknowledge that runtime estimates are often erroneous and instead shift the burden of robustness to the job scheduler. Specifically, we present a scheduling problem that jointly accounts for: (i) job utilities specified as functions of their completion-time, and (ii) uncertainty in the jobs' runtime. Our proposed solution to this problem achieves lexicographic max-min fairness among the job utilities. We implement this as a robust scheduler, named RUSH, for YARN in Hadoop. Our experiments, using real-world data sets, illustrate RUSH's efficacy when compared with other commonly used schedulers.

This paper presents a semantics-aware rule recommendation and enforcement (SARRE) system for taming information leakage on Android. SARRE leverages statistical analysis and a novel application of minimum path cover algorithm to identify system event paths from dynamic runtime monitoring. Then, an online recommendation system is developed to automatically assign a fine-grained security rule to each event path, capitalizing on both known security rules and application semantic information. The proposed SARRE system is prototyped on Android devices and evaluated using real-world malware samples and popular apps from Google Play spanning multiple categories. Our results show that SARRE achieves 93.8% precision and 96.4% recall in identifying the event paths, compared with tainting technique. Also, the average difference between rule recommendation and manual configuration is less than 5%, validating the effectiveness of the automatic rule recommendation. It is also demonstrated that by enforcing the recommended security rules through a camouflage engine, SARRE can effectively prevent information leakage and enable fine-grained protection over private data with very small performance overhead.

Modern distributed storage systems offer large capacity to satisfy the exponentially increasing need of storage space. They often use erasure codes to protect against disk and node failures to increase reliability, while trying to meet the latency requirements of the applications and clients. This paper provides an insightful upper bound on the average service delay of such erasure-coded storage with arbitrary service time distribution and consisting of multiple heterogeneous files. Not only does the result supersede known delay bounds that only work for a single file or homogeneous files, it also enables a novel problem of joint latency and storage cost minimization over three dimensions: selecting the erasure code, placement of encoded chunks, and optimizing scheduling policy. The problem is efficiently solved via the computation of a sequence of convex approximations with provable convergence. We further prototype our solution in an open-source cloud storage deployment over three geographically distributed data centers. Experimental results validate our theoretical delay analysis and show significant latency reduction, providing valuable insights into the proposed latency-cost tradeoff in erasure-coded storage.

This paper proposes an approach to minimize service latency in a data center network where erasure-coded files are stored on distributed disks/racks and access requests are scattered across the network. Due to limited bandwidth available at both top-of-the-rack and aggregation switches, network bandwidth must be apportioned among different intra-and inter-rack data flows in line with their traffic statistics. We formulate this problem as weighted queuing and employ a class of probabilistic request scheduling policies to derive a closed-form outer-bound of service latency for erasure-coded storage with arbitrary file access patterns and service time distributions. The result enables us to propose a joint latency optimization over three entangled "control knobs": the bandwidth allocation at top-of-the-rack and aggregation switches, the probabilities for scheduling file requests, and the placement of encoded file chunks, which affects data locality. The joint optimization is shown to be a mixed-integer problem. We develop an iterative algorithm which decouples and solves the joint optimization as three sub-problems, which are either convex or solvable via bipartite matching in polynomial time. The proposed algorithm is prototyped in an open-source, distributed file system, Tahoe, and evaluated on a cloud tested with 16 separate physical hosts in an Open Stack cluster. Experiments validate our theoretical latency analysis and show significant latency reduction for diverse file access patterns. The results provide valuable insight on designing low-latency data center networks with erasure-coded storage.

The effect of coding on content retrieval latency in data center storage system is drawing more and more significant attention these days, and customizing elastic service latency for the tenants is undoubtedly appealing to cloud storage, but it also comes with great technical challenges: due to the lack of analytic latency models for erasure-coded storage, most of the literature is limited to the analysis of average service latency, e.g., [1], [2], having assumptions like homogeneous files, exponential service time distribution [3], fixed erasure codes [4], which is unsuitable for a multi-tenant cloud environment where each tenant has a different latency requirement for accessing files in an erasure-coded, online cloud storage. Optimizing differentiated service delay in an erasure-coded storage system is an open problem. This work considers an erasure-coded storage with multiple tenants and differentiated delay demands, studies two types of service policies, non-preemptive priority queue and weighted queue, quantifying service latency of these policies, propose a novel optimization framework that provides differentiated service latency to meet heterogeneous application requirements in cloud storage.

There is an increasing need for cloud service performance that can be tailored to customer requirements. In the context of jobs submitted to cloud computing clusters, a crucial requirement is the specification of job completion-times. A natural way to model this specification, is through client/job utility functions that are dependent on job completion-times. We present a method to allocate and schedule heterogeneous resources to jointly optimize the utilities of jobs in a cloud. Specifically: (i) we formulate a completion-time optimal resource allocation (CORA) problem to apportion cluster resources across the jobs that enforces max-min fairness among job utilities, and (ii) starting with an integer programming problem, we perform a series of steps to transform it into an equivalent linear programming problem, and (iii) we implement the proposed framework as a utility-aware resource scheduler in the widely used Hadoop data processing framework, and finally (iv) through extensive experiments with real-world datasets, we show that our prototype achieves significant performance improvement over existing resource-allocation policies.

Given a set of files that show a certain degree of similarity, we consider a novel problem of deduplicating them (eliminating redundant chunks) across a set of distributed servers in a manner that is: (i) space-efficient: the total space needed to deduplicate and store the files is minimized and, (ii) access-efficient: each file can be accessed by communicating with a bounded number of servers, thereby minimizing network-access times in congested data center networks. A space-optimal solution in which we first deduplicate all the files and then distribute them across the servers (referred to as chunk-distribution), may require communication with many servers to access each file. On the other hand, an access-efficient solution in which we randomly partition the files cross the servers, and then store their unique chunks on each server may not exploit the similarities across files to reduce the space overhead. In this paper, we first show that finding an access-efficient, space optimal solution is an NP-Hard problem. Following this, we present the similarity-aware-partitioning (SAP) algorithms that find access-efficient solutions within polynomial time complexity and guarantees bounded space overhead for arbitrary files. Our experimental verification on files from Dropbox and CNN confirm that the SAP technique is much more space-efficient than random partitioning, while maintaining compression ratio close to the chunk-distribution solution.

Energy accounting determines how much a software principal contributes to the total system energy consumption. It is the foundation for evaluating software and for operating system based energy management. While various energy accounting policies have been tried, there is no known way to evaluate them directly simply because it is hard to track all hardware usage by software in a heterogeneous multicore system like modern smartphones and tablets.

No abstract available.

Quantifying the notion of fairness is underexplored when there are multiple types of resources and users request different ratios of the different resources. A typical example is data centers processing jobs with heterogeneous resource requirements on CPU, memory, network bandwidth, etc. In such cases, a tradeoff arises between equitability, or “fairness,” and efficiency. This paper develops a unifying framework addressing the fairness-efficiency tradeoff in light of multiple types of resources. We develop two families of fairness functions that provide different tradeoffs, characterize the effect of user requests' heterogeneity, and prove conditions under which these fairness measures satisfy the Pareto efficiency, sharing incentive, and envy-free properties. Intuitions behind the analysis are explained in two visualizations of multiresource allocation. We also investigate people's fairness perceptions through an online survey of allocation preferences.

Modern day data centers coordinate hundreds of thousands of heterogeneous tasks and aim at delivering highly reliable cloud computing services. Although offering equal reliability to all users benefits everyone at the same time, users may find such an approach either too inadequate or too expensive to fit their individual requirements, which may vary dramatically. In this paper, we propose a novel method for providing reliability as an elastic and on-demand service. Our scheme makes use of peer-to-peer checkpointing and allows user reliability levels to be jointly optimized based on an assessment of their individual requirements and total available resources in the data center. We show that the joint optimization can be efficiently solved by a distributed algorithm using dual decomposition. The solution improves resource utilization and presents an additional source of revenue to data center operators. Our validation results suggest a significant improvement of reliability over existing schemes.

The ability to account system resource usage by software is the key to the design and optimization of modern computer systems. For example, scheduling and memory management are two classic operating system (OS) functions based on the ability to account the CPU and memory usage by process. Energy has become an important system resource due to electricity and thermal concerns. This is particularly true for mobile systems that are battery-powered and require compact form factors. Knowing the energy contribution by a process, or per-process energy accounting, is the foundation for OS energy management and optimization [11, 9], incentive mechanisms for emerging applications in participatory sensing and cooperative communication, detecting rogue applications [8], and software optimization for energy [6].

Today's data centers need efficient traffic management to improve resource utilization in their networks. In this work, we study a joint tenant (e.g., server or virtual machine) placement and routing problem to minimize traffic costs. These two complementary degrees of freedom—placement and routing—are mutually-dependent, however, are often optimized separately in today's data centers. Leveraging and expanding the technique of Markov approximation, we propose an efficient online algorithm in a dynamic environment under changing traffic loads. The algorithm requires a very small number of virtual machine migrations and is easy to implement in practice. Performance evaluation that employs the real data center traffic traces under a spectrum of elephant and mice flows, demonstrates a consistent and significant improvement over the benchmark achieved by common heuristics.

Quantifying the notion of fairness is under-explored when users request different ratios of multiple distinct resource types. A typical example is datacenters processing jobs with heterogeneous resource requirements on CPU, memory, etc. A generalization of max-min fairness to multiple resources was recently proposed in [1], but may suffer from significant loss of efficiency. This paper develops a unifying framework addressing this fairness-efficiency tradeoff with multiple resource types. We develop two families of fairness functions which provide different tradeoffs, characterize the effect of user requests' heterogeneity, and prove conditions under which these fairness measures satisfy the Pareto efficiency, sharing incentive, and envy-free properties. Intuitions behind the analysis are explained in two visualizations of multi-resource allocation.

Network utility maximization has been widely used to model resource allocation and network architectures. However, in practice, often it cannot be solved optimally due to complexity reasons. Thus motivated, we address the following two questions in this paper: 1) Can suboptimal utility maximization maintain queue stability? 2) Can underoptimization of utility objective function in fact benefit other network design objectives? We quantify the following intuition: A resource allocation that is suboptimal with respect to a utility maximization formulation maintains maximum flow-level stability when the utility gap is sufficiently small and information delay is bounded, and it can still provide a guaranteed size of stability region otherwise. Utility-suboptimal rate allocation can also enhance other network performance metrics, e.g., it may reduce link saturation. These results provide a theoretical support for turning attention from optimal but complex solutions of network optimization to those that are simple even though suboptimal.

Long-Term Evolution (LTE) networks comprising conventional cellular macrocells plus user-installed femtocells offer an economically viable solution to achieving high user capacity and upgrading to future fourth-generation systems. With the growing impetus for frequency reuse, the capacity of each user depends on not only the power spectral density of its own, but also on those of others in neighboring cells. Mitigating interference among macrocells and femtocells requires allocating physical resource dynamically in response to channel conditions. In this paper, we formulate the resource allocation problem as a utility optimization and develop a distributed algorithm for joint power control and user scheduling. The algorithm makes novel use of a class of fairness measures for determining user scheduling and is shown to be very efficient for realistic network parameters. Additionally, using a practical model for the LTE air interface that captures geographic distribution of users and buildings, we provide for a framework that allows comparison of different resource allocation algorithms. A variety of problem formulations, including femtocell density, resource tradeoff, and complexity-optimality tradeoff are derived and analyzed using a geometry-based stochastic LTE air interface model. Our analysis also offers useful guidelines for the planning and design of macrocells and femtocells.

We present five axioms for fairness measures in resource allocation. A family of fairness measures satisfying the axioms is constructed. Special cases of this family include ¿-fairness, Jain's index, and entropy. Properties of fairness measures satisfying the axioms are proven, including Schur-concavity. Among the engineering implications is a generalized Jain's index that tunes the resolution of fairness measure, a new understanding of ¿-fair utility functions, and an interpretation of "larger ¿ is more fair". We also construct an alternative set of axioms to capture system efficiency and feasibility constraints.

We consider a widely applicable model of resource allocation where two sequences of events are coupled: on a continuous time axis (t), network dynamics evolve over time. On a discrete time axis [t], certain control laws update resource allocation variables according to some proposed algorithm. The algorithmic updates, together with exogenous events out of the algorithm's control, change the network dynamics, which in turn changes the trajectory of the algorithm, thus forming a loop that couples the two sequences of events. In between the algorithmic updates at [t-1] and [t], the network dynamics continue to evolve randomly as influenced by the previous variable settings at time [t-1]. The standard way used to avoid the subsequent analytic difficulty is to assume the separation of timescales, which in turn unrealistically requires either slow network dynamics or high complexity algorithms. In this paper, we develop an approach that does not require separation of timescales. It is based on the use of stochastic approximation algorithms with continuous-time controlled Markov noise. We prove convergence of these algorithms without assuming timescale separation. This approach is applied to develop simple algorithms that solve the problem of utility-optimal random access in multi-channel, multi-radio wireless networks.

Secure communications in wireless ad hoc networks require setting up end-to-end secret keys for communicating node pairs. Due to physical limitations and scalability requirements, full key-connectivity can not be achieved by key pre-distribution. In this paper, we develop an analytical framework for the on-demand key establishment approach. We propose a novel security metric, called REM resilience vector to quantify the resilience of any key establishment schemes against Revealing, Erasure, and Modification (REM) attacks. Our analysis shows that previous key establishment schemes are vulnerable under REM attacks. Relying on the new security metric, we prove a universal bound on achievable REM resilience vectors for any on-demand key establishment scheme. This bound that characterizes the optimal security performance analytically is shown to be tight, as we propose a REM-resilient key establishment scheme which achieves any vector within this bound. In addition, we develop a class of low complexity key establishment schemes which achieve nearly-optimal REM-attack resilience.

Not too bad. A rate allocation that is suboptimal with respect to a utility maximization formulation still maintains the maximum flow-level stability when the utility gap is sufficiently small, and provides a minimum size of stability region otherwise. Utility-suboptimal allocation may also enhance other network performance metrics, e.g., it may increase network throughput and reduce link saturation. Quantifying these intuitions, this paper provides a theoretical support for turning attention from optimal but complex solutions of network optimization to those that are simple even though suboptimal.

This paper considers the nonconvex and globally coupled problem of joint antenna beamforming and transmit power control, in order to maximize the network-wide utility as a function of attained SIRs. Using a spillage-load characterization for power control [13], we assign utility as a function of attained SIRs and formulate the joint optimization as a utility maximization problem. Despite the highly coupled structure of the problem, we propose an efficient distributed algorithm that is proved to be convergent in general. Despite nonconvexity in the joint optimization, we prove global optimality in the two user case. We find in simulations the algorithm always converges to the global optimal allocation, and the Pareto-optimal tradeoff between power and antenna beamforming in maximizing network utility is illustrated.