Venue of SIGMETRICS 2021

ACM SIGMETRICS 2021

Beijing, China
June 14-18, 2021

Session 1A: (Learning) BANDITS AND FRIENDS

  • (1:30 pm) Federated Bandit: A Gossiping Approach by Zhaowei Zhu (University of California, Santa Cruz), Jingxuan Zhu (Stony Brook University), Ji Liu (Stony Brook University), Yang Liu (University of California, Santa Cruz)
  • (1:55 pm) Statistically Efficient, Polynomial-Time Algorithms for Combinatorial Semi-Bandits by Thibaut Cuvelier (Orange Labs & CentraleSupélec), Richard Combes (CentraleSupélec), Eric Gourdin (Orange Labs)
  • (2:20 pm) Information Aggregation for Constrained Online Control by Tongxin Li (California Institute of Technology), Yue Chen (Tsinghua University), Bo Sun (The Hong Kong University of Science and Technology), Adam Wierman (California Institute of Technology), Steven H. Low (California Institute of Technology)

Session 1B: (Measurement) WHERE ARE YOU GOING?

  • (1:30 pm) Where did my 256GB go? Large-scale Analysis of Mobile Storage Consumption by Ashish Bijlani (Georgia Tech), Kishore Ramachandran (Georgia Tech), Roy H. Campbell (University of Illinois at Urbana-Champaign)
  • (1:55 pm) A Measurement Study of Wechat Mini-Apps by Yue Zhang (Computer Science & Engineering, Ohio State University), Bayan Turkistani (Computer Science & Engineering, Ohio State University), Allen Yuqing Yang (Ohio State University), Chaoshun Zuo (Ohio State University), Zhiqiang Lin (Ohio State University)
  • (2:20 pm) PredictRoute: A Network Path Prediction Toolkit by Rachee Singh (Microsoft/University of Massachusetts Amherst), David Tench (University of Massachusetts Amherst), Phillipa Gill (University of Massachusetts Amherst), Andrew McGregor (University of Massachusetts Amherst)
  • (2:45 pm) A Look Behind the Curtain: Traffic Classification in an Increasingly Encrypted Web by Iman Akbari (University of Waterloo), Mohammad A. Salahuddin (University of Waterloo), Leni Ven (University of Waterloo), Noura Limam (University of Waterloo), Raouf Boutaba (University of Waterloo), Bertrand Mathieu (Orange Labs), Stephanie Moteau (Orange Labs), Stephane Tuffin (Orange Labs)

Session 2A: (Theory) TO SCHEDULE OR NOT TO SCHEDULE

  • (3:15 pm) Online Virtual Machine Allocation with Lifetime and Load Predictions by Niv Buchbinder (Tel Aviv University and Microsoft Research), Yaron Fairstein (Technion), Konstantina Mellou (Microsoft Research), Ishai Menache (Microsoft Research), Joseph (Seffi) Naor (Technion)
  • (3:40 pm) Nudge: Stochastically Improving upon FCFS by Isaac Grosof (Carnegie Mellon University) Kunhe Yang (Tsinghua University), Ziv Scully (Carnegie Mellon University), Mor Harchol-Balter (Carnegie Mellon University)
  • (4:05 pm) Zero Queueing for Multi-Server Jobs by Weina Wang (Carnegie Mellon University), Qiaomin Xie (Cornell University), Mor Harchol-Balter (Carnegie Mellon University)
  • (4:30 pm) The Gittins Policy is Nearly Optimal in the M/G/k under Extremely General Conditions by Ziv Scully (Carnegie Mellon University), Isaac Grosof (Carnegie Mellon University; Mor Harchol-Balter (Carnegie Mellon University)

Session 3A: (Theory) SHARING IS CARING

  • (8:30 am) Achieving Zero Asymptotic Queueing Delay for Parallel Jobs by Wentao Weng (Tsinghua University), Weina Wang (Carnegie Mellon University)
  • (8:55 am) Achievable Stability in Redundancy Systems by Youri Raaijmakers (Eindhoven University of Technology), Sem Borst (Eindhoven University of Technology (TU/e))
  • (9:20 am) On the Asymptotic Insensitivity of the Supermarket Model in Processor Sharing Systems by Grzegorz Kielanski (University of Antwerp), Benny Van Houdt (University of Antwerp)
  • (9:45 am) Refining Mean-field Approximations by Dynamic State Truncation by Francesca Randone (IMT School for Advanced Studies Lucca), Luca Bortolussi (University of Trieste), Mirco Tribastone (IMT School for Advanced Studies Lucca)

Session 3B: (Measurement) FOLLOW THE MONEY

  • (8:30 am) Tracking Counterfeit Cryptocurrency End-to-end by Bingyu Gao (Beijing University of Posts and Telecommunications), Haoyu Wang (Beijing University of Posts and Telecommunications), Pengcheng Xia (Beijing University of Posts and Telecommunications), Siwei Wu (Zhejiang University), Yajin Zhou (Zhejiang University), Xiapu Luo (The Hong Kong Polytechnic University), Gareth Tyson (Queen Mary University of London)
  • (8:55 am) SADPonzi: Detecting and Characterizing Ponzi Schemes in Ethereum Smart Contracts by Weimin Chen (Beijing University of Posts and Telecommunications), Xinran Li (Beijing University of Posts and Telecommunications), Yuting Sui (Beijing University of Posts and Telecommunications), Ningyu He (Peking University), Haoyu Wang (Beijing University of Posts and Telecommunications), Lei Wu (Zhejiang University), Xiapu Luo (The Hong Kong Polytechnic University)
  • (9:20 am) adPerf: Characterizing the Performance of Third-party Ads by Behnam Pourghassemi (University of California, Irvine), Jordan Bonecutter (University of California, Irvine), Zhou Li (University of California, Irvine), Aparna Chandramowlishwaran (University of California, Irvine)

Session 4A: (Theory) THE LOAD BALANCING ACT

  • (3:30 pm) Optimal Load Balancing with Locality Constraints by Wentao Weng (Tsinghua University), Xingyu Zhou (The Ohio State University), R Srikant (UIUC)
  • (3:55 pm) Load Balancing Under Strict Compatibility Constraints by Daan Rutten (Georgia Institute of Technology), Debankur Mukherjee (Georgia Institute of Technology)
  • (4:20 pm) Mean Waiting Time in Large-Scale and Critically Loaded Power of d Load Balancing Systems by Tim Hellemans (University of Antwerp), Benny Van Houdt (University of Antwerp)
  • (4:45 pm) Improving the performance of heterogeneous data centers through redundancy by Elene Anton (CNRS-IRIT, Toulouse INP), Urtzi Ayesta (CNRS-IRIT and Ikerbasque/Univ. Basque Country), Matthieu Jonckheere (University of Buenos Aires), Maaike Verloop (IRIT-CNRS)

Session 4B: (Systems) ALL SYSTEMS GO

  • (3:30 pm) A Systematic Framework to Identify Violations of Scenario-dependent Driving Rules in Autonomous Vehicle Software by Qingzhao Zhang (University of Michigan), Ke David Hong (University of Michigan), Ze Zhang (University of Michigan), Qi Alfred Chen (UC Irvine), Scott Mahlke (University of Michigan/Nvidia Research), Z. Morley Mao (University of Michigan)
  • (3:55 pm) SUGAR: Speeding Up GPGPU Application Resilience Estimation with Input Sizing by Lishan Yang (William & Mary), Bin Nie (William & Mary), Adwait Jog (William & Mary), Evgenia Smirni (William & Mary)
  • (4:20 pm) Mix and Match: Reorganizing Tasks for Enhancing Data Locality by Xulong Tang (University of Pittsburgh, USA), Mahmut Taylan Kandemir (Penn State, USA), Mustafa Karakoy (TUBITAK-BILGEM, Turkey)

Session 5A: (Theory) THE PRICE IS RIGHT

  • (9:00 am) On Private Peering Agreements between Content and Access Providers: A Contractual Equilibrium Analysis by Xin Wang (National University of Singapore), Richard Ma (National University of Singapore)
  • (9:25 am) I Know What You Bought At Chipotle for 9.81 by Solving A Linear Inverse Problem by Michael Fleder (Massachusetts Institute of Technology), Devavrat Shah (Massachusetts Institute of Technology)
  • (9:50 am) Dynamic Pricing and Matching for Two-Sided Markets with Strategic Servers by Sushil Mahavir Varma (Georgia Institute of Technology), Francisco Castro (University of California, Los Angeles), Siva Theja Maguluri (Georgia Institute of Technology)

Session 5B: (Theory) MIXED KNAPSACK

  • (9:00 am) Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint by Jing Tang (National University of Singapore), Xueyan Tang (Nanyang Technological University), Andrew Lim (National University of Singapore), Kai Han (University of Science and Technology of China), Chongshou Li (National University of Singapore), Junsong Yuan (State University of New York at Buffalo)
  • (9:25 am) Approximation Algorithms for Submodular Data Summarization with a Knapsack Constraint by Kai Han (University of Science and Technology of China), Shuang Cui (University of Science and Technology of China), Tianshuai Zhu (University of Science and Technology of China), Enpei Zhang (University of Science and Technology of China), Benwei Wu (University of Science and Technology of China), Zhizhuo Yin (University of Science and Technology of China), Tong Xu (University of Science and Technology of China), Shaojie Tang (University of Texas at Dallas), He Huang (Soochow University)
  • (9:50 am) Competitive Algorithms for the Online Multiple Knapsack Problem with Application to Electric Vehicle Charging by Bo Sun (The Hong Kong University of Science and Technology), Ali Zeynali (University of Massachusetts Amherst), Tongxin Li (California Institute of Technology), Mohammad Hajiesmaili (University of Massachusetts Amherst), Adam Wierman (California Institute of Technology), Danny H.K. Tsang (The Hong Kong University of Science and Technology)

Session 6A: (Theory) VARIOUS THEORISTS

  • (3:00 pm) Input-Dynamic Distributed Algorithms for Communication Networks by Klaus-Tycho Foerster (University of Vienna), Janne H. Korhonen (IST Austria), Ami Paz (University of Vienna), Joel Rybicki (IST Austria), Stefan Schmid (University of Vienna)
  • (3:25 pm) Real-time approximate routing for smart transit systems by Noémie Périvier (Columbia University), Chamsi Hssaine (Cornell University), Samitha Samaranayake (Cornell University), Siddhartha Banerjee (Cornell University)
  • (3:50 pm) Bregman-style Online Convex Optimization with Energy Harvesting Constraints by Kamiar Asgari (University of Southern California), Michael Neely (University of Southern California)
  • (4:15 pm) The Power of D-hops in Matching Power-Law Graphs by LIREN YU (Purdue University), Jiaming Xu (Duke University), Xiaojun Lin (Purdue University)

Session 6B: (Measurement) THE TRUTH IS OUT THERE

  • (3:00 pm) Chasm in Hegemony: Explaining and Reproducing Disparities in Homophilous Networks by Yiguang Zhang (Columbia University), Jessy Xinyi Han (Massachusetts Institute of Technology), Ilica Mahajan (Columbia University), Priyanjana Bengani (Columbia University), Augustin Chaintreau (Columbia University)
  • (3:25 pm) Magma: A Ground-Truth Fuzzing Benchmark by Ahmad Hazimeh (EPFL), Adrian Herrera (Defence Science and Technology Group), Mathias Payer (EPFL)
  • (3:50 pm) Stay Connected, Leave no Trace: Enhancing Security and Privacy in WiFi via Obfuscating Radiometric Fingerprints by Luis F. Abanto-Leon (Technical University of Darmstadt), Andreas Bäuml (Technical University of Darmstadt), Gek Hong (Allyson) Sim (Technical University of Darmstadt), Matthias Hollick (Technical University of Darmstadt), Arash Asadi (Technical University of Darmstadt)

Highlights beyond SIGMETRICS

ChonLam Lao

Tsinghua University

ATP: In-network Aggregation for Multi-tenant Learning

Abstract
Distributed deep neural network training (DT) systems are widely deployed in clusters where the network is shared across multiple tenants, i.e., multiple DT jobs. Each DT job computes and aggregates gradients. Recent advances in hardware accelerators have shifted the the performance bottleneck of training from computation to communication. To speed up DT jobs' communication, we propose ATP, a service for in-network aggregation aimed at modern multi-rack, multi-job DT settings. ATP uses emerging programmable switch hardware to support in-network aggregation at multiple rack switches in a cluster to speedup DT jobs. ATP performs decentralized, dynamic, best-effort aggregation, enables efficient and equitable sharing of limited switch resources across simultaneously running DT jobs, and gracefully accommodates heavy contention for switch resources. ATP outperforms existing systems accelerating training throughput by up to 38% - 66% in a cluster shared by multiple DT jobs.

Biography
ChonLam Lao is a master's student in Computer Science at IIIS Tsinghua University, advised by Professor Wenfei Wu. Next year, he will study for a doctoral degree at Harvard University co-advised by Professor Minlan Yu and Professor Aditya Akella. His research primary focuses on programmable networks and machine learning systems. Recently, his paper "ATP: In-network Aggregation for Multi-tenant Learning" is accepted and received the best paper award at NSDI 2021.

Michael Lingzhi Li

MIT

Forecasting Covid-19 With Application To Vaccine Trial Design and Distribution

Abstract
To help combat the COVID-19 pandemic and understand the impact of government interventions, we develop DELPHI, a novel epidemiological model. We applied DELPHI across over 200 regions since early April 2020 with consistently high predictive power, and is a key contributor to the core CDC ensemble forecast. DELPHI compares favorably with other models and predicted large-scale epidemics in areas such as South Africa and Russia weeks before realization. Furthermore, using DELPHI, we can quantify the impact of interventions and provide insights on future virus incidence under different policies. We illustrate how Janssen Pharmaceuticals (J&J) effectively utilized such analysis from DELPHI to optimally select the Phase III trial locations of the first single-dose vaccine Ad26.Cov2.S, accelerating the trial by 8 weeks while reducing the number of participants needed by 25%. We also demonstrate how DELPHI informed FEMA on optimizing vaccine distribution under constrained supply to minimize the number of pandemic deaths.

Biography
Michael Lingzhi Li is a doctoral candidate at the MIT Operations Research Center, advised by Prof. Dimitris Bertsimas. His research interests primarily focus on scalable algorithms that combine machine learning and optimization, with emphasis on real-world applications in both healthcare and supply chain management. He has worked on problems in interpretable machine learning, personalized risk predictions, medical therapy prescription, infectious disease epidemiology, warehouse optimization and labor scheduling. He is the recipient of awards including the 2021 Innovative Applications in Analytics Award, the 2020 INFORMS Pierskalla Award and the 2019 MSOM Best Student Paper Finalist Award.

Ayush Sekhari

Cornell University

Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations

Abstract
We design an algorithm which finds an ϵ-approximate stationary point (with ‖∇F(x)‖≤ϵ) using O(ϵ−3) stochastic gradient and Hessian-vector products, matching guarantees that were previously available only under a stronger assumption of access to multiple queries with the same random seed. We prove a lower bound which establishes that this rate is optimal and---surprisingly---that it cannot be improved using stochastic pth order methods for any p≥2, even when the first p derivatives of the objective are Lipschitz. Together, these results characterize the complexity of non-convex stochastic optimization with second-order methods and beyond. Expanding our scope to the oracle complexity of finding (ϵ,γ)-approximate second-order stationary points, we establish nearly matching upper and lower bounds for stochastic second-order methods. Our lower bounds here are novel even in the noiseless case.
This is joint work with Yossi Arjevani, Yair Carmon, John Duchi, Dylan J. Foster and Karthik Sridharan.

Biography
Ayush is a PhD student in the Computer Science department at Cornell University, advised by Professor Karthik Sridharan and Professor Robert D. Kleinberg. His research interests span across optimization, online learning, reinforcement learning and control, and the interplay between them. Before coming to Cornell, he spent a year at Google as a part of the Brain residency program. Before Google, he completed his undergraduate studies in computer science from IIT Kanpur in India where he was awarded the President's gold medal.