Main Conference Program

	Monday, October 17th	Tuesday, October 18th	Wednesday, October 19th	Thursday, October 20th
Time (KST)	Workshops	Day 1	Day 2	Day 3
8:00	Registration	Registration	Registration	Registration
9:00		Opening		Session 7 (09:10-)
9:20	Workshop 1 (MobiCOVID)	Keynote 1 Prof. Don Towsley	Keynote 2 Dr. Sunghyun Choi


10:20		Coffee Break	Coffee Break	Coffee Break
10:50		Session 1	Panel AI and Networks	Session 8


12:00
		Lunch	Lunch

13:30	Workshop 2 (WoNEXT)	Session 2	Session 4


14:40		Coffee Break	Coffee Break
15:10		Session 3	Session 5


16:20		Break	Break
16:40		Posters & Demos	Session 6



18:00-		Reception & TPC Report	Banquet & Award Ceremony
18:00-		Reception & TPC Report	Banquet & Award Ceremony

All events including technical sessions will be held at Grand Ballroom (2F), except Banquet (Namsan room - rooftop (19F)) and Posters and Demos (Foyer (2F))

Keynote 1.

Tuesday (October 18th, 09:20 - 10:20)

Session Chair: Kyunghan Lee, Seoul National University

The Quantum Internet: Recent Advances and Challenges
Prof. Don Towsley (University of Massachusetts, Amherst)
Abstract: Quantum information processing is at the cusp of having significant impact on technology and society in the form of providing unbreakable security, ultra-high-precision distributed sensing with applications to metrology and science discovery (e.g., LIGO), and polynomial speed-ups on search with implications to big data. Most of these applications are enabled by high-rate distributed shared entanglement between pairs and groups of users. A critical missing component that prevents crossing this threshold is a distributed infrastructure in the form of a world-wide “Quantum Internet”. This motivates our study of quantum networks, namely what is the right architecture and how should it operate, i.e., route multiple quantum information flows, and dynamically allocate resources fairly. In this talk I will review a specific class of quantum networks - those that generate and distribute entangled quantum states to pairs or groups of users. Drawing on my work, I will present opportunities and challenges related to resource sharing in such networks focusing on similarities to, and differences from classical networks. I will also present challenges for controlling and analyzing such networks. I will end the talk with a list of open problems.

Session 1: Scheduling and Routing.

Tuesday (October 18th, 10:50 - 12:00)

Session Chair: Sangheon Pack, Korea University

Effective Multi-User Delay-Constrained Scheduling with Deep Recurrent Reinforcement Learning

Pihe Hu, Ling pan, Yu Chen, Zhixuan Fang, Longbo Huang (Tsinghua University)

Abstract: Multi-user delay constrained scheduling is important in many real-world applications including wireless communication, live streaming, and cloud computing. Yet, it poses a critical challenge since the scheduler needs to make real-time decisions to guarantee the delay and resource constraints simultaneously without prior information of system dynamics, which can be time-varying and hard to estimate. Moreover, many practical scenarios suffer from partial observability issues, e.g., due to sensing noise or hidden correlation. To tackle these challenges, we propose a deep reinforcement learning (DRL) algorithm, named Recurrent Softmax Delayed Deep Double Deterministic Policy Gradient (RSD4), which is a data-driven method based on a Partially Observed Markov Decision Process (POMDP) formulation. RSD4 guarantees resource and delay constraints by Lagrangian dual and delay-sensitive queues, respectively. It also efficiently tackles partial observability with a memory mechanism enabled by the recurrent neural network (RNN) and introduces user-level decomposition and node-level merging to ensure scalability. Extensive experiments on simulated/real-world datasets demonstrate that RSD4 is robust to system dynamics and partially observable environments, and achieves superior performances over existing DRL and non-DRL-based methods.

Online Scheduling and Routing with End-to-End Deadline Constraints in Multihop Wireless Networks

Christos Tsanikidis, Javad Ghaderi (Columbia University)

Abstract: We consider scheduling deadline-constrained packets in multihop wireless networks. Packets with arbitrary deadlines and weights arrive at and are destined to different nodes. The goal is to design online admission, routing, and scheduling algorithms in order to maximize the cumulative weight of packets that reach their destinations within their deadlines. Under a general interference graph model of the wireless network, we provide online algorithms that are (𝛾, R)-competitive, i.e., they achieve at least 1/𝛾 fraction of the value of the optimal offline algorithm, and do not exceed the capacity by more than a factor R ≥ 1. In particular, our algorithm can achieve 𝛾 = 𝑂(𝜓★ log(Δ𝜌𝐿)/R) when RC = Ω(𝜓★ log(Δ𝜌𝐿)), where 𝜌 is the ratio of maximum weight to minimum weight of packets, 𝐿 is the length of the longest route of packets, and C is the minimum link capacity or the number of channels. Here, Δ is the maximum degree and 𝜓 ★ is the local clique cover number of the interference graph. Our results translate directly to many networks of interest, for example, in one-hop interference networks, 𝜓 ★ = 2, and in the case of wired networks (no interference), 𝜓 ★ = 1. We further provide lower bounds that show that our results are asymptotically optimal in many settings. Finally, we present extensive simulations that show our algorithms provide significant improvement over the prior approaches.

On Scheduling Ring-All-Reduce Learning Jobs in Multi-Tenant GPU Clusters with Communication Contention

Menglu Yu (Iowa State University); Bo Ji (Virginia Tech); Hridesh Rajan (Iowa State University); Jia Liu (The Ohio State University)

Abstract: Powered by advances in deep learning (DL) techniques, machine learning and artificial intelligence have achieved astonishing successes. However, the rapidly growing needs for DL also led to communication- and resource-intensive distributed training jobs for large-scale DL training, which are typically deployed over GPU clusters. To sustain the ever-increasing demand for DL training, the so-called “ring-all-reduce” (RAR) technologies have recently emerged as a favorable computing architecture to efficiently process network communication and computation load in GPU clusters. The most salient feature of RAR is that it removes the need for dedicated parameter servers, thus alleviating the potential communication bottleneck. However, when multiple RAR-based DL training jobs are deployed over GPU clusters, communication bottlenecks could still occur due to contentions between DL training jobs. So far, there remains a lack of theoretical understanding on how to design contention-aware resource scheduling algorithms for RAR-based DL training jobs, which motivates us to fill this gap in this work. Our main contributions are three-fold: i) We develop a new analytical model that characterizes both communication overhead related to the worker distribution of the job and communication contention related to the co-location of different jobs; ii) Based on the proposed analytical model, we formulate the problem as a non-convex integer program to minimize the makespan of all RAR-based DL training jobs. To address the unique structure in this problem that is not amenable for optimization algorithm design, we reformulate the problem into an integer linear program that enables provable approximation algorithm design called SJF-BCO (Smallest Job First with Balanced Contention and Overhead); and iii) We conduct extensive experiments to show the superiority of SJF- BCO over existing schedulers. Collectively, our results contribute to the state-of-the-art of distributed GPU system optimization and algorithm design.

Session 2: Overcoming Delays and Age of Information.

Tuesday (October 18th, 13:30 - 14:40)

Session Chair: Yoora Kim, Ulsan University

How Does Data Freshness Affect Real-time Supervised Learning?

Md Kamran Chowdhury Shisher, Yin Sun (Department of ECE, Auburn University)

Abstract: In this paper, we analyze the impact of data freshness on real-time supervised learning, where a neural network is trained to infer a time-varying target (e.g., the position of the vehicle in front) based on features (e.g., video frames) observed at a sensing node (e.g., camera or lidar). One might expect that the performance of real- time supervised learning degrades monotonically as the feature becomes stale. Using an information-theoretic analysis, we show that this is true if the feature and target data sequence can be closely approximated as a Markov chain; it is not true if the data sequence is far from Markovian. Hence, the prediction error of real-time supervised learning is a function of the Age of Information (AoI), where the function could be non-monotonic. Several experiments are conducted to illustrate the monotonic and non-monotonic behaviors of the prediction error. To minimize the inference error in real-time, we propose a new “selection-from-buffer” model for sending the features, which is more general than the “generate-at-will” model used in earlier studies. By using Gittins and Whittle indices, low-complexity scheduling strategies are developed to minimize the inference error, where a new connection between the Gittins index theory and Age of Information (AoI) minimization is discovered. These scheduling results hold (i) for minimizing general AoI functions (monotonic or non-monotonic) and (ii) for general feature transmission time distributions. Data-driven evaluations are presented to illustrate the benefits of the proposed scheduling algorithms.

Optimizing Age of Information with Correlated Sources

Vishrant Tripathi, Eytan Modiano (MIT)

Abstract: We develop a simple model for the timely monitoring of correlated sources over a wireless network. Using this model, we study how to optimize weighted-sum average Age of Information (AoI) in the presence of correlation. First, we discuss how to find optimal stationary randomized policies and show that they are at-most a factor of two away from optimal policies in general. Then, we develop a Lyapunov drift-based max-weight policy that performs better than randomized policies in practice and show that it is also at-most a factor of two away from optimal. Next, we derive scaling results that show how AoI improves in large networks in the presence of correlation. We also show that for stationary randomized policies, the expression for average AoI is robust to the way in which the correlation structure is modeled. Finally, for the setting where correlation parameters are unknown and time-varying, we develop a heuristic policy that adapts its scheduling decisions by learning the correlation parameters in an online manner. We also provide numerical simulations to support our theoretical results.

Sampling of the Wiener Process for Remote Estimation over a Channel with Unknown Delay Statistics

Haoyue Tang (Yale University); Yin Sun (Dept. of ECE, Auburn University); Leandros Tassiulas (Yale University)

Abstract: In this paper, we study an online sampling problem of the Wiener process. The goal is to minimize the mean squared error (MSE) of the remote estimator under a sampling frequency constraint when the transmission delay distribution is unknown. The sampling problem is reformulated into a renewal reward optimization problem, and we propose an online sampling algorithm that can adaptively learn the optimal sampling policy through stochastic approximation. We show that the cumulative MSE regret grows with rate O(ln 𝑘), where 𝑘 is the number of samples. Through Le Cam’s two point method, we show that the worst-case cumulative MSE regret of any online sampling algorithm is lower bounded by Ω(ln𝑘). Hence, the proposed online sampling algorithm is minimax order-optimal. Finally, we validate the performance of the proposed algorithm via numerical simulations.

Session 3: De-centralized and Federated Learning.

Tuesday (October 18th, 15:10 - 16:20)

Session Chair:Parikshit Hegde, University of Texas at Austin

INTERACT: Achieving Low Sample and Communication Complexities in Decentralized Bilevel Learning over Networks

Zhuqing Liu (The Ohio State University); Xin Zhang (Iowa State University); Prashant Khanduri (University of Minnesota); Songtao Lu (IBM Thomas J. Watson Research Center); Jia Liu (The Ohio State University)

Abstract: In recent years, decentralized bilevel optimization problems have received increasing attention in the networking and machine learning communities. However, for decentralized bilevel optimization over networks with limited computation and communication capabilities, how to achieve low sample and communication complexities are two fundamental challenges. In this paper, we make the first attempt to investigate the class of decentralized bilevel optimization problems with nonconvex and strongly-convex structure corresponding to the outer and inner subproblems, respectively. Our main contributions in this paper are two-fold: i) We first propose a deterministic algorithm called INTERACT (inner-gradient-descent-outer-tracked-gradient) that requires the sample complexity of O(𝑛𝜖−1) and communication complexity of O(𝜖−1) to solve the bilevel optimization problem, where 𝑛 and 𝜖 > 0 are the number of samples at each agent and the desired stationarity gap, respectively. ii) To relax the need for full gradient evaluations in each iteration, we propose a stochastic variance-reduced version of INTERACT (SVR-INTERACT), which improves the sample complexity √ −1 to O ( 𝑛𝜖 ) while achieving the same communication complexity as the deterministic algorithm. Our numerical experiments also corroborate our theoretical findings.

NET-FLEET: Achieving Linear Convergence Speedup for Fully Decentralized Federated Learning with Heterogeneous Data

Xin Zhang (Iowa State University); Minghong Fang, Zhuqing Liu, Haibo Yang, Jia Liu (The Ohio State University); Zhengyuan Zhu (Iowa State University)

Abstract: Federated learning (FL) has received a surge of interest in recent years thanks to its benefits in data privacy protection, efficient communication, and parallel data processing. Also, with appropriate algorithmic designs, one could achieve the desirable linear speedup for convergence effect in FL. However, most existing works on FL are limited to systems with i.i.d. data and centralized parameter servers and results on decentralized FL with heterogeneous datasets remains limited. Moreover, whether or not the linear speedup for convergence is achievable under fully decentralized FL with data heterogeneity remains an open question. In this paper, we address these challenges by proposing a new algorithm, called NET-FLEET, for fully decentralized FL systems with data heterogeneity. The key idea of our algorithm is to enhance the local update scheme in FL (originally intended for communication efficiency) by incorporating a recursive gradient correction technique to handle heterogeneous datasets. We show that, under appropriate parameter settings, the proposed NET-FLEET algorithm achieves a linear speedup for convergence. We further conduct extensive numerical experiments to evaluate the performance of the proposed NET-FLEET algorithm and verify our theoretical findings.

Index-Aware Reinforcement Learning for Adaptive Video Streaming at the Wireless Edge

Guojun Xiong (SUNY-Binghamton University); Xudong Qin, Bin Li (Pennsylvania State University); Rahul Singh (Indian Institute of Science); Jian Li (SUNY-Binghamton University)

Abstract: We study adaptive video streaming for multiple users in wireless access edge networks with unreliable channels. The key challenge is to jointly optimize the video bitrate adaptation and resource allocation such that the users’ cumulative quality of experience is maximized. This problem is a finite-horizon restless multi-armed multi-action bandit problem and is provably hard to solve. To overcome this challenge, we propose a computationally appealing index policy entitled Quality Index Policy, which is well-defined without the Whittle indexability condition and is provably asymptotically optimal without the global attractor condition. These two conditions are widely needed in the design of most existing index policies, which are diffi- cult to establish in general. Since the wireless access edge network environment is highly dynamic with system parameters unknown and time-varying, we further develop an index-aware reinforcement learning (RL) algorithm dubbed QA-UCB. We show that QA-UCB achieves a sub-linear regret with a low-complexity since it fully exploits the structure of the Quality Index Policy for making decisions. Extensive simulations using real-world traces demonstrate significant gains of proposed policies over conventional approaches. We note that the proposed framework for designing index policy and index-aware RL algorithm is of independent interest and could be useful for other large-scale multi-user problems.

Posters and Demos.

Tuesday (October 18th, 16:40 - 17:50), Foyer (2F)

Session Chair: Jeongseul Ok, POSTECH

Demo: Hivemind: IoT-based Democratization of Shared Actuators in a Public Space
Wonjung Kim (KAIST), Seungchul Lee (KAIST), Youngjae Chang (KAIST), Taegyeong Lee (KAIST), Seongwoong Kang (KAIST), Inseok Hwang (POSTECH), Junehwa Song (KAIST)
Demo: a Prototype of Uplink NOMA Wi-Fi with Successive Interference Cancellation
Roman Zlobin (IITP RAS, Russia), Aleksey Kureev (IITP RAS and HSE University, Russia), Evgeny Khorov (IITP RAS and HSE University, Russia)
Demo: Feasibility of Simultaneous Transmit and Receive in Wi-Fi 7 Multi-Link Devices
Ilya Levitsky (IITP RAS), Yaroslav Okatev (IITP RAS), Evgeny Khorov (IITP RAS)
Demo: Federated Learning over Private 5G Networks
Seungyeol Lee (ETRI), Myung-Ki Shin (ETRI)
Poster: Distributed Inference for Multiple DNN Models in IoT Environments
YoungHwan Jin (Yonsei University), Hyung Bin Park (Yonsei University), SuKyoung Lee (Yonsei University)
Poster: Partial Federated Learning Based Network Intrusion System for Mobile Devices
Hyoseon Kye (Soongsil University), Minhae Kwon (Soongsil University)
Poster: Efficient Low-rank Federated Learning based on Singular Value Decomposition
Jungmin Kwon (Ewha Womans University), Hyunggon Park (Ewha Womans University)

Keynote 2.

Wednesday (October 19th, 09:20 - 10:20)

Session Chair: Changhee Joo, Korea University

6G Towards "The Next Hyper-Connected Experience for All"
Dr. Sunghyun Choi (Samsung Research, Samsung Electronics)
Abstract: Since the first commercial launch in 2019, 5G has grown to be the core infrastructure for a wide range of industries. It is used to support everything from high-quality communication to smart factories, vehicle-to-vehicle communication, and a whole raft of other new services. Future communication networks will require not only more powerful network equipment with vast amounts of information processing but also softwarization of communication technologies to make equipment flexible with lower costs. To overcome current technical challenges, strengthening the function of software and developing AI will be top priority, and furthermore research activities are essential to build 6G, the next-generation communication system, in both academia and industry. In this talk, I will discuss various aspects such as mega trends, services, requirements, candidate technologies towards 6G as a next-generation communication system along with the current developments status within Samsung.

Panel Discussion.

Wednesday (October 19th, 10:50 - 12:00)

Topic: What are the key challenges/questions that need to be addressed to make more efficient use of AI/ML techniques for next-generation networking (or to let AI/ML techniques settle in next-generation networking)?

Panelists:

Prof. Xiaojun Lin, Perdue University

Prof. Carlee Joe-Wong, Carnegie Mellon University

Prof. Javad Ghaderi, Columbia University

Prof. Dongsu Han, KAIST

Moderator: I-Hong Hou, Texas A&M University

Session 4: Network Resource Allocation.

Wednesday (October 19th, 13:30 - 14:40)

Session Chair: Jian Li, SUNY-Binghamton University

Correlated Combinatorial Bandits for Online Resource Allocation

Samarth Gupta, Jinhang Zuo, Carlee Joe-Wong, Gauri Joshi, Osman Yagan (Carnegie Mellon University)

Abstract: 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 𝑇 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.

Online Learning for Multi-Agent Based Resource Allocation in Weakly Coupled Wireless Systems

Jianhan Song, Gustavo de Veciana, Sanjay Shakkottai (The University of Texas at Austin)

Abstract: We propose and evaluate a learning-based framework to address multi-agent resource allocation in coupled wireless systems. In particular we consider, multiple agents (e.g., base stations, access points, etc.) that choose amongst a set of resource allocation options towards achieving their own performance objective /requirements, and where the performance observed at each agent is further coupled with the actions chosen by the other agents, e.g., through interference, channel leakage, etc. The challenge is to find the best collective action. To that end we propose a Multi-Armed Bandit (MAB) framework wherein the best actions (aka arms) are adaptively learned through online reward feedback. Our focus is on systems which are “weakly-coupled” wherein the best arm of each agent is invariant to others’ arm selection the majority of the time – this majority structure enables one to develop light weight efficient algorithms. This structure is commonly found in many wireless settings such as channel selection and power control. We develop a bandit algorithm based on the Track-and-Stop strategy, which shows a logarithmic regret with respect to a genie. Finally through simulation, we exhibit the potential use of our model and algorithm in several wireless application scenarios.

Achieving Efficiency via Fairness in Online Resource Allocation

Zhiyuan Wang (Beihang University); Jiancheng Ye, Dong Lin (Huawei); John C. S. Lui (The Chinese University of Hong Kong)

Abstract: The classic utility maximization framework studies the fairness-efficiency tradeoff in various resource allocation problems (e.g., bandwidth allocation). The weighted alpha-fair utility is a common utilitarian metric. However, this classic framework cannot tackle those allocation problems with the online decision-making requirement (e.g., caching capacity allocation under unknown requests). Existing studies on these online allocation problems largely follow the online learning approaches, thus inevitably overlook the allocation fairness. In this paper, we propose a novel utility maximization framework accommodating the online setting. The major challenge of designing this framework lies in the tight coupling between the desirable fairness guarantee and the unknown allocation efficiency. To tackle this, we integrate the weighted alpha-fair utility with the learning rationale, by properly devising the merit-based weights and the increasing fairness levels. Under our proposed framework, the utility-maximizing allocation in each time slot is weighted alpha-fair. Our framework also performs asymptotically as well as the offline optimal/efficient outcome. We demonstrate how this framework functions in two networking applications. In size-based scheduling, it enables network switches to prioritize short flows and avoid flow starvation without the prior flow size information. In file caching, our framework outperforms several state-of-the-art caching policies up to 21% in terms of cache-hit-ratio.

Session 5: Online Learning and Approximation.

Wednesday (October 19th, 15:10 - 16:20)

Session Chair: Jinhang Zuo, Carnegies Mellon University

Multi-User Terahertz WLANs with Angularly Dispersive Links

Keerthi Priya Dasala, Edward W. Knightly (Rice University)

Abstract: THz communication can realize the next order of magnitude in data rate and user densities due to the availability of wide THz-scale spectral bands. Wide bandwidth links can exhibit angular dispersion, i.e., frequency-dependent radiation direction. While angular dispersion has enabled path discovery and dynamic beam steering via frequency tuning, multi-user communication in THz links remains an unaddressed challenge.This paper presents the rst study and performance evaluation of multi-user THz WLANs with angularly dispersive links. We employ a single parallel-plate Leaky-Wave Antenna (LWA) for THz directional transmission and present a multi-user communication strategy that exploits angular dispersion and angular separation of users and provides all-spectrum access to users located in dierent directions with the objective of aggregate rate maximization. With analytical model-driven evaluations and over-the-air experiments, we show how the multi-user performance of an angularly dispersive LWA link fundamentally depends on frequency, angle, and bandwidth utilized by users, through non-linear mechanisms. As increasing bandwidth yields a larger signal footprint in LWA links, we demonstrate that as compared to the model prediction, not only is aggregate data rate maximized with wider beams, but that the experimental link is far better even for practical irregular beams with side lobes and asymmetry. Our experiments demonstrate that by exploiting angular dispersion and users’ angular separation, we can transmit without contention or medium access control up to 11 simultaneous users.

Power-of-2-Arms for Bandit Learning With Switching Costs

Ming Shi, Xiaojun Lin (Purdue University); Lei Jiao (University of Oregon)

Abstract: Motivated by edge computing with artificial intelligence, in this paper we study a bandit-learning problem with switching costs. Existing results in the literature either incur Θ(T^{2/3}) regret with bandit feedback, or rely on free full-feedback in order to reduce the regret to 𝑂(\sqrt{𝑇}). In contrast, we expand our study to incorporate two new factors. First, full feedback could incur a cost. Second, the player may choose 2 (or more) arms at a time, in which case she is free to use any one of the chosen arms to calculate loss, and switching costs are incurred only when she changes the set of chosen arms. For the setting where the player pulls only one arm at a time, our new regret lower-bound shows that, even when costly 2 full-feedback is added, the Θ(𝑇^{2/3}) regret still cannot be improved. However, the dependence on the number of arms may be improved when the full-feedback cost is small. In contrast, for the setting where the player can choose 2 (or more) arms at a time, we provide a novel online learning algorithm that achieves a lower 𝑂(\sqrt{𝑇}) regret. Further, our new algorithm does not need any full feedback at all. This sharp difference therefore reveals the surprising power of choosing 2 (or more) arms for this type of bandit-learning problems with switching costs. Both our new algorithm and regret analysis involve several new ideas, which may be of independent interest.

On Low-Complexity Quickest Intervention of Mutated Diffusion Processes Through Local Approximation

Qining Zhang, Honghao Wei (University of Michigan, Ann Arbor); Weina Wang (Carnegie Mellon University); Lei Ying (University of Michigan, Ann Arbor)

Abstract: We consider the problem of controlling a mutated diffusion process with an unknown mutation time. The problem is formulated as the quickest intervention problem with the mutation modeled by a change-point, which is a generalization of the quickest change- point detection (QCD). Our goal is to intervene in the mutated process as soon as possible while maintaining a low intervention cost with optimally chosen intervention actions. This model and the proposed algorithms can be applied to pandemic prevention (such as Covid-19) or misinformation containment. We formulate the problem as a partially observed Markov decision process (POMDP) and convert it to an MDP through the belief state of the change-point. We first propose a grid-approximation approach to calculate the optimal intervention policy, whose computational complexity could be very high when the number of grids is large. In order to reduce the computational complexity, we further propose a low-complexity threshold-based policy through the analysis of the first-order approximation of the value functions in the “local intervention” regime. Simulation results show the low-complexity algorithm has a similar performance as the grid-approximation approach and both perform much better than the QCD-based algorithms.

Session 6: Edge and Cloud Computing.

Wednesday (October 19th, 16:40 - 17:50)

Session Chair: Jeongho Kwak, DGIST

SYNTHESIS: A Semi-Asynchronous Path-Integrated Stochastic Gradient Method for Distributed Learning in Computing Clusters

Zhuqing Liu (The Ohio State University); Xin Zhang (Iowa State University); Jia Liu (The Ohio State University)

Abstract: To increase the training speed of distributed learning, recent years have witnessed a significant amount of interest in developing both synchronous and asynchronous distributed stochastic variance-reduced optimization methods. However, all existing synchronous and asynchronous distributed training algorithms suffer from various limitations in either convergence speed or implementation complexity. This motivates us to propose an algorithm called SYNTHESIS (semi-asynchronous path-integrated stochastic gradient search), which leverages the special structure of the variance-reduction framework to overcome the limitations of both synchronous and asynchronous distributed learning algorithms, while retaining their salient features. We consider two implementations of SYNTHESIS under distributed and shared memory architectures. We show that our SYNTHESIS algorithms have 𝑂( 𝑁𝜖 (Δ + 1) + 𝑁) and 𝑂( 𝑁𝜖 (Δ + 1)𝑑 + 𝑁) computational complexities for achieving an 𝜖-stationary point in non-convex learning under distributed and shared memory architectures, respectively, where 𝑁 denotes the total number of training samples and Δ represents the maximum delay of the workers. Moreover, we investigate the generalization performance of SYNTHESIS by establishing algorithmic stability bounds for quadratic strongly convex and non-convex optimization. We further conduct extensive numerical experiments to verify our theoretical findings.

Sharp Waiting-Time Bounds for Multiserver Jobs

Yige Hong, Weina Wang (Carnegie Mellon University)

Abstract: Multiserver jobs, which are jobs that occupy multiple servers simultaneously during service, are prevalent in today’s computing clusters. But little is known about the delay performance of systems with multiserver jobs. We consider queueing models for multiserver jobs in a scaling regime where the system load becomes heavy and meanwhile the total number of servers in the system and the number of servers that a job needs become large. Prior work has derived upper bounds on the queueing probability in this scaling regime. However, without proper lower bounds, the existing results cannot be used to dierentiate between policies. In this paper, we study the delay performance by establishing sharp bounds on the mean waiting time of multiserver jobs, where the waiting time of a job is the time spent in queueing rather than in service. We rst consider the commonly used First-Come-First-Serve (FCFS) policy and characterize the exact order of its mean waiting time. We then prove a lower bound on the mean waiting time of all policies, and demonstrate that there is an order gap between this lower bound and the mean waiting time under FCFS. We nally complement the lower bound with an achievability result: we show that under a priority policy that we call P-Priority, the mean waiting time achieves the order of the lower bound. This achievability result implies the tightness of the lower bound, the asymptotic optimality of P-Priority, and the strict suboptimality of FCFS.

Tackling Heterogeneous Traffic in Multi-access Systems via Erasure Coded Servers

Tuhinangshu Choudhury, Weina Wang, Gauri Joshi (Carnegie Mellon University)

Abstract: Most data generated by modern applications is stored in the cloud, and there is an exponential growth in the volume of jobs to access these data and perform computations using them. The volume of data access or computing jobs can be heterogeneous across different job types and can unpredictably change over time. Cloud service providers cope with this demand heterogeneity and unpredictability by over-provisioning the number of servers hosting each job type. In this paper, we propose the addition of erasure-coded servers that can flexibly serve multiple job types without additional storage cost. We analyze the service capacity region and the response time of such erasure-coded systems and compare them with standard uncoded replication-based systems currently used in the cloud. We show that coding expands the service capacity region, thus enabling the system to handle variability in demand for different data types. Moreover, we characterize the response time of the coded system in various arrival rate regimes. This analysis reveals that adding even a small number of coded servers can significantly reduce the mean response time, with a drastic reduction in regimes where the demand is skewed across different job types.

Session 7: Wireless Systems and Experimentation.

Thursday (October 20th, 09:10 - 10:20)

Session Chair: Jia (Kevin) Liu, The Ohio State University

Extracting and Predicting Multipath Profiles under High Mobility and Its Application

Ghufran Baig, Changhan Ge, Lili Qiu (The University of Texas at Austin); Yuanjie Li (Tsinghua University); Wangyang Li, Wei Sun, Jian He (The University of Texas at Austin); Zhehui Zhang, Songwu Lu (University of California, Los Angeles)

Abstract: The wireless signal propagates via multipath arising from different reflections and penetration between a transmitter and receiver. Extracting multipath profiles (e.g., delay and Doppler along each path) from received signals enables many important applications, such as channel prediction and crossband channel estimation (i.e., estimating the channel on a different frequency). The benefit of multipath estimation further increases with mobility since the channel in that case is less stable and more important to track. Yet high-speed mobility poses significant challenges to multipath estimation. In this paper, instead of using time-frequency domain channel representation, we leverage the delay-Doppler domain representation to accurately extract and predict multipath properties. Specifically, we use impulses in the delay-Doppler domain as pilots to estimate the multipath parameters and apply the multipath information to predicting wireless channels as an example application. Our design rationale is that mobility is more predictable than the wireless channel since mobility has inertial while the wireless channel is the outcome of a complicated interaction between mobility, multi-path, and noise. We evaluate our approach via both acoustic and RF experiments, including vehicular experiments using USRP. Our results show that the estimated multipath matches the ground truth, and the resulting channel prediction is more accurate than the traditional channel prediction schemes.

BioTag: Robust RFID-based Continuous User Verification Using Physiological Features from Respiration

Bin Hu (Rutgers University); Tianming Zhao, Yan Wang (Temple University); Jerry Cheng (New York Institute of Technology); Richard Howard (Wireless Information Network Laboratory (WINLAB), Rutgers University); Yingying Chen (Rutgers University); Hao Wan (New York Institute of Technology)

Abstract: For decades, one-time verification has been the standard for user verification at entry points, office rooms, etc. However, such approaches request users to provide their secrets (e.g., entering passwords and collecting fingerprints) and re-verify (e.g., screen shut- down) manually. Thus, they cannot confirm whether the user is a legitimate or an imposter after verification, which raises the urgent demand for a more convenient and secure solution to perform continuous user verification. However, existing continuous verification methods heavily rely on users’ active participation, which is inconvenient. Toward this end, we propose a continuous user verification system, BioTag, which utilizes the low-cost radio frequency identification (RFID) technology to capture unique physiological characteristics rooted in the users’ respiration motions for continuous user verification. Specifically, we use two RFID tags attached to a user’s chest and abdomen to capture the user’s intrinsic respiratory patterns via RFID signals. We develop respiratory feature extraction methods based on waveform morphology analysis and fuzzy wavelet transformation (FWPT) to derive unique biometric information from the user’s respiration signals. Furthermore, we develop an adaptive classifier using the gradient boosting decision tree (GBDT) to identify legitimate users and attackers accurately. Extensive experiments involving 41 participants demonstrate that BioTag can robustly authenticate users and detect various types of adversaries with low training effort. In particular, our system can achieve over 95.2% and 94.8% verification accuracy on random attack and imitation attack scenarios, respectively.

Outdoor-to-Indoor 28 GHz Wireless Measurements in Manhattan: Path Loss, Location Impacts, and 90% Coverage

Manav Kohli, Abhishek Adhikari, Gulnur Avci, Sienna Brent (Columbia University); Jared Moser (Stuyvesant High School); Sabbir Hossain (City College of New York); Aditya Dash, Igor Kadota (Columbia University); Rodolfo Feick (Universidad Tecnica Federico Santa Maria); Dmitry Chizhik, Jinfeng Du, Reinaldo A. Valenzuela (Nokia Bell Labs); Gil Zussman (Columbia University)

Abstract: Outdoor-to-indoor (OtI) signal propagation further challenges link budgets at millimeter-wave (mmWave). To gain insight into OtI mmWave at 28 GHz, we conducted an extensive measurement campaign consisting of over 2,000 link measurements in West Harlem, New York City, covering seven highly diverse buildings. A path loss model constructed over all links shows an average of 30 dB excess loss over free space at distances beyond 50 m. We find the type of glass to be the dominant factor in OtI loss, with 20 dB observed difference between clustered scenarios with low- and high-loss glass. Other factors, such as difference in floor height, are found to have an impact between 5ś10 dB. We show that for urban buildings with high-loss glass, OtI data rates up to 400 Mb/s are supported for 90% of indoor users by a base station (BS) up to 49 m away. For buildings with low-loss glass, such as our case study covering multiple classrooms of a public school, data rates over 2.8/1.4 Gb/s are possible from a BS 68/175 m away when a line-of-sight path is available. We expect these results to be useful for the deployment of OtI mmWave networks in dense urban environments and the development of scheduling and beam management algorithms.

Session 8: Privacy and Blockchains.

Thursday (October 20th, 10:50 - 12:00)

Session Chair: Yin Sun, Auburn University

Online Incentive Mechanism for Task Offloading with Privacy-Preserving in UAV-assisted Mobile Edge Computing

Ruiting Zhou, Renli Zhang, Yufeng Wang (Wuhan University); Haisheng Tan (University of Science and Technology of China); Kun He (Wuhan university)

Abstract: Unmanned aerial vehicles (UAVs) have emerged as a promising technology to provide low-latency mobile edge computing (MEC) services. To fully utilize the potential of UAV-assisted MEC in practice, both technical and economic challenges need to be addressed: how to optimize UAV trajectory for online task offloading and incen- tivize the participation of UAVs without compromising the privacy of user equipment (UE). In this work, we consider unique features of UAVs, i.e., high mobility as well as limited energy and computing capacity, and propose a privacy-preserving auction framework, Ptero, to schedule offloading tasks on the fly and incentivize UAVs’ participation. Specifically, Ptero first decomposes the online task offloading problem into a series of one-round problems by scaling the UAV’s energy constraint into the objective. To protect UE’s privacy, Ptero calculates UAV’s coverage based on subset-anonymity. At each round, Ptero schedules UAVs greedily, computes remuneration for working UAVs, and processes unserved tasks in the cloud to maximize the system’s utility (i.e., minimize social cost). Theoretical analysis proves that Ptero achieves truthfulness, individual rationality, computational efficiency, privacy preserving and a nontrivial competitive ratio. Trace-driven evaluations further verify that Ptero can reduce the social cost by up to 116% compared with four state-of-the-art algorithms.

Performance and Efficiency Tradeoffs in Blockchain Overlay Networks

Parikshit Hegde, Gustavo de Veciana (The University of Texas at Austin)

Abstract: Underlying blockchain’s scalability and performance is a Peer-to-Peer (P2P) overlay network and protocols for relaying blocks and transactions among participating nodes. In this work, we model and perform a systematic analysis of blockchain communication proto- cols. We begin by introducing the performance metric of interest for blockchains, the sequence of ordered-completion-times, which captures the progress distributed nodes are making in jointly con- structing a consistent blockchain. We then study the characteristics of block relaying protocols. In particular, we show that when nodes cannot perform cut-through relaying, there is no optimal causal block relaying protocol if block relaying times are deterministic. We propose a simple age-based block relaying protocol that is provably near-optimal in terms of minimizing ordered-completion-times when the P2P overlay network is a tree. This analysis is relevant to blockchain relay networks such as Bitcoin-Fibre, Bloxroute etc., where the core part of the overlay is a tree. Finally, using the insights derived for tree overlays, we explore the interplay between transaction and block relaying and prioritization (age, size, FCFS based) on both tree and fully connected overlays via simulation. We observe that policies that relay blocks and incorporate transactions into blocks based on ‘age’ outperform other natural policies. We also explore a fundamental tradeoff between mining and computational efficiencies and performance (in terms of ordered completion times).

Optimal Bootstrapping of PoW Blockchains

Ranvir Rana (University of Illinois Urbana Champaign); Dimitris Karakostas (University of Edinburgh); Sreeram Kannan (University of Washington Seattle); Aggelos Kiayias (University of Edinburgh and IOHK); Pramod Viswanath (University of Illinois Urbana Champaign)

Abstract: Proof of Work (PoW) blockchains are susceptible to adversarial majority mining attacks in the early stages due to incipient participation and corresponding low net hash power. Bootstrapping ensures safety and liveness during the transient stage by protecting against a majority mining attack, allowing a PoW chain to grow the participation base and corresponding mining hash power. Live- ness is especially important since a loss of liveness will lead to loss of honest mining rewards, decreasing honest participation, hence creating an undesired spiral; indeed existing bootstrapping mechanisms offer especially weak liveness guarantees. In this paper, we propose Advocate, a new bootstrapping methodology, which achieves two main results: (a) optimal liveness and low latency under a super-majority adversary for the Nakamoto longest chain protocol and (b) immediate black-box generalization to a variety of parallel-chain based scaling architectures, including OHIE [34] and Prism [4]. We demonstrate via a full-stack implementation the robustness of Advocate under a 90% adversarial majority.