In environments with sparse or delayed rewards, reinforcement learning (RL) incurs high sample complexity due to the large number of interactions needed for learning. This limitation has motivated the use of large language models (LLMs) for subgoal discovery and trajectory guidance. While LLMs can support exploration, frequent reliance on LLM calls raises concerns about scalability and reliability. We address these challenges by constructing a memory graph that encodes subgoals and trajectories from both LLM guidance and the agent’s own successful rollouts. From this graph, we derive a utility function that evaluates how closely the agent’s trajectories align with prior successful strategies. This utility shapes the advantage function, providing the critic with additional guidance without altering the reward. Our method relies primarily on offline input and only occasional online queries, avoiding dependence on continuous LLM supervision. Preliminary experiments in benchmark environments show improved sample efficiency and faster early learning compared to baseline RL methods, with final returns comparable to methods that require frequent LLM interaction.

Large Language Models (LLMs) are revolutionizing how users interact with information systems, yet their high inference cost poses serious scalability and sustainability challenges. Caching inference responses, allowing them to be retrieved without another forward pass through the LLM, has emerged as one possible solution. Traditional exact-match caching, however, overlooks the semantic similarity between queries, leading to unnecessary recomputation. Semantic caching addresses this by retrieving responses based on semantic similarity, but introduces a fundamentally different cache eviction problem: one must account for mismatch costs between incoming queries and cached responses. Moreover, key system parameters, such as query arrival probabilities and serving costs, are often unknown and must be learned over time. Existing semantic caching methods are largely ad-hoc, lacking theoretical foundations and unable to adapt to real-world uncertainty. In this paper, we present a principled, learning-based framework for semantic cache eviction under unknown query and cost distributions. We formulate both offline optimization and online learning variants of the problem, and develop provably efficient algorithms with state-of-the-art guarantees. We also evaluate our framework on a synthetic dataset, showing that our proposed algorithms perform matching or superior performance compared with baselines.

While Vision Transformers (ViTs) have emerged as foundation models for visual recognition, their high computational demands hinder deployment on edge platforms. Temporal redundancy across video frames offers a natural opportunity to reuse prior computations; however, existing methods remain far from ideal, often relying on simple frame-difference signals. To address this, we propose Ouroboros, a framework that encompasses geometric redundancy from spatial displacement of content. We achieve this by aligning invariant content to consistent coordinates across frames, enabled by warping each frame into a global coordinate system via motion vectors from a hardware-accelerated encoder. Yet, this design raises two key challenges: (i) preserving content that drifts out of the limited coordinate system and (ii) maintaining spatial continuity at frame borders. Ouroboros resolves these challenges by introducing a toroidal (i.e., wrap-around) input space and reassigning positional encodings to track displaced content. Leveraging the significant patch reduction via a system-efficient partial computation scheme, our approach accelerates inference by up to 2.61× and reduces energy consumption by 64.5% on NVIDIA Jet-son Orin devices, with <1% accuracy loss on object detection and instance segmentation, outperforming prior methods. Designed to process only non-redundant patches, Ouroboros also excels as an offloading system, yielding higher accuracy at lower bandwidth compared to prior schemes. The source code is available at https://github.com/ckswjd99-lab/Ouroboros.

Abstract Neural Radiance Fields (NeRF) methods excel at 3D reconstruction from multiple 2D images, even those taken with unknown camera poses. However, they still miss the fine-detailed structures that matter in industrial inspection, e.g., detecting sub-micron defects on a production line or analyzing chips with Scanning Electron Microscopy (SEM). In these scenarios, the sensor resolution is fixed and compute budgets are tight, so the only way to expose fine structure is to add zoomed-in images; yet, this breaks the multi-view consistency that pose-free NeRF training relies on. We propose Multi-Zoom Enhanced NeRF (MZEN), the first NeRF framework that natively handles multi-zoom image sets. MZEN (i) augments the pin-hole camera model with an explicit, learnable zoom parameter that scales the focal length, and (ii) introduces a novel pose estimation strategy: wide-field (i.e., zoomed-out) images are used first to establish a global metric frame, and the poses of zoomed-in images are then initialized to the nearest wide-field counterpart via a zoom-consistent crop-and-match procedure before joint refinement of both poses and the NeRF model. Across eight forward-facing scenes—synthetic TCAD models, real SEM of micro-structures, and BLEFF objects—MZEN consistently outperforms pose-free baselines and even high-resolution variants, boosting PSNR by up to $$32 \%$$ , SSIM by $$52 \%$$ , and reducing LPIPS by up to $$400 \%$$ . MZEN, therefore, extends NeRF to real-world factory settings, preserving global accuracy while capturing the micron-level details essential for industrial inspection.

Combinatorial multi-armed bandit (CMAB) is a fundamental online learning framework that can optimize cumulative rewards in networked systems under uncertainty. Real-world applications like content delivery and channel allocation often feature binary base arm rewards and nonlinear total reward functions. This paper introduces combinatorial logistic bandits (CLogB), a contextual CMAB framework with the base arm reward modeled as a nonlinear logistic function of the context, and the feedback is governed by a general arm-triggering process. We study CLogB with smooth reward functions, covering applications such as online content delivery, online multi-LLM selection, and dynamic channel allocation. Our first algorithm, CLogUCB, uses a variance-agnostic exploration bonus and achieves a regret bound of Õ(d√κKT), where d is the feature dimension, κ reflects logistic model nonlinearity,Kis the maximum number of triggered arms, and Õ ignores logarithmic factors. This improves on prior results by Õ (√κ). We further propose VA-CLogUCB, a variance-adaptive enhancement achieving regret bounds of Õ(d√KT) under standard smoothness conditions and Õ (d√T) under stronger variance conditions, removing dependence on K. For time-invariant feature maps, we enhance computational efficiency by avoiding nonconvex optimization while maintaining Õ(d√T) regret. Experiments on synthetic and real-world datasets validate the superior performance of our algorithms, demonstrating their effectiveness and scalability for real-world networked systems.

We consider the contextual combinatorial bandit setting where in each round, the learning agent, e.g., a recommender system, selects a subset of "arms,'' e.g., products, and observes rewards for both the individual base arms, which are a function of known features (called "context''), and the super arm (the subset of arms), which is a function of the base arm rewards. The agent's goal is to simultaneously learn the unknown reward functions and choose the highest-reward arms. For example, the "reward'' may represent a user's probability of clicking on one of the recommended products. Conventional bandit models, however, employ restrictive reward function models in order to obtain performance guarantees. We make use of deep neural networks to estimate and learn the unknown reward functions and propose Neural UCB Clustering (NeUClust), which adopts a clustering approach to select the super arm in every round by exploiting underlying structure in the context space. Unlike prior neural bandit works, NeUClust uses a neural network to estimate the super arm reward and select the super arm, thus eliminating the need for a known optimization oracle. We non-trivially extend prior neural combinatorial bandit works to prove that NeUClust achieves sublinear regret in the number of rounds. Experiments on real world recommendation datasets show that NeUClust achieves better regret and reward than other contextual combinatorial and neural bandit algorithms.

We study a federated version of multi-objective optimization (MOO), where a single model is trained to optimize multiple objective functions. MOO has been extensively studied in the centralized setting but is less explored in federated or distributed settings. We propose FedCMOO, a novel communication-efficient federated multi-objective optimization (FMOO) algorithm that improves the error convergence performance of the model compared to existing approaches. Unlike prior works, the communication cost of FedCMOO does not scale with the number of objectives, as each client sends a single aggregated gradient, obtained using randomized SVD (singular value decomposition), to the central server. We provide a convergence analysis of the proposed method for smooth non-convex objective functions under milder assumptions than in prior work. In addition, we introduce a variant of FedCMOO that allows users to specify a preference over the objectives in terms of a desired ratio of the final objective values. Through extensive experiments, we demonstrate the superiority of our proposed method over baseline approaches.

Foundation models are now a major focus of leading technology organizations due to their ability to generalize across diverse tasks. Existing approaches for adapting foundation models to new applications often rely on Federated Learning (FL) and disclose the foundation model weights to clients when using it to initialize the global model. While these methods ensure client data privacy, they compromise model and information security. In this paper, we introduce Federated Learning Aggregation Biased by a Foundation Model (FedBaF), a novel method for dynamically integrating pre-trained foundation model weights during the FL aggregation phase. Unlike conventional methods, FedBaF preserves the confidentiality of the foundation model while still leveraging its power to train more accurate models, especially in non-IID and adversarial scenarios. Our comprehensive experiments use Pre-ResNet and foundation models like Vision Transformer to demonstrate that FedBaF not only matches, but often surpasses the test accuracy of traditional weight initialization methods by up to 11.4% in IID and up to 15.8% in non-IID settings. Additionally, FedBaF applied to a Transformer-based language model significantly reduced perplexity by up to 39.2%.

Federated learning (FL) addresses privacy concerns in training language models by enabling multiple clients to contribute to the training, without sending their data to others. However, non-IID (identically and independently distributed) data across clients often limits FL’s performance. This issue is especially challenging during model fine-tuning, as noise due to variations in clients’ data distributions can harm model convergence near stationary points. This paper proposes a targeted layer update strategy for fine-tuning in FL. Instead of randomly updating layers of the language model, as often done in practice, we use a scoring mechanism to identify and update the most critical layers, avoiding excessively noisy or even poisoned updates by freezing the parameters in other layers. We show in extensive experiments that our method improves convergence and performance in non-IID settings, offering a more efficient approach to fine-tuning federated language models.

Non-independent and identically distributed (Non-IID) data across edge clients have long posed significant challenges to federated learning (FL) training. Prior works have proposed various methods to mitigate this statistical heterogeneity. While these methods can achieve good theoretical performance, they may lead to the over-correction problem, which degrades model performance and even causes failures in model convergence. In this paper, we provide the first investigation into the hidden over-correction phenomenon brought by the uniform model correction coefficients across clients adopted by the existing methods. To address this problem, we propose TACO, a novel algorithm that addresses the non-IID nature of clients’ data by implementing fine-grained, client-specific gradient correction and model aggregation, steering local models towards a more accurate global optimum. Moreover, we verify that leading FL algorithms generally have better model accuracy in terms of communication rounds rather than wall-clock time, resulting from their extra computation overhead imposed on clients. To enhance the training efficiency, TACO deploys a lightweight model correction and tailored aggregation approach that requires minimum computation overhead and no extra information beyond the synchronized model parameters. To validate TACO’s effectiveness, we present the first FL convergence analysis that reveals the root cause of over-correction. Extensive experiments across various datasets confirm TACO’s superior and stable performance in practice.

Multi-armed bandits (MAB) are commonly used in sequential online decision-making when the reward of each decision is an unknown random variable. In practice however, the typical goal of maximizing total reward may be less important than minimizing the total cost of the decisions taken, subject to a reward constraint. For example, we may seek to make decisions that have at least the reward of a reference ``default'' decision, with as low a cost as possible. This problem was recently introduced in the Multi-Armed Bandits with Cost Subsidy (MAB-CS) framework. MAB-CS is broadly applicable to problem domains where a primary metric (cost) is constrained by a secondary metric (reward), and the rewards are unknown. In our work, we address variants of MAB-CS including ones with reward constrained by the reward of a known reference arm or by the subsidized best reward. We introduce the Pairwise-Elimination (PE) algorithm for the known reference arm variant and generalize PE to PE-CS for the subsidized best reward variant. Our instance-dependent analysis of PE and PE-CS reveals that both algorithms have an order-wise logarithmic upper bound on Cost and Quality Regret, making our policies the first with such a guarantee. Moreover, by comparing our upper and lower bound results we establish that PE is order-optimal for all known reference arm problem instances. Finally, experiments are conducted using the MovieLens 25M and Goodreads datasets for both PE and PE-CS revealing the effectiveness of PE and the superior balance between performance and reliability offered by PE-CS compared to baselines from the literature.

The combinatorial multi-armed bandit (CMAB) is a fundamental sequential decision-making framework, extensively studied over the past decade. However, existing work primarily focuses on the online setting, overlooking the substantial costs of online interactions and the readily available offline datasets. To overcome these limitations, we introduce Off-CMAB, the first offline learning framework for CMAB. Central to our framework is the combinatorial lower confidence bound (CLCB) algorithm, which combines pessimistic reward estimations with combinatorial solvers. To characterize the quality of offline datasets, we propose two novel data coverage conditions and prove that, under these conditions, CLCB achieves a near-optimal suboptimality gap, matching the theoretical lower bound up to a logarithmic factor. We validate Off-CMAB through practical applications, including learning to rank, large language model (LLM) caching, and social influence maximization, showing its ability to handle nonlinear reward functions, general feedback models, and out-of-distribution action samples that excludes optimal or even feasible actions. Extensive experiments on synthetic and real-world datasets further highlight the superior performance of CLCB.

Federated learning has recently gained popularity as a framework for distributed clients to collaboratively train a machine learning model using local data. While traditional federated learning relies on a central server for model aggregation, recent advancements adopt a decentralized framework, enabling direct model exchange between clients and eliminating the single point of failure. However, existing decentralized frameworks often assume all clients train a shared model. Personalizing each client’s model can enhance performance, especially with heterogeneous client data distributions. We propose FedSPD, an efficient personalized federated learning algorithm for the decentralized setting, and show that it learns accurate models in low-connectivity networks. To provide theoretical guarantees on convergence, we introduce a clustering-based framework that enables consensus on models for distinct data clusters while personalizing to unique mixtures of these clusters at different clients. This flexibility, allowing selective model updates based on data distribution, substantially reduces communication costs compared to prior work on personalized federated learning in decentralized settings. Experimental results on real-world datasets show that FedSPD outperforms multiple decentralized variants of existing personalized federated learning algorithms in scenarios with low-connectivity networks.

Federated learning (FL) allows multiple clients to collaboratively train a model without sharing their private data. In practical scenarios, clients frequently engage in training multiple models concurrently, referred to as multi-model federated learning (MMFL). While concurrent training is generally faster than training one model at a time, MMFL exacerbates traditional FL challenges like the presence of non-i.i.d. data: since each individual client may only be able to train one model in each training round due to local resource limitations, the set of clients training each model will change in each round, introducing instability when clients have different data distributions. Existing single-model FL approaches leverage inherent client clustering to accelerate convergence in the presence of such data heterogeneity. However, since each MMFL model may train on a different dataset, extending these ideas to MMFL requires creating a unified cluster or group structure that supports all models while coordinating their training. In this paper, we present the first group-based client-model allocation scheme in MMFL able to accelerate the training process and improve MMFL performance. We also consider a more realistic scenario in which models and clients can dynamically join the system during training. Empirical studies in real-world datasets show that our MMFL algorithms outperform several baselines up to 15 %, particularly in more complex and statically heterogeneous scenarios.

The Probabilistic Maximum Coverage (PMC) problem plays a pivotal role in modeling various network applications, such as mobile crowdsensing, which involves selecting nodes within a graph that probabilistically cover other nodes. Our study focuses on PMC within the framework of online learning, termed the PMC bandit, where the network parameters are initially unknown. In this scenario, the decision-maker is tasked with learning these parameters to maximize the cumulative rewards from covered nodes. Despite prior research on the PMC bandit, we propose a novel variant, dynamic PMC-G bandit, which extends the semi-bandit feedback model to represent applications more accurately. To tackle the complexities of the time-varying combinatorial arm set rather than traditional static, we enhance the Combinatorial Upper Confidence Bound (CUCB) algorithms by developing two innovative variance-aware strategies: the Variance-Adaptive Combinatorial Upper Confidence Bound (VACUCB) for probabilistically triggered arms, and the Action-Based Combinatorial Upper Confidence Bound (ABCUCB) for self-reliant arms, i.e., independent arms with probabilistically triggered outcomes. Based on variance-aware properties, our contributions notably reduce the dependence on the number of nodes$K$selected per round, demonstrating that: (i) VACUCB effectively minimizes the regret associated with the triggered arms, enhancing the CUCB by a factor of$\tilde{O}(K)$; (ii) ABCUCB further diminishes the dependence on$K$in the leading term. Empirical results from synthetic and real-world datasets confirm that our proposed algorithms outperform current benchmarks in three network applications.

Federated learning (FL) enables collaborative learning across multiple clients. In most FL work, all clients train a single learning task. However, the recent proliferation of FL applications may increasingly require multiple FL tasks to be trained simultaneously, sharing clients’ computing resources, which we call Multiple-Model Federated Learning (MMFL). Current MMFL algorithms use naïve average-based client-task allocation schemes that often lead to unfair performance when FL tasks have heterogeneous difficulty levels, as the more difficult tasks may need more client participation to train effectively. Furthermore, in the MMFL setting, we face a further challenge that some clients may prefer training specific tasks to others, and may not even be willing to train other tasks, e.g., due to high computational costs, which may exacerbate unfairness in training outcomes across tasks. We address both challenges by firstly designing FedFairMMFL, a difficulty-aware algorithm that dynamically allocates clients to tasks in each training round, based on the tasks’ current performance levels. We provide guarantees on the resulting task fairness and FedFairMMFL’s convergence rate. We then propose novel auction designs that incentivizes clients to train multiple tasks, so as to fairly distribute clients’ training efforts across the tasks, and extend our convergence guarantees to this setting. We finally evaluate our algorithm with multiple sets of learning tasks on real world datasets, showing that our algorithm improves fairness by improving the final model accuracy and convergence speed of the worst performing tasks, while maintaining the average accuracy across tasks.

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.

Federated learning (FL) is a variant of distributed learning in which multiple clients collaborate to learn a global model without sharing their data with the central server. In real-world scenarios, a client may be involved in training multiple unrelated FL models, which we call multi-model federated learning (MMFL), and the client sampling strategy and task allocation are crucial for improving system performance. In this paper, we propose an optimal sampling method to minimize the variance of global updates for unbiased learning in MMFL systems. The resulting method achieves an average accuracy of over 30 % higher than other baseline methods, as we demonstrate through simulations on real-world federated datasets.

The emergence of 5G technology and edge computing enables the collaborative use of data by mobile users for scalable training of machine learning models. Privacy concerns and communication constraints, however, can prohibit users from offloading their data to a single server for training. Split learning, in which models are split between end users and a central server, somewhat resolves these concerns but requires exchanging information between users and the server in each local training iteration. Thus, splitting models between end users and geographically close edge servers can significantly reduce communication latency and training time. In this setting, users must decide to which edge servers they should offload part of their model to minimize the training latency, a decision that is further complicated by the presence of multiple, mobile users competing for resources. We present Edge-MSL, a novel formulation of the mobile split learning problem as a contextual multi-armed bandits framework. To counter scalability challenges with a centralized Edge-MSL solution, we introduce a distributed solution that minimizes competition between users for edge resources, reducing regret by at least two times compared to a greedy baseline. The distributed Edge-MSL approach improves trained model convergence with a 15% increase in test accuracy.

As edge computing capabilities increase, model learning deployments in diverse edge environments have emerged. In experimental design networks, introduced recently, network routing and rate allocation are designed to aid the transfer of data from sensors to heterogeneous learners. We design efficient experimental design network algorithms that are (a) distributed and (b) use multicast transmissions. This setting poses significant challenges as classic decentralization approaches often operate on (strictly) concave objectives under differentiable constraints. In contrast, the problem we study here has a non-convex, continuous DR-submodular objective, while multicast transmissions naturally result in non-differentiable constraints. From a technical standpoint, we propose a distributed Frank-Wolfe and a distributed projected gradient ascent algorithm that, coupled with a relaxation of non-differentiable constraints, yield allocations within a 1 − 1/e factor from the optimal. Numerical evaluations show that our proposed algorithms outperform competitors with respect to model learning quality.

This paper addresses challenges in monitoring human behavior in crowds through floor vibration sensing, overcoming limitations like subjective manual observation, visual occlusions, and audio interference. Our approach involves tackling limited-data vibration signal tasks by conducting pre-training across modalities, leveraging publicly available audio datasets. By leveraging self-supervised representation learning to pre-train on publicly available audio datasets, our approach reduces data requirements, improves robustness, and minimizes the need for human labeling efforts. Evaluation using in-game stadium vibration data with YouTube audio dataset demonstrates up to 5.8 × error reduction for crowd behavior.

This paper introduces FedSecurity, an end-to-end benchmark that serves as a supplementary component of the FedML library for simulating adversarial attacks and corresponding defense mechanisms in Federated Learning (FL). FedSecurity eliminates the need for implementing the fundamental FL procedures, e.g., FL training and data loading, from scratch, thus enables users to focus on developing their own attack and defense strategies. It contains two key components, including FedAttacker that conducts a variety of attacks during FL training, and FedDefender that implements defensive mechanisms to counteract these attacks. FedSecurity has the following features: i) It offers extensive customization options to accommodate a broad range of machine learning models (e.g., Logistic Regression, ResNet, and GAN) and FL optimizers (e.g., FedAVG, FedOPT, and FedNOVA); ii) it enables exploring the effectiveness of attacks and defenses across different datasets and models; and iii) it supports flexible configuration and customization through a configuration file and some APIs. We further demonstrate FedSecurity's utility and adaptability through federated training of Large Language Models (LLMs) to showcase its potential on a wide range of complex applications.

Computer vision has been used more ubiquitously in recent years to understand and measure the environment around us, particularly in our neighborhoods. However, many city-wide sensing applications using vision require large labeling efforts, making various applications difficult on a wide scale. We propose a framework for labeling and self-training of in-car video to detect trash on the roads. Our approach requires minimal manual labeling to identify items not meant to be in the street, sidewalk, or public places, from a front-viewing car camera. Our system provides each frame of a video with a score indicating the amount of trash. To prevent overfitting, due to minimal available data, we remove data with high certainty of trash from the training dataset. The results show that our prediction with manually labeled ground truth yield an R2 of 0.66.

Recent successes in natural language processing have led to the proliferation of large language models (LLMs) by multiple providers. Each LLM offering has different inference accuracy, monetary cost, and latency, and their accuracy further depends on the exact wording of the question (i.e., the specific prompt). At the same time, users often have a limit on monetary budget and latency to answer all their questions, and they do not know which LLMs to choose for each question to meet their accuracy and long term budget requirements. To navigate this rich design space, we propose TREACLE (Thrifty Reasoning via Context-Aware LLM and Prompt Selection), a reinforcement learning policy that jointly selects the model and prompting scheme while respecting the user's monetary cost and latency constraints. TREACLE uses the problem context, including question text embeddings (reflecting the type or difficulty of a query) and the response history (reflecting the consistency of previous responses) to make smart decisions. Our evaluations on standard reasoning datasets (GSM8K, CSQA, and LLC) with various LLMs and prompts show that TREACLE enables cost savings of up to 85% compared to baselines, while maintaining high accuracy. Importantly, it provides the user with the ability to gracefully trade off accuracy for cost.

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).

Addressing intermittent client availability is critical for the real-world deployment of federated learning algorithms. Most prior work either overlooks the potential non-stationarity in the dynamics of client unavailability or requires substantial memory/computation overhead. We study federated learning in the presence of heterogeneous and non-stationary client availability, which may occur when the deployment environments are uncertain, or the clients are mobile. The impacts of heterogeneity and non-stationarity on client unavailability can be significant, as we illustrate using FedAvg, the most widely adopted federated learning algorithm. We propose FedAWE, which includes novel algorithmic structures that (i) compensate for missed computations due to unavailability with only $O(1)$ additional memory and computation with respect to standard FedAvg, and (ii) evenly diffuse local updates within the federated learning system through implicit gossiping, despite being agnostic to non-stationary dynamics. We show that FedAWE converges to a stationary point of even non-convex objectives while achieving the desired linear speedup property. We corroborate our analysis with numerical experiments over diversified client unavailability dynamics on real-world data sets.

Federated Learning (FL) enables edge devices or clients to collaboratively train machine learning (ML) models without sharing their private data. Much of the existing work in FL focuses on efficiently learning a model for a single task. In this paper, we study simultaneous training of multiple FL models using a common set of clients. The few existing simultaneous training methods employ synchronous aggregation of client updates, which can cause significant delays because large models and/or slow clients can bottleneck the aggregation. On the other hand, a naive asynchronous aggregation is adversely affected by stale client updates. We propose FedAST, a buffered asynchronous federated simultaneous training algorithm that overcomes bottlenecks from slow models and adaptively allocates client resources across heterogeneous tasks. We provide theoretical convergence guarantees for FedAST for smooth non-convex objective functions. Extensive experiments over multiple real-world datasets demonstrate that our proposed method outperforms existing simultaneous FL approaches, achieving up to 46.0% reduction in time to train multiple tasks to completion.

The open radio access network (O-RAN) architecture provides enhanced opportunities for integrating machine learning in 5G/6G resource management by decomposing RAN functionalities. Yet, generic learning mechanisms either do not fully exploit the disaggregated non-real-time and near-real-time RAN controllers or ignore the potential elasticity of application demands, another degree of freedom in managing RAN resources. We introduce a two-timescale framework aimed at optimizing users’ long-term total QoS. Rather than reactive resource allocation, our approach proactively modifies multi-resource user demands using congestion indicators, prior to enforcing any allocation rules. Addressing the issue of insufficient user feedback on individual resource utilities, we employ a bandit-feedback version of the combinatorial multi-armed bandit framework to deduce resource-specific signals. Also, to compensate for insufficient and infrequent feedback, we’ve developed an algorithm that gleans side information from live network traffic to refine predictions on user resource sensitivities. This streamlines the algorithm’s optimality convergence and leverages the two-tier O-RAN controller structure. We validate our algorithms’ efficacy through analysis and 5G usage experiments, revealing our proposed method improves application utility by 13-60%, throughput by 8-19%, and reduces latency by 10-18%.

Deep learning (DL) powered real-time applications usually need continuous training using data streams generated over time and across different geographical locations. Enabling data offloading among computation nodes through model training is promising to mitigate the problem that devices generating large datasets may have low computation capability. However, offloading can compromise model convergence and incur communication costs, which must be balanced with the long-term cost spent on computation and model synchronization. Therefore, this paper proposes EdgeC3, a novel framework that can optimize the frequency of model aggregation and dynamic offloading for continuously generated data streams, navigating the trade-off between long-term accuracy and cost. We first provide a new error bound to capture the impacts of data dynamics that are varying over time and heterogeneous across devices, as well as quantifying varied data heterogeneity between local models and the global one. Based on the bound, we design a two-timescale online optimization framework. We periodically learn the synchronization frequency to adapt with uncertain future offloading and network changes. In the finer timescale, we manage online offloading by extending Lyapunov optimization techniques to handle an unconventional setting, where our long-term global constraint can have abruptly changed aggregation frequencies that are decided in the longer timescale. Finally, we theoretically prove the convergence of EdgeC3 by integrating the coupled effects of our two-timescale decisions, and we demonstrate its advantage through extensive experiments performing distributed DL training for different domains.

Federated Learning (FL) is a distributed learning paradigm that can coordinate heterogeneous edge devices to perform model training without sharing private data. While prior works have focused on analyzing FL convergence with respect to hyperparameters like batch size and aggregation frequency, the joint effects of adjusting these parameters on model performance, training time, and resource consumption have been overlooked, especially when facing dynamic data streams and network characteristics. This paper introduces novel analytical models and optimization algorithms that leverage the interplay between batch size and aggregation frequency to navigate the trade-offs among convergence, cost, and completion time for dynamic FL training. We establish a new convergence bound for training error considering heterogeneous datasets across devices and derive closed-form solutions for co-optimized batch size and aggregation frequency that are consistent across all devices. Additionally, we design an efficient algorithm for assigning different batch configurations across devices, improving model accuracy and addressing the heterogeneity of both data and system characteristics. Further, we propose an adaptive control algorithm that dynamically estimates network states, efficiently samples appropriate data batches, and effectively adjusts batch sizes and aggregation frequency on the fly. Extensive experiments demonstrate the superiority of our offline optimal solutions and online adaptive algorithm.

Federated learning allows distributed clients to train a shared machine learning model while preserving user privacy. In this framework, user devices (i.e., clients) perform local iterations of the learning algorithm on their data. These updates are periodically aggregated to form a shared model. Thus, a client represents the bundle of the user data, the device, and the user’s willingness to participate: since participating in federated learning requires clients to expend resources and reveal some information about their data, users may require some form of compensation to contribute to the training process. Recruiting more users generally results in higher accuracy, but slower completion time and higher cost. We propose the first work to theoretically analyze the resulting performance tradeoffs in deciding which clients to recruit for the federated learning algorithm. Our framework accounts for both accuracy (training and testing) and efficiency (completion time and cost) metrics. We provide solutions to this NP-Hard optimization problem and verify the value of client recruitment in experiments on synthetic and real-world data. The results of this work can serve as a guideline for the real-world deployment of federated learning and an initial investigation of the client recruitment problem.

On-demand and resource reservation pricing models, widely used in cloud computing, are currently used in Multi-Access Edge Computing (MEC). Nevertheless the edge's resources are distributed and each server has lower capacity. If too much resources were reserved in advance, on-demand users may not get their jobs served on time, jeopardizing MEC's latency benefits. Concurrently, reservation plan users may possess un-used quota. Therefore, we propose a sharing platform where reservation plan users can re-sell unused resource quota to on-demand users. To investigate the mobile network operator's (MNO‘s) incentive of allowing re-selling, we formulate a 3-stage non-cooperative Stackelberg Game and characterize the optimal strategies of buyers and re-sellers. We show that users’ actions give rise to 4 different outcomes at equilibrium, dependent on the prices and supply levels of the sharing and on-demand pools. Based on the 4 possible outcomes, we characterise the MNO's optimal prices for on-demand users. Numerical results show that having both pools gives the MNO an optimal revenue when the on-demand pool's supply is low, and unexpectedly, when the MNO's commission is low. We develop an interactive prototype, and show that users’ decision distributions in studies on our prototype are similar to that of our decision model.

Federated learning allows for clients in a distributed system to jointly train a machine learning model. However, clients’ models are vulnerable to attacks during the training and testing phases. In this paper, we address the issue of adversarial clients performing “internal evasion attacks”: crafting evasion attacks at test time to deceive other clients. For example, adversaries may aim to deceive spam filters and recommendation systems trained with federated learning for monetary gain. The adversarial clients have extensive information about the victim model in a federated learning setting, as weight information is shared amongst clients. We are the first to characterize the transferability of such internal evasion attacks for different learning methods and analyze the trade-off between model accuracy and robustness depending on the degree of similarities in client data. We show that adversarial training defenses in the federated learning setting only display limited improvements against internal attacks. However, combining adversarial training with personalized federated learning frameworks increases relative internal attack robustness by 60$%$ compared to federated adversarial training and performs well under limited system resources.

No abstract available.

Cascading failures are a common phenomenon in complex networked systems, where failures at only a few nodes may trigger a process of sequential failures. We investigate the robustness against cascading failures in systems carrying flows or loads that contain multiple interdependent networks, e.g., power grid, transportation system, etc. In these systems, the coupling coefficients between the networks, which determine how the flow from failed components gets redistributed across the networks, is a key factor affecting the robustness against cascading failures. Prior work has introduced the step-wise optimization (SWO) strategy that dynamically adjusts the coupling coefficients during the course of the cascading failures in an effort to preserve the network size. SWO has been shown to have good performance against cascading failures on synthetic data. In this paper, we show the optimality of the SWO strategy under certain conditions on the flow and capacity distributions of the nodes. We also show, via simulations, that the SWO strategy performs well under various real-world network topologies as well.

Probabilistic maximum coverage (PMC) is an important problem that can model many network applications, including mobile crowdsensing, network content delivery, and dynamic channel allocation, where an operator chooses nodes in a graph that can probabilistically cover other nodes. In this paper, we study PMC under the online learning context: the PMC bandit. For PMC bandit where network parameters are not known a priori, the decision maker needs to learn the unknown parameters and the goal is to maximize the total rewards from the covered nodes. Though PMC bandit has been studied previously, the existing model and its corresponding algorithm can be significantly improved. First, we propose the PMC-G bandit whose feedback model generalizes existing semi-bandit feedback, allowing PMC bandit to model applications like online content delivery and online dynamic channel allocation. Next, we improve the existing combinatorial upper confidence bound (CUCB) algorithm by introducing the variance-adaptive algorithm, i.e., the VA-CUCB algorithm. We prove that VA-CUCB can achieve strictly better regret bounds, which improves CUCB by a factor of $\tilde O(K)$, where K is the number of nodes selected in each round. Finally, experiments show our superior performance compared with benchmark algorithms on synthetic and real-world datasets.

Federated learning (FL) is an increasingly popular form of distributed learning across devices such as sensors and smartphones. To amortize the effort and cost of setting up FL training in real world systems, in practice multiple machine learning tasks may be trained during one FL execution. However, given that the tasks have varying complexities, naïve methods of allocating resource-constrained devices to work on each task may lead to highly variable performance across the tasks. We instead propose an α -fair based allocation algorithm that dynamically allocates tasks to users during multi-model FL training, based on the prevailing loss levels.

Federated Learning (FL) is a distributed learning paradigm that can coordinate heterogeneous edge devices to perform model training without sharing private raw data. Many prior works have analyzed the FL convergence with respect to important hyperparameters, including batch size and aggregation frequency. However, adjusting the batch size and the number of local updates can affect the model performance, training time, and the cost of consuming computation and communication resources, in different and perhaps complex forms. Their joint effects have been overlooked and should be exploited to achieve accurate models with controllable operational expenditure. This paper proposes novel analytical models and optimization algorithms that leverage the interplay of batch size and aggregation frequency to navigate the trade-offs among convergence, cost, and completion time for FL. We first obtain a new convergence bound of the training error under heterogeneous training datasets across devices. Based on this bound, we derive closed-form solutions of a co-optimized batch size and aggregation frequency, a single configuration for all the devices. We then design an efficient exact algorithm for assigning different batch configurations across devices that can further improve the model accuracy to address the heterogeneity of both data and system characteristics. Further, we propose an adaptive control algorithm to dynamically adjust the solutions with estimated network states. Extensive experiments demonstrate the superiority of our offline optimal solutions and online adaptive algorithm.

Federated learning (FL) is a distributed paradigm for collaboratively learning models without having clients disclose their private data. One natural and practically relevant metric to measure the efficiency of FL algorithms is the total wall-clock training time, which can be quantified by the product of the average time needed for a single iteration and the number of iterations for convergence. In this work, we focus on improving FL efficiency with respect to this metric through caching. Specifically, instead of having all clients download the latest global model from a parameter server, we select a subset of clients to access, with a smaller delay, a somewhat stale global model stored in caches. We propose CacheFL - a cache-enabled variant of FedAvg, and provide theoretical convergence guarantees in the general setting where the local data is imbalanced and heterogeneous. Armed with this result, we determine the caching strategies that minimize total wall-clock training time at a given convergence threshold for both stochastic and deterministic communication/computation delays. Through numerical experiments on real data traces, we show the advantage of our proposed scheme against several baselines, over both synthetic and real-world datasets.

In the rapidly evolving landscape of smart home automation, the potential of IoT devices is vast. In this realm, rules are the main tool utilized for this automation, which are predefined conditions or triggers that establish connections between devices, enabling seamless automation of specific processes. However, one significant challenge researchers face is the lack of comprehensive datasets to explore and advance the field of smart home rule recommendations. These datasets are essential for developing and evaluating intelligent algorithms that can effectively recommend rules for automating processes while preserving the privacy of the users, as it involves personal information about users' daily lives. To bridge this gap, we present the Wyze Rule Dataset, a large-scale dataset designed specifically for smart home rule recommendation research. Wyze Rule encompasses over 1 million rules gathered from a diverse user base of 300,000 individuals from Wyze Labs, offering an extensive and varied collection of real-world data. With a focus on federated learning, our dataset is tailored to address the unique challenges of a cross-device federated learning setting in the recommendation domain, featuring a large-scale number of clients with widely heterogeneous data. To establish a benchmark for comparison and evaluation, we have meticulously implemented multiple baselines in both centralized and federated settings. Researchers can leverage these baselines to gauge the performance and effectiveness of their rule recommendation systems, driving advancements in the domain. The Wyze Rule Dataset is publicly accessible through HuggingFace's dataset API.

Methods for training models on graphs distributed across multiple clients have recently grown in popularity, due to the size of these graphs as well as regulations on keeping data where it is generated. However, the cross-client edges naturally exist among clients. Thus, distributed methods for training a model on a single graph incur either significant communication overhead between clients or a loss of available information to the training. We introduce the Federated Graph Convolutional Network (FedGCN) algorithm, which uses federated learning to train GCN models for semi-supervised node classification with fast convergence and little communication. Compared to prior methods that require extra communication among clients at each training round, FedGCN clients only communicate with the central server in one pre-training step, greatly reducing communication costs and allowing the use of homomorphic encryption to further enhance privacy. We theoretically analyze the tradeoff between FedGCN's convergence rate and communication cost under different data distributions. Experimental results show that our FedGCN algorithm achieves better model accuracy with 51.7\% faster convergence on average and at least 100$\times$ less communication compared to prior work.

Internet of Things (IoT) technologies have enabled numerous data-driven mobile applications and have the potential to significantly improve environmental monitoring and hazard warnings through the deployment of a network of IoT sensors. However, these IoT devices are often power-constrained and utilize wireless communication schemes with limited bandwidth. Such power constraints limit the amount of information each device can share across the network, while bandwidth limitations hinder sensors’ coordination of their transmissions. In this work, we formulate the communication planning problem of IoT sensors that track the state of the environment. We seek to optimize sensors’ decisions in collecting environmental data under stringent resource constraints. We propose a multi-agent reinforcement learning (MARL) method to find the optimal communication policies for each sensor that maximize the tracking accuracy subject to the power and bandwidth limitations. MARL learns and exploits the spatial-temporal correlation of the environmental data at each sensor’s location to reduce the redundant reports from the sensors. Experiments on wildfire spread with LoRA wireless network simulators show that our MARL method can learn to balance the need to collect enough data to predict wildfire spread with unknown bandwidth limitations.

Deep learning (DL) powered real-time applications usually need continuous training using data streams generated geographically. Enabling data offloading among computation nodes through model training is promising to mitigate the problem that devices generating large datasets may have low computation capability. However, offloading can compromise model convergence and incur communication costs, which must be balanced with the cost spent on computation and model synchronization. Therefore, this paper proposes EdgeC3, a novel framework that can optimize the frequency of model aggregation and dynamic offloading for continuously generated data streams, navigating the trade-off between long-term accuracy and cost. We first provide a new error bound to capture the impacts of data dynamics that are varying over time and heterogeneous across devices. Based on the bound, we design a two-timescale online optimization framework. We periodically learn the synchronization frequency to adapt with uncertain future offloading and network changes. In the finer timescale, we manage online offloading by extending Lyapunov optimization techniques to handle an unconventional setting, where our long-term global constraint can have abruptly changed aggregation frequencies that are decided in the longer timescale. Finally, we theoretically prove the convergence of EdgeC3 by integrating the coupled effects of our two-timescale decisions, and we demonstrate its advantage through extensive experiments.

To defray the increasingly massive costs of running large machine learning workloads, much work has proposed running them on preemptible cloud instances, a discount tier of virtual machine rentals that may be interrupted at the cloud provider's discretion. This work, however, largely ignores the fact that much data used for machine learning comes from streams of diverse sources, e.g., wirelessly connected cameras or hospital health records. Processing datastreams on preemptible instances presents new challenges: processing data as they arrive may engender bottlenecks when scaling the system to handle higher throughput, particularly if the instances are frequently interrupted. Ours is the first work to design, analyze, and optimize a system that uses a set of datastreams to train a machine learning model on preemptible instances. Our system, DOLL, uses queueing and batching to parallelize and scale SGD (stochastic gradient descent)-based optimizers to large numbers of workers and datastreams, as well as heterogeneous data arrival rates across streams. Expected error convergence guarantees are then derived for DOLL's training process. We use this guarantee to optimize the cost of requisitioning preemptible and on-demand instances given an error target and wall-clock time deadline; this optimization is validated on experiments demonstrating substantial cost savings with little impact on model error.

Edge computing capabilities in 5G wireless networks promise to benefit mobile users: computing tasks can be offloaded from user devices to nearby edge servers, reducing users’ experienced latencies. Few works have addressed how this offloading should handle long-term user mobility: as devices move, they will need to offload to different edge servers, which may require migrating data or state information from one edge server to another. In this paper, we introduce MoDEMS, a system model and architecture that provides a rigorous theoretical framework and studies the challenges of such migrations to minimize the service provider cost and user latency. We show that this cost minimization problem can be expressed as an integer linear programming problem, which is hard to solve due to resource constraints at the servers and unknown user mobility patterns. We show that finding the optimal migration plan is in general NP-hard, and we propose alternative heuristic solution algorithms that perform well in both theory and practice. We finally validate our results with real user mobility traces, ns-3 simulations, and an LTE testbed experiment. Migrations reduce the latency experienced by users of edge applications by 33% compared to previously proposed migration approaches.

Today’s Internet must support applications with increasingly dynamic and heterogeneous connectivity requirements, such as video streaming and the Internet of Things. Yet current network management practices generally rely on pre-specified network configurations, which may not be able to cope with dynamic application needs. Moreover, even the best-specified policies will find it difficult to cover all possible scenarios, given applications’ increasing heterogeneity and dynamic network conditions, e.g., on volatile wireless links. In this work, we instead propose a model-free learning approach to find the optimal network policies for current network flow requirements. This approach is attractive as comprehensive models do not exist for how different policy choices affect flow performance under changing network conditions. However, it can raise new challenges for online learning algorithms: policy configurations can affect the performance of multiple flows sharing the same network resources, and this performance coupling limits the scalability and optimality of existing online learning algorithms. In this work, we extend multi-armed bandit frameworks to propose new online learning algorithms for protocol selection with provably sublinear regret under certain conditions. We validate the optimality and scalability of our algorithms through data-driven simulations and testbed experiments. (An extended abstract of this work was accepted by IEEE ICNP as a short paper Zhanget al. (2019)).

We consider the problem of predicting link formation in Social Learning Networks (SLN), a type of social network that forms when people learn from one another through structured interactions. While link prediction has been studied for general types of social networks, the evolution of SLNs over their lifetimes coupled with their dependence on which topics are being discussed presents new challenges for this type of network. To address these challenges, we develop a series of autonomous link prediction methodologies that utilize spatial and time-evolving network architectures to pass network state between space and time periods, and that models over three types of SLN features updated in each period: neighborhood-based (e.g., resource allocation), path-based (e.g., shortest path), and post-based (e.g., topic similarity). Through evaluation on six real-world datasets from Massive Open Online Course (MOOC) discussion forums and from Purdue University, we find that our method obtains substantial improvements over Bayesian models, linear classifiers, and graph neural networks, with AUCs typically above 0.91 and reaching 0.99 depending on the dataset. Our feature importance analysis shows that while neighborhood and path-based features contribute the most to the results, post-based features add additional information that may not always be relevant for link prediction. The code and four of the datasets used in this work are available athttps://github.com/Jess-jpg-txt/sln-learning.

Traditionally, clustered federated learning groups clients with the same data distribution into a cluster, so that every client is uniquely associated with one data distribution and helps train a model for this distribution. We relax this hard association assumption to soft clustered federated learning, which allows every local dataset to follow a mixture of multiple source distributions. We propose FedSoft, which trains both locally personalized models and high-quality cluster models in this setting. FedSoft limits client workload by using proximal updates to require the completion of only one optimization task from a subset of clients in every communication round. We show, analytically and empirically, that FedSoft effectively exploits similarities between the source distributions to learn personalized and cluster models that perform well.

We study the problem of learning representations that are private yet informative i.e., provide information about intended "ally" targets while hiding sensitive "adversary" attributes. We propose Exclusion-Inclusion Generative Adversarial Network (EIGAN), a generalized private representation learning (PRL) architecture that accounts for multiple ally and adversary attributes unlike existing PRL solutions. While centrally-aggregated dataset is a prerequisite for most PRL techniques, data in real-world is often siloed across multiple distributed nodes unwilling to share the raw data because of privacy concerns. We address this practical constraint by developing D-EIGAN, the first distributed PRL method that learns representations at each node without transmitting the source data. We theoretically analyze the behavior of adversaries under the optimal EIGAN and D-EIGAN encoders and the impact of dependencies among ally and adversary tasks on the optimization objective. Our experiments on various datasets demonstrate the advantages of EIGAN in terms of performance, robustness, and scalability. In particular, EIGAN outperforms the previous state-of-the-art by a significant accuracy margin ($47%$ improvement), and D-EIGAN’s performance is consistently on par with EIGAN under different network settings.

Online influence maximization has attracted much attention as a way to maximize influence spread through a social network while learning the values of unknown network parameters. Most previous works focus on single-item diffusion. In this paper, we introduce a new Online Competitive Influence Maximization (OCIM) problem, where two competing items (e.g., products, news stories) propagate in the same network and influence probabilities on edges are unknown. We adopt a combinatorial multi-armed bandit (CMAB) framework for OCIM, but unlike the non-competitive setting, the important monotonicity property (influence spread increases when influence probabilities on edges increase) no longer holds due to the competitive nature of propagation, which brings a significant new challenge to the problem. We provide a nontrivial proof showing that the Triggering Probability Modulated (TPM) condition for CMAB still holds in OCIM, which is instrumental for our proposed algorithms OCIM-TS and OCIM-OFU to achieve sublinear Bayesian and frequentist regret, respectively. We also design an OCIM-ETC algorithm that requires less feedback and easier offline computation, at the expense of a worse frequentist regret bound. Experimental evaluations demonstrate the effectiveness of our algorithms.

The recent advances of conversational recommendations provide a promising way to efficiently elicit users' preferences via conversational interactions. To achieve this, the recommender system conducts conversations with users, asking their preferences for different items or item categories. Most existing conversational recommender systems for cold-start users utilize a multi-armed bandit framework to learn users' preference in an online manner. However, they rely on a pre-defined conversation frequency for asking about item categories instead of individual items, which may incur excessive conversational interactions that hurt user experience. To enable more flexible questioning about key-terms, we formulate a new conversational bandit problem that allows the recommender system to choose either a key-term or an item to recommend at each round and explicitly models the rewards of these actions. This motivates us to handle a new exploration-exploitation (EE) trade-off between key-term asking and item recommendation, which requires us to accurately model the relationship between key-term and item rewards. We conduct a survey and analyze a real-world dataset to find that, unlike assumptions made in prior works, key-term rewards are mainly affected by rewards of representative items. We propose two bandit algorithms, Hier-UCB and Hier-LinUCB, that leverage this observed relationship and the hierarchical structure between key-terms and items to efficiently learn which items to recommend. We theoretically prove that our algorithm can reduce the regret bound's dependency on the total number of items from previous work. We validate our proposed algorithms and regret bound on both synthetic and real-world data.

Edge computing capabilities in 5G wireless networks promise to benefit mobile users: computing tasks can be offloaded from user devices to nearby edge servers, reducing users’ experienced latencies. Few works have addressed how this offloading should handle long-term user mobility: as devices move, they will need to offload to different edge servers, which may require migrating data or state information from one edge server to another. In this paper, we introduce MoDEMS, a system model and architecture that provides a rigorous theoretical framework and studies the challenges of such migrations to minimize the service provider cost and user latency. We show that this cost minimization problem can be expressed as an integer linear programming problem, which is hard to solve due to resource constraints at the servers and unknown user mobility patterns. We show that finding the optimal migration plan is in general NP-hard, and we propose alternative heuristic solution algorithms that perform well in both theory and practice. We finally validate our results with real user mobility traces, ns-3 simulations, and an LTE testbed experiment. Migrations reduce the latency experienced by users of edge applications by 33% compared to previously proposed migration approaches.

We study a sequential resource allocation problem where, at each round, the decision-maker needs to allocate its limited budget among different available entities. In doing so, the decision-maker obtains the reward for each entity in that round. The goal of the decision-maker is to maximize the expected cumulative reward or equivalently minimize cumulative regret over a total of T rounds. Sequential resource allocation can be modeled as a combinatorial bandit by viewing the allocation of a budget to an entity as a base arm. In the context of resource allocation, the rewards received under different budget allocations are likely to be correlated. We propose a novel correlated combinatorial bandit framework that explicitly models such correlations. We develop a novel Correlated-UCB algorithm for online resource allocation, which yields significantly reduced regret relative to correlation-agnostic algorithms. In certain cases, our proposed algorithm even achieves bounded regret, which is an order-wise reduction in the regret relative to the correlation-agnostic approach, which incurs logarithmic regret under all scenarios. We validate these performance gains through experiments on several applications such as online power allocation across wireless channels, job scheduling in multi-server systems and online channel assignment for the slotted ALOHA protocol.

In this paper, we study the combinatorial semi-bandits (CMAB) and focus on reducing the dependency of the batch-size $K$ in the regret bound, where $K$ is the total number of arms that can be pulled or triggered in each round. First, for the setting of CMAB with probabilistically triggered arms (CMAB-T), we discover a novel (directional) triggering probability and variance modulated (TPVM) condition that can replace the previously-used smoothness condition for various applications, such as cascading bandits, online network exploration and online influence maximization. Under this new condition, we propose a BCUCB-T algorithm with variance-aware confidence intervals and conduct regret analysis which reduces the $O(K)$ factor to $O(\log K)$ or $O(\log^2 K)$ in the regret bound, significantly improving the regret bounds for the above applications. Second, for the setting of non-triggering CMAB with independent arms, we propose a SESCB algorithm which leverages on the non-triggering version of the TPVM condition and completely removes the dependency on $K$ in the leading regret. As a valuable by-product, the regret analysis used in this paper can improve several existing results by a factor of $O(\log K)$. Finally, experimental evaluations show our superior performance compared with benchmark algorithms in different applications.

Many Cyber-Physical Systems (CPS) have timing constraints that must be met by the cyber components (software and the network) to ensure safety. It is a tedious job to check if a CPS meets its timing requirement especially when it is distributed and the software and/or the underlying computing platforms are complex. Furthermore, the system design is brittle since a timing failure can still happen (e.g., network failure, soft error bit flip). In this article, we propose a new design methodology calledPlan Bwhere timing constraints of the CPS are monitored at runtime, and a proper backup routine is executed when a timing failure happens to ensure safety. We provide a model on how to express the desired timing behavior using a set of timing constructs in a C/C++ code and how to efficiently monitor them at the runtime. We showcase the effectiveness of our approach by conducting experiments on three case studies: (1) the full software stack for autonomous driving (Apollo), (2) a multi-agent system with 1/10th-scale model robots, and (3) a quadrotor for search and rescue application. We show that the system remains safe and stable even when intentional faults are injected to cause a timing failure. We also demonstrate that the system can achieve graceful degradation when a less extreme timing failure happens.

Due to the massive size of the neural network models and training datasets used in machine learning today, it is imperative to distribute stochastic gradient descent (SGD) by splitting up tasks such as gradient evaluation across multiple worker nodes. However, running distributed SGD can be prohibitively expensive because it may require specialized computing resources such as GPUs for extended periods of time. We propose cost-effective strategies to exploit volatile cloud instances that are cheaper than standard instances, but may be interrupted by higher priority workloads. To the best of our knowledge, this work is the first to quantify how variations in the number of active worker nodes (as a result of preemption) affect SGD convergence and the time to train the model. By understanding these trade-offs between preemption probability of the instances, accuracy, and training time, we are able to derive practical strategies for configuring distributed SGD jobs on volatile instances such as Amazon EC2 spot instances and other preemptible cloud instances. Experimental results show that our strategies achieve good training performance at substantially lower cost.

Mobile Augmented Reality (AR), which overlays digital content on the real-world scenes surrounding a user, is bringing immersive interactive experiences where the real and virtual worlds are tightly coupled. To enable seamless and precise AR experiences, an image recognition system that can accurately recognize the object in the camera view with low system latency is required. However, due to the pervasiveness and severity of image distortions, an effective and robust image recognition solution for “in the wild” mobile AR is still elusive. In this article, we present CollabAR, an edge-assisted system that provides distortion-tolerant image recognition for mobile AR with imperceptible system latency . CollabAR incorporates both distortion-tolerant and collaborative image recognition modules in its design. The former enables distortion-adaptive image recognition to improve the robustness against image distortions, while the latter exploits the spatial-temporal correlation among mobile AR users to improve recognition accuracy. Moreover, as it is difficult to collect a large-scale image distortion dataset, we propose a Cycle-Consistent Generative Adversarial Network-based data augmentation method to synthesize realistic image distortion. Our evaluation demonstrates that CollabAR achieves over 85% recognition accuracy for “in the wild” images with severe distortions, while reducing the end-to-end system latency to as low as 18.2 ms.

We study the problem of clustering nodes in a dynamic graph, where the connections between nodes and nodes' cluster memberships may change over time, e.g., due to community migration. We first propose a dynamic stochastic block model that captures these changes, and a simple decay-based clustering algorithm that clusters nodes based on weighted connections between them, where the weight decreases at a fixed rate over time. This decay rate can then be interpreted as signifying the importance of including historical connection information in the clustering. However, the optimal decay rate may differ for clusters with different rates of turnover. We characterize the optimal decay rate for each cluster and propose a clustering method that achieves almost exact recovery of the true clusters. We then demonstrate the efficacy of our clustering algorithm with optimized decay rates on simulated graph data. Recurrent neural networks (RNNs), a popular algorithm for sequence learning, use a similar decay-based method, and we use this insight to propose two new RNN-GCN (graph convolutional network) architectures for semi-supervised graph clustering. We finally demonstrate that the proposed architectures perform well on real data compared to state-of-the-art graph clustering algorithms.

Traditional federated learning algorithms impose strict requirements on the participation rates of devices, which limit the potential reach of federated learning. This paper extends the current learning paradigm to include devices that may become inactive, compute incomplete updates, and depart or arrive in the middle of training. We derive analytical results to illustrate how allowing more flexible device participation can affect the learning convergence when data is not independently and identically distributed (non-IID). We then propose a new federated aggregation scheme that converges even when devices may be inactive or return incomplete updates. We also study how the learning process can adapt to early departures or late arrivals, and analyze their impacts on the convergence.

Serverless computing is a rapidly growing paradigm in the cloud industry that envisions functions as the computational building blocks of an application. Instead of forcing the application developer to provision cloud resources for their application, the cloud provider provisions the required resources for each function "under the hood." In this work, we envision virtual serverless providers (VSPs) to aggregate serverless offerings. In doing so, VSPs allow developers (and businesses) to get rid of vendor lock-in problems and exploit pricing and performance variation across providers by adaptively utilizing the best provider at each time, forcing the providers to compete to offer cheaper and superior services. We discuss the merits of a VSP and show that serverless systems are well-suited to cross-provider aggregation, compared to virtual machines. We propose a VSP system architecture and implement an initial version. Using experimental evaluations, our preliminary results show that a VSP can improve maximum sustained throughput by 1.2x to 4.2x, reduces SLO violations by 98.8%, and improves the total invocations' costs by 54%.

Graph Convolutional Networks (GCNs) are a popular method from graph representation learning that have proved effective for tasks like node classification. Recent variants on traditional GCN models aim to classify nodes in dynamic graphs whose topologies and node attributes change over time, e.g., social networks with dynamic relationships. These works, however, do not fully address the challenge of flexibly assigning different importance to snapshots of the graph at different times, which depending on the graph dynamics may have more or less predictive power on the labels. We address this challenge by proposing a new method, GCN-SE, that attaches a set of learnable attention weights to graph snapshots at different times, inspired by Squeeze and Excitation Net (SE-Net). We show that GCNSE outperforms previously proposed node classification methods on a variety of graph datasets. To verify the effectiveness of the attention weight in determining the importance of different graph snapshots, we adapt perturbation-based methods from the field of explainable machine learning to graphical settings and evaluate the correlation between the attention weights learned by GCN-SE and the importance of different snapshots over time.

Edge computing systems benefit from knowledge of short-term mobility from 5G technologies, as tasks offloaded from user devices can be placed at the edge to reduce their latencies. However, as devices move, they will need to offload their tasks to different edge servers, which may require migrating data from one edge server to another. In this paper, we introduce MoDEMS, a system architecture through which we provide a rigorous theoretical framework to study the challenges of such migrations to minimize the service provider cost and user latency. We show that this cost minimization problem can be expressed as an integer linear programming problem, which is challenging to solve due to resource constraints at the servers and unknown user mobility patterns. We show that finding the optimal migration plan is in general NP-hard, and we propose alternative heuristic solution algorithms. We finally validate our results with realistic user mobility traces.

Urban environments are the most prevalent application scenario for the Internet of Things (IoT). In this context, effective data collection and forwarding to a cloud (or edge) server are particularly important. This work leverages opportunistic data collection based on the mobile crowd sourcing (MCS) paradigm for time-sensitive IoT applications. Specifically, it introduces an incentive mechanism for the crowd to collect data that are valuable to data consumers in terms of regions of interest and time constraints. The proposed approach successfully incorporates the willingness of the crowd to participate in the data collection as part of the related incentives. It also ensures collection of valuable data via selective user incentivization. Accordingly, a weighted social welfare maximization problem is defined for users to decide which sensors to visit subject to deadline constraints. Following the NP-hardness of the problem, an online heuristic algorithm is proposed for sensors to dynamically incentivize mobile users with a low message and time complexity. The proposed solution is shown to be effective for time-sensitive quality data collection through extensive simulations on realistic mobility traces. It significantly increases the overall social welfare as well as the amount of collected data compared to other approaches.

Federated learning allows distributed clients to train a shared machine learning model while preserving user privacy. In this framework, an operator recruits user devices (i.e., clients) to occasionally perform local iterations of the learning algorithm on their data. We propose the first work to theoretically analyze the resulting performance tradeoffs in deciding which clients to recruit for federated learning, complementing other works on the selection of recruited clients in each iteration. Specifically, we define and optimize the tradeoffs between both accuracy (training and testing) and efficiency (completion time and cost) metrics. We provide efficient solutions to this NP-Hard optimization problem, and verify the value of client recruitment in experiments on synthetic and real-world data. The results of this work can serve as guidelines for the real-world deployment of federated learning and an initial investigation of the client recruitment problem.

Fog computing promises to enable machine learning tasks to scale to large amounts of data by distributing processing across connected devices. Two key challenges to achieving this goal are (i) heterogeneity in devices’ compute resources and (ii) topology constraints on which devices communicate with each other. We address these challenges by developing a novel network-aware distributed learning methodology where devices optimally share local data processing and send their learnt parameters to a server for periodic aggregation. Unlike traditional federated learning, our method enables devices to offload their data processing tasks to each other, with these decisions optimized to trade off costs associated with data processing, offloading, and discarding. We analytically characterize the optimal data transfer solution under different assumptions on the fog network scenario, showing for example that the value of offloading is approximately linear in the range of computing costs in the network when the cost of discarding is modeled as decreasing linearly in the amount of data processed at each node. Our experiments on real-world data traces from our testbed confirm that our algorithms improve network resource utilization substantially without sacrificing the accuracy of the learned model, for varying distributions of data across devices. We also investigate the effect of network dynamics on model learning and resource costs.

We consider the stochastic multi-armed bandit (MAB) problem in a setting where a player can pay to pre-observe arm rewards before playing an arm in each round. Apart from the usual trade-off between exploring new arms to find the best one and exploiting the arm believed to offer the highest reward, we encounter an additional dilemma: pre-observing more arms gives a higher chance to play the best one, but incurs a larger cost. For the single-player setting, we design an Observe-Before-Play Upper Confidence Bound (OBP-UCB) algorithm for K arms with Bernoulli rewards, and prove a T-round regret upper bound O(K2log T). In the multi-player setting, collisions will occur when players select the same arm to play in the same round. We design a centralized algorithm, C-MP-OBP, and prove its T-round regret relative to an offline greedy strategy is upper bounded in O(K4/M2log T) for K arms and M players. We also propose distributed versions of the C-MP-OBP policy, called D-MP-OBP and D-MP-Adapt-OBP, achieving logarithmic regret with respect to collision-free target policies. Experiments on synthetic data and wireless channel traces show that C-MP-OBP and D-MP-OBP outperform random heuristics and offline optimal policies that do not allow pre-observations.

Data generated by increasingly pervasive and intelligent devices has led to an explosion in the use of machine learning (ML) and artificial intelligence, with ever more complex models trained to support applications in fields as diverse as healthcare, finance, and robotics. In order to train these models in a reasonable amount of time, the training is often distributed among multiple machines. However, paying for these machines (either by constructing a local cloud infrastructure or renting machines through an external provider such as Amazon AWS) is very costly. We propose to reduce these costs by creating a marketplace of computing resources designed to support distributed machine learning algorithms. Through our marketplace (coined “DeepMarket”), users can lend their spare computing resources (when not needed) or augment their resources with available DeepMarket machines to train their ML models. Such a marketplace directly provides several benefits for two groups of researchers: (i) ML researchers would be able to train their models with much reduced cost, and (ii) network economics researchers would be able to experiment with different compute pricing mechanisms. The focus of this Demo is to introduce the audience to DeepMarket and its user interface (named “PLUTO”). In particular, we will bring a few laptops with pre-installed PLUTO applications so that users can see how they can create an account on DeepMarket servers, lend their resource, borrow available resources, submit ML jobs, and retrieve the results. Our overall goal is to encourage the conference audience to install PLUTO on their own machines and create a user and developer community around DeepMarket.

In this paper, we propose SPARCLE, a novel scheduling system offering network-aware polynomial-time task assignment and resource allocation algorithms for stream processing applications in dispersed computing networks. In particular, we address two major challenges. The first one concerns the assignment of both computation and transport tasks comprising a stream processing application to computing nodes and communication links of the network, respectively, to maximize the application's processing rate. The second one concerns the resource allocation of multiple stream processing applications to satisfy their requested QoS. Our experimental results on a real image stream processing application and extensive simulations show that SPARCLE can increase the application's processing rate by 9 times and 3 times, compared to the cloud computing case and state-of-the-art algorithms, respectively.

Running intensive compute tasks across the fifth generation mobile network of edge devices introduces distributed computing challenges: edge devices are heterogeneous in the compute, storage, and communication capabilities; and can exhibit unpredictable straggler effects and failures. In this work, we propose an error-correcting-code inspired strategy to execute computing tasks in edge computing environments, which is designed to mitigate variability in response times and errors caused by edge devices' heterogeneity and lack of reliability. Unlike prior coding approaches, we incorporate partially unfinished coded tasks into our computation recovery, which allows us to achieve smooth performance degradation with low-complexity decoding when the coded tasks are run on edge devices with a fixed deadline. By further carrying out coding on edge devices as well as a master node, the proposed computing scheme also alleviates communication bottlenecks during data shuffling and is amenable to distributed implementation in a highly variable and limited network. Such distributed encoding forces us to solve new decoding challenges. Using a representative implementation based on federated multi-task learning frameworks, extensive performance simulations are carried out, which demonstrate that the proposed strategy offers significant gains in latency and accuracy over conventional coded computing schemes.

Deep neural networks (DNN) are the de-facto solution behind many intelligent applications of today, ranging from machine translation to autonomous driving. DNNs are accurate but resource-intensive, especially for embedded devices such as mobile phones and smart objects in the Internet of Things. To overcome the related resource constraints, DNN inference is generally offloaded to the edge or to the cloud. This is accomplished by partitioning the DNN and distributing computations at the two different ends. However, most of existing solutions simply split the DNN into two parts, one running locally or at the edge, and the other one in the cloud. In contrast, this article proposes a technique to divide a DNN in multiple partitions that can be processed locally by end devices or offloaded to one or multiple powerful nodes, such as in fog networks. The proposed scheme includes both an adaptive DNN partitioning scheme and a distributed algorithm to offload computations based on a matching game approach. Results obtained by using a self-driving car dataset and several DNN benchmarks show that the proposed solution significantly reduces the total latency for DNN inference compared to other distributed approaches and is 2.6 to 4.2 times faster than the state of the art.

Recent growth in user demand for mobile data has strained mobile network infrastructure. One possible solution is to use mobile (i.e., moving) devices to supplement existing infrastructure according to users' needs at different times and locations. For instance, vehicles can be used as communication relays or computation points. However, it is unclear how much value these devices add relative to their deployment costs: they may, for instance, interfere with existing network infrastructure, limiting the potential benefits. We take the first step towards quantifying the value of this supplemental infrastructure by examining the use case of mobile caches. We consider a network operator using both mobile (e.g., vehicular) and stationary (small cell) caches, and find the optimal amount of both types of caches under time- and location-varying user demands, as a function of the cache prices. In doing so, we account for interference between users' connections to the different caches, which requires solving a non-convex optimization problem. We show that there exists a threshold price above which no vehicular caches are purchased. Moreover, as the network operator's budget increases, vehicular caching yields little additional value beyond that provided by small cell caches. These results may help network operators and cache providers find conditions under which vehicles add value to existing networks.

Fog computing promises to enable machine learning tasks to scale to large amounts of data by distributing processing across connected devices. Two key challenges to achieving this are (i) heterogeneity in devices' compute resources and (ii) topology constraints on which devices can communicate. We are the first to address these challenges by developing a network-aware distributed learning optimization methodology where devices process data for a task locally and send their learnt parameters to a server for aggregation at certain time intervals. Unlike traditional federated learning frameworks, our method enables devices to offload their data processing tasks, with these decisions determined through a convex data transfer optimization problem that trades off costs associated with devices processing, offloading, and discarding data points. We analytically characterize the optimal data transfer solution for different fog network topologies, showing for example that the value of a device offloading is approximately linear in the range of computing costs in the network. Our subsequent experiments on both synthetic and real-world datasets we collect confirm that our algorithms are able to improve network resource utilization substantially without sacrificing the accuracy of the learned model.

Due to the massive size of the neural network models and training datasets used in machine learning today, it is imperative to distribute stochastic gradient descent (SGD) by splitting up tasks such as gradient evaluation across multiple worker nodes. However, running distributed SGD can be prohibitively expensive because it may require specialized computing resources such as GPUs for extended periods of time. We propose cost-effective strategies to exploit volatile cloud instances that are cheaper than standard instances, but may be interrupted by higher priority workloads. To the best of our knowledge, this work is the first to quantify how variations in the number of active worker nodes (as a result of preemption) affects SGD convergence and the time to train the model. By understanding these trade-offs between preemption probability of the instances, accuracy, and training time, we are able to derive practical strategies for configuring distributed SGD jobs on volatile instances such as Amazon EC2 spot instances and other preemptible cloud instances. Experimental results show that our strategies achieve good training performance at substantially lower cost.

Mobile Augmented Reality (AR), which overlays digital content on the real-world scenes surrounding a user, is bringing immersive interactive experiences where the real and virtual worlds are tightly coupled. To enable seamless and precise AR experiences, an image recognition system that can accurately recognize the object in the camera view with low system latency is required. However, due to the pervasiveness and severity of image distortions, an effective and robust image recognition solution for mobile AR is still elusive. In this paper, we present CollabAR, an edge-assisted system that provides distortion-tolerant image recognition for mobile AR with imperceptible system latency. CollabAR incorporates both distortion-tolerant and collaborative image recognition modules in its design. The former enables distortion-adaptive image recognition to improve the robustness against image distortions, while the latter exploits the ‘spatial-temporal’ correlation among mobile AR users to improve recognition accuracy. We implement CollabAR on four different commodity devices, and evaluate its performance on two multi-view image datasets. Our evaluation demonstrates that CollabAR achieves over 96% recognition accuracy for images with severe distortions, while reducing the end-to-end system latency to as low as 17.8ms for commodity mobile devices.

Vehicular mobile crowdsensing (MCS) enables many smart city applications. Ridesharing vehicle fleets provide promising solutions to MCS due to the advantages of low cost, easy maintenance, high mobility, and long operational time. However, as nondedicated mobile sensing platforms, the first priorities of these vehicles are delivering passengers, which may lead to poor sensing coverage quality. Therefore, to help MCS derive good (large and balanced) sensing coverage quality, an actuation system is required to dispatch vehicles with a limited amount of monetary budget. This article presents PAS, a prediction-based actuation system for city-wide ridesharing vehicular MCS to achieve optimal sensing coverage quality with a limited budget. In PAS, two prediction models forecast probabilities of potential near-future vehicle routes and ride requests across the city. Based on prediction results, a prediction-based actuation planning algorithm is proposed to decide which vehicles to actuate and the corresponding routes. Experiments on city-scale deployments and physical feature-based simulations show that our PAS achieves up to 40% more improvement in sensing coverage quality and up to 20% higher ride request matching rate than baselines. In addition, to achieve a similar level of sensing coverage quality as the baseline, our PAS only needs 10% budget.

The growing demand for mobile data and the evolution of next-generation networks, particularly fifth-generation (5G) wireless networks, has called for new approaches to pricing and managing the limited capacity of existing network resources and infrastructures. In particular, emerging mobile applications like autonomous vehicles, augmented/virtual reality, and more broadly the Internet-of-Things will have heterogeneous demand patterns and service requirements, raising questions on how they should pay for their data usage and how next-generation networks can meet their demands with limited resources. Several recent policy changes and regulatory initiatives have been proposed to address the shift in demands due to next-generation networks and technologies. These include the FCC’s “5G Fast Plan,” which outlines strategies for modifying spectrum policies, infrastructure policies, and existing regulations, in light of emerging 5G technologies. This plan has included the rollback of net neutrality rules in June 2018, allowing broadband providers to offer a wider variety of service options.

Vehicular crowd sensing systems are designed to achieve large spatio-temporal sensing coverage with low-cost in deployment and maintenance. For example, taxi platforms can be utilized for sensing city-wide air quality. However, the goals of vehicle agents are often inconsistent with the goal of the crowdsourcer. Vehicle agents like taxis prioritize searching for passenger ride requests (defined as task requests), which leads them to gather in busy regions. In contrast, sensing systems often need to sample data over the entire city with a desired distribution (e.g., Uniform distribution, Gaussian Mixture distribution, etc.) to ensure sufficient spatio-temporal information for further analysis. This inconsistency decreases the sensing coverage quality and thus impairs the quality of the collected information. A simple approach to reduce the inconsistency is to greedily incentivize the vehicle agents to different regions. However, incentivization brings challenges, including the heterogeneity of desired target distributions, limited budget to incentivize more vehicle agents, and the high computational complexity of optimizing incentivizing strategies. To this end, we present a vehicular crowd sensing system to efficiently incentivize the vehicle agents to match the sensing distribution of the sampled data to the desired target distribution with a limited budget. To make the system flexible to various desired target distributions, we formulate the incentivizing problem as a new type of non-linear multiple-choice knapsack problem, with the dissimilarity between the collected data distribution and the desired distribution as the objective function. To utilize the budget efficiently, we design a customized incentive by combining monetary incentives and potential task (ride) requests at the destination. Meanwhile, an efficient optimization algorithm, iLOCuS, is presented to plan the incentivizing policy for vehicle agents to decompose the sensing distribution into two distinct levels: time-location level and vehicle level, to approximate the optimal solution iteratively and reduce the dissimilarity objective. Our experimental results based on real-world data show that our system can reduce up to 26.99 percent of the dissimilarity between the sensed and target distributions compared to benchmark methods.

Leading cloud providers recently introduced a new instance type named burstable instances to better match the time-varying workloads of tenants and further reduce their costs. In the research community, however, little has been done to understand burstable instances from a theoretical perspective. This paper presents the first unified framework to model, analyze, and optimize the operation of burstable instances. Specifically, we model the resource provisioning of burstable instances, identify key performance metrics, and derive the analytical performance given the resource provisioning decisions. We then characterize the equilibrium behind tenants' responses to the prices offered for different burstable instance service classes, taking into account the impact of tenants' actions on the performance achieved by each service class. In addition, we investigate how a cloud provider can leverage knowledge of this equilibrium to find the prices that maximize its total revenue. Finally, we validate our framework on real traces and demonstrate its usage to price burstable offerings in a public cloud.

Growing mobile data usage has led to end users paying substantial data costs, while Internet service providers (ISPs) struggle to upgrade their networks to keep up with demand and maintain high quality-of-service (QoS). This problem is particularly severe for smaller ISPs with less capital. Instead of simply upgrading their network infrastructure, ISPs can pool their networks to provide a good QoS and attract more users. Such a vISP (virtual ISP), for example, Google's Project Fi, allows users to access any of its partner ISPs' networks. We provide the first systematic analysis of a vISP's economic impact, showing that the vISP provides a viable solution for smaller ISPs attempting to attract more users, but may not maintain a positive profit if users' data demands evolve. To do so, we consider users' decisions of whether to defect from their current ISP to the vISP, as well as existing ISPs' decisions on whether to partner with the vISP. We derive the vISP's dependence on user behavior and partner ISPs: users with very light or very heavy usage are the most likely to defect, while ISPs with heavy-usage customers can benefit from declining to partner with the vISP. Our analytical results are verified with extensive numerical simulations.

Emerging applications like virtual reality (VR), augmented reality (AR), and 360-degree video aim to exploit the unprecedentedly low latencies promised by technologies like the tactile Internet and mobile 5G networks. Yet these promises are still unrealized. In order to fulfill them, it is crucial to understand where packet delays happen, which impacts protocol performance such as throughput and latency. In this work, we empirically find that sender-side protocol stack delays can cause high end-to-end latencies, though existing solutions primarily address network delays. Unfortunately, however, current latency diagnosis tools cannot even distinguish between delays on network links and delays in the end hosts. To close this gap, we present ELEMENT, a latency diagnosis framework that decomposes end-to-end TCP latency into endhost and network delays, without requiring admin privileges at the sender or receiver.

Ensuring high availability for applications despite unpredictable cloud component failure events is a well-known problem in managing cloud infrastructure. One proposed solution uses a VM redundancy approach, reserving cloud resources for backup VMs that can substitute for primary ones in case of a failure event. However, this solution decreases the cloud resource utilization, since the backup resources usually remain idle. In this paper, we propose ECHO, a cloud resource management system that overbooks these backup VMs by optimizing the overbooking rate tradeoff between maximizing the cloud resource utilization, and thus maximizing the cloud provider's revenue; and improving application availability, thus satisfying users. Specifically, ECHO first obtains the optimal overbooking rate required to achieve a cloud provider's desired resource utilization level. It then computes the optimal (required) number of backup VMs that are required to maintain a given application availability level. Our extensive experimental and simulation results show that using ECHO can increase the number of accepted applications with satisfied availability by about 30%, while increasing the defined resource utilization at the same time.

Today’s Internet must support applications with increasingly dynamic and heterogeneous connectivity requirements, such as video streaming and the Internet of Things. Yet current network management practices generally rely on pre-specified flow configurations, which cannot cover all possible scenarios. In this work, we instead propose a model-free learning approach to automatically optimize the policies for heterogeneous network flows. This approach is attractive as no existing comprehensive models quantify how different policy choices affect flow performance under dynamically changing network conditions. We extend multi-armed bandit frameworks to propose new online learning algorithms for protocol selection, addressing the challenge of policy configurations affecting the performance of multiple flows sharing the same network resources. This performance coupling limits the scalability and optimality of existing online learning algorithms. We theoretically prove that our algorithm achieves a sublinear regret and demonstrate its optimality and scalability through data-driven simulations.

Leading cloud providers recently introduced a new instance type named burstable instances to better match the time-varying workloads of tenants and further reduce their costs. In the research community, however, little has been done to understand burstable instances from a theoretical perspective. This paper presents the first unified framework to model, analyze, and optimize the operation of burstable instances. Specifically, we model the resource provisioning of burstable instances in different service classes, identify key performance metrics, and derive the performance given the resource provisioning decisions. We then characterize the equilibrium behind tenants' responses to the prices offered for different burstable instance service classes, taking into account the impact of tenants' actions on the performance achieved by each service class. In addition, we investigate how a cloud provider can leverage the knowledge of this equilibrium to find the prices that maximize its total revenue. Finally, we validate our framework on real traces and demonstrate its usage to price a public cloud.

Urban environments are a particularly important application scenario for the Internet of Things (IoT). These environments are usually dense and dynamic; in contrast, IoT devices are resource-constrained, thus making reliable data collection and scalable coordination a challenge. This work leverages the fog networking paradigm to devise a multi-tier data offloading protocol suitable for diverse data-centric applications in urban IoT scenarios. Specifically, it takes advantage of heterogeneity in the network so that sensors can collaboratively offload data to each other or to mobile gateways. Second, it evaluates the performance of this offloading process through the amount of data successfully reported to the cloud. In detail, it provides an analytical characterization of data drop-off rates as a random process and derives a light-weight yet efficient method for collaborative data offloading. Finally, it shows that the proposed fog-based solution significantly decreases the data drop-off rate through both analysis and extensive trace-driven simulations based on human mobility data from real urban settings.

Mobile crowd sensing (MCS) collects city-scale sensing data with low cost and high efficiency. One important goal of MCS is to ensure high quality of sensing coverage to provide sufficient information to data analysis end. However, the goal of the MCS may be inconsistent with the goal of vehicles. This inconsistency between goals results in a bad sensing coverage and decreases the quality of the collected information. Key challenges to resolve this inconsistency include the heterogeneous target desired spatio-temporal distributions, limited budget constraining the ability to incentivize more taxis, and high computational complexity.

This paper presents a fully distributed scheduling framework called CASTLE (Client-side Adaptive Scheduler That minimizes Load and Energy), which jointly optimizes the spectral efficiency of cellular networks and battery consumption of smart devices. To do so, we focus on scenarios when many smart devices compete for cellular resources in the same base station: spreading out transmissions over time so that only a few devices transmit at once improves both spectral efficiency and battery consumption. To this end, we devise two novel features in CASTLE. First, we explicitly consider inter-cell interference for accurate cellular load estimation. Based on our observations, we exploit the RSRQ (Reference Signal Received Quality) and SINR as features in a machine learning algorithm to accurately estimate the cellular load. Second, we propose a fully distributed scheduling algorithm that coordinates transmissions between clients based on the locally estimated load level at each client. Our formulation for minimizing battery consumption at each device leads to an optimized backoff-based algorithm that fits practical environments. To evaluate these features, we prototype a complete LTE system testbed consisting of mobile devices, eNodeBs, EPC (Evolved Packet Core) and application servers. Our comprehensive experimental results show that CASTLE's load estimation is up to 91% accurate, and that CASTLE achieves higher spectral efficiency with less battery consumption, compared to existing centralized scheduling algorithms as well as a distributed CSMA-like protocol. Furthermore, we develop a light-weight SDK that can expedite the deployment of CASTLE into smart devices and evaluate it in a commercial LTE network.

We present the demonstration of a fully distributed scheduling framework called CASTLE (Client-side Adaptive Scheduler That minimizes Load and Energy) that jointly optimizes the spectral efficiency of cellular networks and battery consumption of smart devices. To do so, we focus on scenarios when many smart devices compete for cellular resources in the same base station: spreading out transmissions over time so that only a few devices transmit at once and improves both spectral efficiency and battery consumption. To this end, we devise two novel features in CASTLE. First, we explicitly consider inter-cell interference for accurate cellular load estimation in our machine learning algorithm. Second, we propose a fully distributed scheduling algorithm that coordinates transmissions between clients based on the locally estimated load level at each client. Our formulation for minimizing battery consumption at each device leads to an optimized back off-based algorithm that fits practical environments. Our comprehensive experimental results show that CASTLE's load estimation is up to 91 % accurate, and that CASTLE achieves higher spectral efficiency with less battery consumption, compared to existing centralized scheduling algorithms as well as a distributed CSMA-like protocol. Furthermore,we develop a light-weight SDK that can expedite the deployment of CASTLE into smart devices and evaluate it in a commercial LTE network.

Mobile Augmented Reality (AR), which overlays digital information with real-world scenes surrounding a user, provides an enhanced mode of interaction with the ambient world. Contextual AR applications rely on image recognition to identify objects in the view of the mobile device. In practice, due to image distortions and device resource constraints, achieving high performance image recognition for AR is challenging. Recent advances in edge computing offer opportunities for designing collaborative image recognition frameworks for AR. In this demonstration, we present CollabAR, an edge-assisted collaborative image recognition framework. CollabAR allows AR devices that are facing the same scene to collaborate on the recognition task. Demo participants develop an intuition for different image distortions and their impact on image recognition accuracy. We showcase how heterogeneous images taken by different users can be aggregated to improve recognition accuracy and provide a better user experience in AR.

Real-time multimedia applications, such as interactive gaming, live video streaming, and augmented reality, have strict latency and bitrate requirements. However, unpredictable network conditions, such as congestion and link quality, can severely degrade the quality of experience (QoE). While buffer-based mitigations cannot be applied to real-time applications due to their immediate resource needs, recent innovations in network slicing have demonstrated the feasibility of dedicating specified amounts of network resources to individual sessions in the radio access network. Encouraged by this, we propose to reserve network resources for multimedia sessions in real time according to their declared needs, thereby providing ad hoc session-level performance guarantees. Through Wi-Fi experiments and trace-driven LTE simulations, we show that such session-level resource provisioning is robust to real-time channel fluctuations and congestion externalities over the lifetime of a session. This approach, however, raises challenges: how can the network ensure that users are honest about their resource needs and optimally allocate its limited resources to users under uncertainty in future sessions' resource needs? We derive a novel multi-unit combinatorial auction (MUCA) model with a unique structure that can be exploited for fast winner determination, and yet incentivize truthful bidding, properties not simultaneously achieved in a generic MUCA but essential to making real-time session guarantees. Furthermore, since dynamic bidding in real time is challenging for end-users who are budget-constrained, we develop a reinforcement learning-based utility-maximizing strategy to distribute their budget across sessions and show that it yields high user utility.

The explosive growth of multimedia data traffic in wired and wireless networks have led Internet service providers (ISPs) to use penalty mechanisms like throttling, capping, overage fees to manage network congestion; however, such measures are harmful to the Internet ecosystem. Therefore, we use ideas from economics to create incentive-based, as opposed to penalty-based, solutions for data plans. In particular, we explore time-dependent pricing (TDP) - a form of dynamic pricing that manages congestion by offering time-varying discounts to incentivize users to shift some data traffic temporally. To realize TDP data plans in practice, we provide (i) an optimization model to compute time-dependent prices, (ii) a system implementation for deployment in operational networks, and (iii) experiments with two cellular networks for demonstrating feasibility. Our results show that the users respond to such pricing plans by using higher volume of traffic in lower-priced (off-peak) periods and benefit from a lower $/GB fee, while the ISPs benefit from a higher revenue due to increase in off-peak usage and lower peak-to-average traffic ratio in their network. This suggests that such a pricing solution can incentivize users to modify their usage behavior and enable better revenue management in multimedia-rich networks.

As demand for Internet usage increases, Internet service providers (ISPs) have begun to explore pricing-based solutions to dampen data demand. However few explicitly consider the dual problem of monetizing idle network capacity at uncongested times. PopData is a recent initiative from Verizon that does so by offering supplemental discount offers (SDOs) at these times, in which users can pay a fixed fee in exchange for unlimited data in the next hour. This work is the first of its kind to assess the benefits and viability of SDOs by modeling user and ISP decisions as a game, considering both overall monthly decisions and hour-to-hour decisions throughout the month. We first use our monthly model to show that users are generally willing to accept some SDO offers, allowing the ISP to increase its revenue. We then show that users face a complex hourly decision problem as to which SDOs they should accept over their billing cycles, since they are unaware of their exact future needs or when future SDOs will be made. The ISP faces a similarly challenging problem in deciding when to offer SDOs so as to maximize its revenue, subject to users' decisions. We develop optimal decision criteria for users and ISPs to decide whether to make or accept SDO offers. Our analysis shows that both users and ISPs can benefit from these offers, and we verify this through numerical experiments on a one-week trace of 20 cellular data users. We find that ISPs can exploit user uncertainty in when future SDOs will be made to optimize its revenue.

As infrastructure-as-a-service clouds become more popular, cloud providers face the complicated problem of maximizing their resource utilization by handling the dynamics of user demand. Auction-based pricing, such as Amazon EC2 spot pricing, provides an option for users to use idle resources at highly reduced yet dynamic prices; under such a pricing scheme, users place bids for cloud resources, and the provider chooses a threshold “spot” price above which bids are admitted. In this paper, we propose a nonlinear dynamical system model for the time-evolution of the spot price as a function of latent states that characterize user demand in the spot and on-demand markets. This model enables us to adaptively predict future spot prices given past spot price observations, allowing us to derive user bidding strategies for heterogeneous cloud resources that minimize the cost to complete a job with negligible probability of interruption. Along the way, the model also yields novel, empirically verifiable insights into cloud provider behavior. We experimentally validate our model and bidding strategy on two months of Amazon EC2 spot price data and find that our proposed bidding strategy is up to 4 times closer to the optimal strategy in hindsight compared to a baseline regression approach while incurring the same negligible probability of interruption.

Modern vehicle fleets, e.g., for ridesharing platforms and taxi companies, can reduce passengers' waiting times by proactively dispatching vehicles to locations where pickup requests are anticipated in the future. Yet it is unclear how to best do this: optimal dispatching requires optimizing over several sources of uncertainty, including vehicles' travel times to their dispatched locations, as well as coordinating between vehicles so that they do not attempt to pick up the same passenger. While prior works have developed models for this uncertainty and used them to optimize dispatch policies, in this work we introduce a model-free approach. Specifically, we propose MOVI, a Deep Q-network (DQN)-based framework that directly learns the optimal vehicle dispatch policy. Since DQNs scale poorly with a large number of possible dispatches, we streamline our DQN training and suppose that each individual vehicle independently learns its own optimal policy, ensuring scalability at the cost of less coordination between vehicles. We then formulate a centralized receding-horizon control (RHC) policy to compare with our DQN policies. To compare these policies, we design and build MOVI as a large-scale realistic simulator based on 15 million taxi trip records that simulates policy-agnostic responses to dispatch decisions. We show that the DQN dispatch policy reduces the number of unserviced requests by 76% compared to without dispatch and 20% compared to the RHC approach, emphasizing the benefits of a model-free approach and suggesting that there is limited value to coordinating vehicle actions. This finding may help to explain the success of ridesharing platforms, for which drivers make individual decisions.

We consider the problem of predicting link formation in Social Learning Networks (SLN), a type of social network that forms when people learn from one another through structured interactions. While link prediction has been studied for general types of social networks, the evolution of SLNs over their lifetimes coupled with their dependence on which topics are being discussed presents new challenges for this type of network. To address these challenges, we develop a time-series prediction methodology that uses a recurrent neural network architecture to pass network state between time periods, and that models over three types of SLN features updated in each period: neighborhood-based (e.g., resource allocation), path-based (e.g., shortest path), and post-based (e.g., topic similarity). Through evaluation on four real-world datasets from Massive Open Online Course (MOOC) discussion forums, we find that our method obtains substantial improvements over a Bayesian model and an unsupervised baseline, with AUCs typically above 0.75 and reaching 0.97 depending on the dataset. Our feature importance analysis shows that while neighborhood-based features contribute the most to the results, post-based and path-based features add additional information that significantly improve the predictions. We also find that several input features have opposite directions of correlation between link formation and post quality, suggesting that response time and quality are two competing objectives to be accounted for in SLN link recommendation systems.

As the U.S. mobile data market matures, Internet service providers (ISPs) generally charge their users with some variation on a quota-based data plan with overage charges. Common variants include unlimited, prepaid, and usage-based data plans. However, despite a recent flurry of research on optimizing mobile data pricing, few works have considered how these data plans affect users' consumption behavior. In particular, while users with such plans have a strong incentive to plan their usage over the month, they also face uncertainty in their future data usage needs that would make such planning difficult. In this work, we develop a dynamic programming model of users' consumption decisions over the month that takes this uncertainty into account. We use this model to quantify which types of users would benefit from different types of data plans, using these conditions to extrapolate the optimal types of data plans that ISPs should offer. Our theoretical findings are complemented by numerical simulations on a dataset of user usage from a large U.S. ISP. The results help mobile users to choose data plans that maximize their utilities and ISPs to gain profit by understanding their user behavior while choosing what data plans to offer.

We study the resource allocation problem in RAN-level integrated HetNets. This emerging HetNets paradigm allows for dynamic traffic splitting across radio access technologies for each client, and then for aggregating the traffic inside the network to improve the overall resource utilization. We focus on the max-min fair service rate allocation across the clients, and study the properties of the optimal solution. Based on the analysis, we design a low complexity distributed algorithm that tries to achieve max-min fairness. We also design a hybrid network architecture that leverages opportunistic centralized network supervision to augment the distributed solution. We analyze the performance of our proposed algorithms and prove their convergence. We also derive conditions under which the outcome is optimal. When the conditions are not satisfied, we provide constant upper and lower bounds on the optimality gap. Finally, we study the convergence time of our distributed solution and show that leveraging appropriate policies in its design significantly reduces the convergence time.

Fog computing is an emerging architecture that aims to run applications on multiple devices that lie on a continuum from cloud servers to personal user smartphones. These architectures allow applications to optimize over the information stored at and functionalities run on each device, based on individual device capabilities. We demonstrate the benefits of this approach for mobile video streaming. Existing HAS (HTTP adaptive streaming) techniques often suffer from problems like unstable video quality and suboptimal resource utilization. We find that a lack of coordination prevents both clientand network-side HAS techniques from solving them. However, our fog approach can exploit existing telecommunication APIs, which expose network capabilities to applications, in order to coordinate between clients and the network. Our coordinated HAS solution, FLARE, optimizes the total utility of all clients in a cell while maintaining stable video quality and supporting user- and device-specific needs. We implement FLARE on a commodity LTE femtocell and use the implementation to conduct the first comparison of HAS players on an LTE femtocell. By conducting extensive experiments using the ns-3 simulator, we also demonstrate that FLARE (i) enhances the average video bitrate, (ii) achieves stable video quality, and (iii) balances the throughput of simultaneous video and data flows, compared to other representative HAS solutions.

A cloud computing cluster equipped with a deadline-aware job scheduler faces fairness and efficiency challenges when greedy users falsely advertise the urgency of their jobs. Penalizing such untruthfulness without demotivating users from using the cloud service calls for advanced mechanism design techniques that work together with deadline-aware job scheduling. We propose a Bayesian incentive compatible pricing mechanism based on matching by replica-surrogate valuation functions. User valuations can be discovered by the mechanism, even when the users themselves do not fully understand their own valuations. Furthermore, users who are charged a Bayesian incentive compatible price have no reason to lie about the urgency of their jobs. The proposed mechanism achieves multiple desired truthful properties such as Bayesian incentive compatibility and ex-post individual rationality. We implement the proposed pricing mechanism. Through experiments in a Hadoop cluster with real-world datasets, we show that our prototype is capable of suppressing untruthful behavior from users.

Video streaming applications based on Peer-to-Peer (P2P) systems are popular for their scalability, which is hard to achieve with traditional client-server approaches. In particular, layered video streaming has been much-studied due to its ability to differentiate users' streaming qualities in heterogeneous user environments. Previous work, however, has shown that user misbehavior (e.g., free-riding and protocol deviation) poses a serious threat to P2P systems that are not equipped with proper incentive mechanisms. We propose a method to disincentivize such misbehavior. Our SVC-TChain is a layered P2P video streaming method based on scalable video coding (SVC), which uses the recently proposed T-Chain incentive mechanism to discourage free-riding. After introducing T-Chain, we present the first analytical framework to study SVC piece selection with multiple video layers, using it to efficiently choose SVC-TChain's optimal piece selection parameters and thus discourage deviations from the piece selection policy. Extensive experimental results show that SVC-TChain outperforms layered extensions of BiTos and Give-to-Get, two popular P2P video streaming approaches, both in the absence of user misbehavior and when some users misbehave.

Growing mobile data usage has led to end users paying substantial data costs, while Internet service providers (ISPs) struggle to upgrade their networks to keep up with demand and maintain high quality-of-service (QoS). This problem is particularly severe for smaller ISPs with less capital. Instead of simply upgrading their network infrastructure, ISPs can pool their networks to provide a good QoS and attract more users. Such a vISP (virtual ISP), for example, Google's Project Fi, allows users to access any of its partner ISPs' networks. We provide the first systematic analysis of a vISP's economic impact, showing that the vISP provides a viable solution for smaller ISPs attempting to attract more users, but may not maintain a positive profit if users' data demands evolve. To do so, we consider users' decisions of whether to defect from their current ISP to the vISP, as well as ISPs' decisions on whether to partner with the vISP. We derive the vISP's dependence on user behavior and partner ISPs: users with very light or very heavy usage are the most likely to defect, while ISPs with heavy-usage customers can benefit from declining to partner with the vISP. Our analytical results are verified with extensive numerical simulations.

Internet service providers (ISPs) struggle to invest in upgrading their networks to catch up with growing mobile data demand, while users have to face significant data overage fees. Pooling ISPs' network infrastructures can potentially enable better user experience and lower prices. For example, Google recently launched a cross-carrier MVNO (mobile virtual network operator) data plan called Project Fi, where users' devices can automatically access either of two partner cellular networks or any available open WiFi network. We consider the economic impact of cross-carrier MVNOs on the mobile data market. We begin by analyzing a network selection strategy that optimizes cross-carrier users' costs. We then study ISPs' behavior, deriving the prices that partner ISPs charge the cross-carrier MVNO and that the cross-carrier MVNO charges its end users. Although the cross-carrier MVNO may lose money from selling data, it can offset this loss with side revenue, e.g., advertisement revenue when users consume more content. We derive conditions under which the cross-carrier MVNO achieves a profit and its users reduce their costs. Finally, we use a real-world network quality dataset to simulate users' network selection behavior and demonstrate the benefits of the ISP competition brought by the cross-carrier MVNO.

The growing volume of mobile data traffic has led many Internet service providers (ISPs) to cap the monthly data usage of their users and to charge overage fees, when the data caps are exceeded. Yet data caps imperfectly capture the reality of heterogeneous data usage over a month-even the same user may have varied requirements from month to month. In response, some ISPs are providing alternative avenues for users to customize data plans to their needs. In this paper, we examine a secondary data market, as for example created by China Mobile Hong Kong, in which users can buy and sell leftover data caps from one another. While similar to an auction in that users submit bids to buy and sell data, it differs from traditional double auctions in that the ISP serves as the middleman between buyers and sellers. Such a market faces two questions. First, can users learn each others' trading behavior well enough for the market to function, and second, do ISPs have a financial incentive to offer such a market? Different users' abilities to trade data depend on others, thus forcing users to not only optimize the amounts of data they bid, but also to learn and adjust for other users' trading behavior. We derive users' optimal behavior and propose an algorithm for ISPs to match buyers and sellers. We compare the optimal matchings for different ISP objectives and derive conditions under which the secondary market increases ISP revenue: while the ISP loses revenue from overage fees, it can assess administration fees and profit from the differences between the buyer and seller prices. Finally, we use one year of usage data from 100 U.S. mobile users to simulate the market dynamics and to illustrate that sustainable conditions for a revenue increase for the ISP can hold in practice.

In this paper, we propose a simple, distributed, but highly efficient fairness-enforcing incentive mechanism for cooperative computing. The proposed mechanism, called triangle chaining (T-Chain), enforces reciprocity to avoid the exploitable aspects of the schemes that allow free-riding. In T-Chain, symmetric key cryptography provides the basis for a lightweight, almost-fair exchange protocol, which is coupled with a pay-it-forward mechanism. This combination increases the opportunity for multi-lateral exchanges and further maximizes the resource utilization of participants, each of whom is assumed to operate solely for his or her own benefit. T-Chain also provides barrier-free entry to newcomers with flexible resource allocation, allowing them to immediately benefit, and, therefore, is suitable for dynamic environments with high churn (i.e., turnover). T-Chain is distributed and simple to implement, as no trusted third party is required to monitor or enforce the scheme, nor is there any reliance on reputation information or tokens.

As more devices gain Internet connectivity, more information needs to be exchanged between them. For instance, cloud servers might disseminate instructions to clients, or sensors in the Internet of Things might send measurements to each other. In such scenarios, information spreads faster when users have an incentive to contribute data to others. While many works have considered this problem in peer-to-peer scenarios, none have rigorously theorized the performance of different design choices for the incentive mechanisms. In particular, different designs have different ways of "bootstrapping" new users (distributing information to them) and preventing "free-riding" (receiving information without uploading any in return). We classify incentive mechanisms in terms of reciprocity-, altruism-, and reputation-based algorithms, and then analyze the performance of these three basic and three hybrid algorithms. We show that the algorithms lie along a tradeoff between fairness and efficiency, with altruism and reciprocity at the two extremes. The three hybrids all leverage their component algorithms to achieve similar efficiency. The reputation hybrids are the most fair and can nearly match altruism's bootstrapping speed, but only the reciprocity/reputation hybrid can match reciprocity's zero-tolerance for free-riding. It therefore yields better fairness and efficiency when free-riders are present. We validate these comparisons with extensive experimental results.

Cloud service providers (CSPs) often face highly dynamic user demands for their resources, which can make it difficult for them to maintain consistent quality-of-service. Some CSPs try to stabilize user demands by offering sustained-use discounts to jobs that consume more instance-hours per month. These discounts present an opportunity for users to pool their usage together into a single ``job.'' In this paper, we examine the viability of a middleman, the cloud virtual service provider (CVSP), that rents cloud resources from a CSP and then resells them to users. We show that the CVSP's business model is only viable if the average job runtimes and thresholds for sustained-use discounts are sufficiently small; otherwise, the CVSP cannot simultaneously maintain low job waiting times while qualifying for a sustained-use discount. We quantify these viability conditions by modeling the CVSP's job scheduling and then use this model to derive users' utility-maximizing demands and the CVSP's profit-maximizing price, as well as the optimal number of instances that the CVSP should rent from the CSP. We verify our results on a one-month trace from Google's production compute cluster, through which we first validate our assumptions on the job arrival and runtime distributions, and then show that the CVSP is viable under these workload traces. Indeed, the CVSP can earn a positive profit without significantly impacting the CSP's revenue, indicating that the CSP and CVSP can coexist in the cloud market.

To cope with recent exponential increases in demand for mobile data, wireless Internet service providers (ISPs) are increasingly changing their pricing plans and deploying Wi-Fi hotspots to offload their mobile traffic. However, these ISP-centric approaches for traffic management do not always match the interests of mobile users. Users face a complex, multi-dimensional tradeoff between cost, throughput, and delay in making their offloading decisions: while they may save money and receive a higher throughput by waiting for Wi-Fi access, they may not wait for Wi-Fi if they are sensitive to delay. To navigate this tradeoff, we develop Adaptive bandwidth Management through USer-Empowerment (AMUSE), a functional prototype of a practical, cost-aware Wi-Fi offloading system that takes into account a user's throughput-delay tradeoffs and cellular budget constraint. Based on predicted future usage and Wi-Fi availability, AMUSE decides which applications to offload to what times of the day. Since nearly all traffic flows from mobile devices are TCP flows, we introduce a new receiver-side bandwidth allocation mechanism to practically enforce the assigned rate of each TCP application. Thus, AMUSE users can optimize their bandwidth rates according to their own cost-throughput-delay tradeoff without relying on support from different apps’ content servers. Through a measurement study of 20 smartphone users’ traffic usage traces, we observe that though users already offload a large amount of some application types, our framework can offload a significant additional portion of users’ cellular traffic. We implement AMUSE on Windows 7 tablets and evaluate its effectiveness with 3G and Wi-Fi usage data obtained from a trial with 37 mobile users. Our results show that AMUSE improves user utility; when compared with AMUSE, other offloading algorithms yield 14 and 27 percent lower user utilities for light and heavy users, respectively. Intelligently managing users’ competing interests for cost, throughput, and delay can therefore improve their offloading decisions.

Public cloud storage has recently surged in popularity. However, cloud storage providers (CSPs) today offer fairly rigid services, which cannot be customized to meet individual users' needs. We propose a distributed, client-defined architecture that integrates multiple autonomous CSPs into one unified cloud and allows individual clients to specify their desired performance levels and share files. We design, implement, and deploy CYRUS (Client-defined privacY-protected Reliable cloUd Service), a practical system that realizes this architecture. CYRUS ensures user privacy and reliability by scattering files into smaller pieces across multiple CSPs, so that no one CSP can read users' data. We develop an algorithm that sets reliability and privacy parameters according to user needs and selects CSPs from which to download user data so as to minimize latency. To accommodate multiple autonomous clients, we allow clients to upload simultaneous file updates and detect conflicts after the fact from the client. We finally evaluate the performance of a CYRUS prototype that connects to four popular commercial CSPs in both lab testbeds and user trials, and discuss CYRUS's implications for the cloud storage market.

In this paper, we propose a simple, distributed, but highly efficient fairness-enforcing incentive mechanism for cooperative computing. The proposed incentive scheme, called Triangle Chaining (T-Chain), enforces reciprocity to minimize the exploitable aspects of other schemes that allow free-riding. In T-Chain, symmetric key cryptography provides the basis for a lightweight, almost-fair exchange protocol, which is coupled with a pay-it-forward mechanism. This combination increases the opportunity for multi-lateral exchanges and further maximizes the resource utilization of participants, each of whom is assumed to operate solely for his or her own benefit. T-Chain also provides barrier-free entry to newcomers with flexible resource allocation, providing them with immediate benefits, and therefore is suitable for dynamic environments with high churn (i.e., Turnover). TChain is distributed and simple to implement, as no trusted third party is required to monitor or enforce the scheme, nor is there any reliance on reputation information or tokens.

In January 2014, AT&T introduced sponsored data to the U.S. mobile data market, allowing content providers (CPs) to subsidize users' cost of mobile data. As sponsored data gains traction in industry, it is important to understand its implications. This work considers CPs' choice of how much content to sponsor and the implications for users, CPs, and ISPs (Internet service providers). We first formulate a model of user, CP, and ISP interaction for heterogeneous users and CPs and derive their optimal behaviors. We then show that these behaviors can reverse our intuition as to how user demand and utility change with different user and CP characteristics. While all three parties can benefit from sponsored data, we find that sponsorship disproportionately favors less cost-constrained CPs and more cost-constrained users, exacerbating CP inequalities but making user demand more even. We also show that users' utilities increase more than CPs' with sponsored data. We finally illustrate these results in practice through numerical simulations with data from a commercial pricing trial and introduce a framework for CPs to decide which, in addition to how much, content to sponsor.

The growing volume of mobile data traffic has led many Internet service providers (ISPs) to cap their users' monthly data usage, with overage fees for exceeding their caps. In this work, we examine a secondary data market in which users can buy and sell leftover data caps from each other. China Mobile Hong Kong recently introduced such a market. While similar to an auction in that users submit bids to buy and sell data, it differs from traditional double auctions in that the ISP serves as the middleman between buyers and sellers. We derive the optimal prices and amount of data that different buyers and sellers are willing to bid in this market and then propose an algorithm for ISPs to match buyers and sellers. We compare the optimal matching for different ISP objectives and derive conditions under which an ISP can obtain higher revenue with the secondary market: while the ISP loses revenue from overage fees, it can assess administration fees and take the differences between the buyer and seller prices. Finally, we use one year of usage data from 100 U.S. mobile users to illustrate that the conditions for a revenue increase can hold in practice.

Recent increases in network traffic have led to severe congestion in broadband networks. We propose to mitigate this problem with a two-level edge-based solution that incentivizes users to moderate their bandwidth usage based on their actual needs. In the first level, home gateways are given QoE (quality of experience) credits that they can spend to receive more bandwidth at congested times; to ensure fairness, the credits are redistributed to other gateways after they are spent. We show that this scheme guarantees long-term fairness and maximizes users' total satisfaction at the equilibrium. In the second level, each gateway allocates bandwidth among its users and apps according to its own priorities. Gateways can thus customize their bandwidth allocation depending on individual preferences. We develop a prototype of this second-level allocation on commodity wireless routers. We then consider an example scenario and show by simulation and implementation results that our solution outperforms an equal bandwidth allocation, increasing users' overall utility and fairly allocating bandwidth across users.

Amazon's Elastic Compute Cloud (EC2) uses auction-based spot pricing to sell spare capacity, allowing users to bid for cloud resources at a highly reduced rate. Amazon sets the spot price dynamically and accepts user bids above this price. Jobs with lower bids (including those already running) are interrupted and must wait for a lower spot price before resuming. Spot pricing thus raises two basic questions: how might the provider set the price, and what prices should users bid? Computing users' bidding strategies is particularly challenging: higher bid prices reduce the probability of, and thus extra time to recover from, interruptions, but may increase users' cost. We address these questions in three steps: (1) modeling the cloud provider's setting of the spot price and matching the model to historically offered prices, (2) deriving optimal bidding strategies for different job requirements and interruption overheads, and (3) adapting these strategies to MapReduce jobs with master and slave nodes having different interruption overheads. We run our strategies on EC2 for a variety of job sizes and instance types, showing that spot pricing reduces user cost by 90% with a modest increase in completion time compared to on-demand pricing.

To alleviate the congestion caused by rapid growth in demand for mobile data, wireless service providers (WSPs) have begun encouraging users to offload some of their traffic onto supplementary network technologies, e.g., offloading from 3G or 4G to WiFi or femtocells. With the growing popularity of such offerings, a deeper understanding of the underlying economic principles and their impact on technology adoption is necessary. To this end, we develop a model for user adoption of a base technology (e.g., 3G) and a bundle of the base plus a supplementary technology (e.g., 3G + WiFi). Users individually make their adoption decisions based on several factors, including the technologies' intrinsic qualities, negative congestion externalities from other subscribers, and the flat access rates that a WSP charges. We then show how these user-level decisions translate into aggregate adoption dynamics and prove that these converge to a unique equilibrium for a given set of exogenously determined system parameters. We fully characterize these equilibria and study adoption behaviors of interest to a WSP. We then derive analytical expressions for the revenue-maximizing prices and optimal coverage factor for the supplementary technology and examine some resulting nonintuitive user adoption behaviors. Finally, we develop a mobile app to collect empirical 3G/WiFi usage data and numerically investigate the profit-maximizing adoption levels when a WSP accounts for its cost of deploying the supplemental technology and savings from offloading traffic onto this technology.

In an era of 108% annual growth in demand for mobile data and $10/GB overage fees, Internet Service Providers (ISPs) are experiencing severe congestion and in turn are hurting consumers with aggressive pricing measures. But smarter practices, such as time-dependent pricing (TDP), reward users for shifting their non-critical demand to off-peak hours and can potentially benefit both users and ISPs. Although dynamic TDP ideas have existed for many years, dynamic pricing for mobile data is only now gaining interest among ISPs. Yet TDP plans require not only systems engineering but also an understanding of economic incentives, user behavior and interface design. In particular, the HCI aspects of communicating price feedback signals from the network and the response of mobile data users need to be studied in the real world. But investigating these issues by deploying a virtual TDP data plan for real ISP customers is challenging and rarely explored. To this end, we carried out the first TDP trial for mobile data in the US with 10 families. We describe the insights gained from the trial, which can help the HCI community as well as ISPs, app developers and designers create tools that empower users to better control their usage and save on their monthly bills, while also alleviating network congestion.

Mobile users face a tradeoff between cost, throughput, and delay in making their offloading decisions. To navigate this tradeoff, we propose AMUSE (Adaptive bandwidth Management through USer-Empowerment), a practical, costaware WiFi offloading system that takes into account a user's throughput-delay tradeoffs and cellular budget constraint. Based on predicted future usage and WiFi availability, AMUSE decides which applications to offload to what times of the day. To practically enforce the assigned rate of each TCP application, we introduce a receiver-side TCP bandwidth control algorithm that adjusts the rate by controlling the TCP advertisement window from the user side. We implement AMUSE on Windows 7 tablets and evaluate its effectiveness with 3G and WiFi usage data obtained from a trial with 25 mobile users. Our results show that AMUSE improves user utility.

To alleviate the congestion caused by rapid growth in demand for mobile data, ISPs have begun encouraging users to offload some of their traffic onto a supplementary, better quality network technology, e.g., offloading from 3G or 4G to WiFi and femtocells. With the growing popularity of such offerings, a deeper understanding of the underlying economic principles and their impact on technology adoption is necessary. To this end, we develop a model for user adoption of a base wireless technology and a bundle of the base plus a supplementary technology. In our model, individual users make their adoption decisions based on several factors, including the technologies' intrinsic qualities, throughput degradation due to congestion externalities from other subscribers, and the flat access rates that an ISP charges. We study the adoption dynamics and show that they converge to a unique equilibrium for a given set of exogenously determined system parameters. In particular, we characterize the occurrence of interesting adoption behaviors, including a possible decrease in the adoption of the supplementary technology as its coverage increases. Similar behaviors occur at an ISP's profit-maximizing prices and the optimal coverage area for the supplementary technology. To account for the potential benefits from offloading in practice, we collect 3G and WiFi usage and location data from twenty mobile users. We then use this data to numerically investigate the profit-maximizing adoption levels when an ISP accounts for its cost of deploying the supplemental technology and savings from offloading traffic onto this technology.

Rapid increases in the demand for broadband data are increasingly causing a growth in costs for communication service providers (CSPs). Yet under the current pricing plans, CSPs' revenue has not kept pace with these costs. Thus, many CSPs are considering Smart Data Pricing (SDP) as a way to reduce cost or increase revenue. Before offering such novel data plans, however, CSPs must conduct trials of the specific data plans proposed. Due to the complexity of necessary changes in network equipment and a need to carefully design the trial in order to understand customer behavior, planning such trials is not only a critical precursor to SDP deployment, but also a nontrivial undertaking in itself. This paper discusses general principles of trial design and proposes two methods for estimating their effectiveness. We first give an introduction to the goals of SDP research and review three possible SDP approaches. We then discuss the importance of pre-trial participant surveys and some technical considerations of implementing the trial infrastructure for a particular SDP algorithm. Finally, we show how the CSP may extrapolate from the trial results to estimate the SDP trial's benefits, in terms of changes in traffic patterns and a reduction in spectrum requirements. We conclude with some remarks about future work.

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.

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.

ISPs around the world have begun to offer new pricing plans for wireless data, such as usage-based pricing in the U.S., to mitigate recent growth in bandwidth demand. Time Dependent Pricing (TDP) represents a next step in this direction [1, 2]. With TDP, ISPs can shift traffic to off-peak periods, thus reducing their cost, while consumers save money by choosing the time of usage. TDP uses a feedback control loop between an ISP and its users to account for users' responses to offered prices in optimizing the future prices. We have implemented such a TDP system and are presently conducting a user trial at Princeton while planning larger trials with commercial ISPs. This demo will introduce the audience to our system's ISP- and user-side features. On the ISP side, we show the current network congestion, while on the user side, we show device UIs displaying the offered prices, the device usage history, and automated scheduling of applications to keep users within a specified budget.

The two largest U.S. wireless ISPs have recently moved towards usage-based pricing to better manage the growing demand on their networks. Yet usage-based pricing still requires ISPs to over-provision capacity for demand at peak times of the day. Time-dependent pricing (TDP) addresses this problem by considering when a user consumes data, in addition to how much is used. We present the architecture, implementation, and a user trial of an end-to-end TDP system called TUBE. TUBE creates a price-based feedback control loop between an ISP and its end users. On the ISP side, it computes TDP prices so as to balance the cost of congestion during peak periods with that of offering lower prices in less congested periods. On mobile devices, it provides a graphical user interface that allows users to respond to the offered prices either by themselves or using an "autopilot" mode. We conducted a pilot TUBE trial with 50 iPhone or iPad 3G data users, who were charged according to our TDP algorithms. Our results show that TDP benefits both operators and customers, flattening the temporal fluctuation of demand while allowing users to save money by choosing the time and volume of their usage.

Smart grids are capable of two-way communication between individual user devices and the electricity provider, enabling providers to create a control-feedback loop using time-dependent pricing. By charging users more in peak and less in off-peak hours, the provider can induce users to shift their consumption to off-peak periods, thus relieving stress on the power grid and the cost incurred from large peak loads. We formulate the electricity provider's cost minimization problem in setting these prices by considering consumers' device-specific scheduling flexibility and the provider's cost structure of purchasing electricity from an electricity generator. Consumers' willingness to shift their device usage is modeled probabilistically, with parameters that can be estimated from real data. We develop an algorithm for computing day-ahead prices, and another algorithm for estimating and refining user reaction to the prices. Together, these two algorithms allow the provider to dynamically adjust the offered prices based on user behavior. Numerical simulations with data from an Ontario electricity provider show that our pricing algorithm can significantly reduce the cost incurred by the provider.

Charging different prices for Internet access at different times induces users to spread out their bandwidth consumption across times of the day. Potential impact on ISP revenue, congestion management, and consumer behavior can be significant, yet some fundamental questions remain: is it feasible to operate time dependent pricing and how much benefit can it bring? We develop an efficient way to compute the cost-minimizing time-dependent prices for an Internet service provider (ISP), using both a static session-level model and a dynamic session model with stochastic arrivals. A key step is choosing the representation of the optimization problem so that the resulting formulations remain computationally tractable for large-scale problems. We next show simulations illustrating the use and limitation of time-dependent pricing. These results demonstrate that optimal prices, which "reward'' users for deferring their sessions, roughly correlate with demand in each period, and that changing prices based on real-time traffic estimates may significantly reduce ISP cost. The degree to which traffic is evened out over times of the day depends on the time-sensitivity of sessions, cost structure of the ISP, and amount of traffic not subject to time-dependent prices. Finally, we present our system integration and implementation, called TUBE, and proof-of-concept experimentation.