pwc-archive/papers-with-abstracts huggingface dataset:
Designing Replicable Networking Experiments with TriScale
Authors: Anonymous
Date: 2021-08-02 00:00:00
Proceeding: JSYS Aug_Papers 2021 1

When designing their performance evaluations, networking researchers often encounter questions such as: How long should a run be? How many runs to perform? How to account for the variability across multiple runs? What statistical methods should be used to analyze the data? Despite their best intentions, researchers often answer these questions differently, thus impairing the replicability of their  evaluations and the confidence in their results.  

In this paper, we propose a concrete methodology for the design and analysis of performance evaluations. Our approach  hierarchically partitions the performance evaluation into three timescales, following the principle of separation of concerns. The idea is to understand, for each timescale, the temporal characteristics of variability sources, and then to apply rigorous statistical methods to derive  performance results with quantifiable confidence in spite of the inherent variability. We implement this methodology in a software  framework called TriScale. For each performance metric, TriScale computes a variability score that estimates, with a given confidence, how similar the results would be if the evaluation were replicated; in other words, TriScale quantifies the replicability of evaluations. We showcase the practicality and usefulness of TriScale on four different case studies demonstrating that TriScale helps to generalize and strengthen published results. 

Improving the standards of replicability in networking is a complex challenge. This paper is an important  contribution to this endeavor; it provides networking researchers with a rational and concrete experimental methodology rooted in sound  statistical foundations. The first of its kind.
SoK: A Generalized Multi-Leader State Machine Replication Tutorial
Authors: Michael Whittaker, Neil Giridharan, Adriana Szekeres, Joseph Hellerstein, Ion Stoica
Date: 2021-03-01 00:00:00
Proceeding: JSYS Mar_Papers 2021 3

MultiPaxos and Raft are the two most popular and widely deployed state machine replication protocols. There is a more sophisticated family of generalized multi-leader state machine replication protocols like EPaxos, Caesar, and Atlas that have better performance, but they are extremely complicated and hard to understand. Due to their complexity, they have seen little to no industry adoption, and academically there has been a lack of clarity in analyzing, comparing, and extending the protocols. This paper is a tutorial on generalized multi-leader protocols. We explain why the protocols work the way they do, what they have in common, where they differ, which parts of the protocols are straightforward, which are more subtle than they appear, and so on. In doing so, we present four new generalized multi-leader protocols, identify key insights into existing protocols, and taxonomize the space.
Solution: Matchmaker Paxos: A Reconfigurable Consensus Protocol
Authors: Michael Whittaker, Neil Giridharan, Adriana Szekeres, Joseph Hellerstein, Heidi Howard, Faisal Nawab, Ion Stoica
Date: 2021-03-02 00:00:00
Proceeding: JSYS Mar_Papers 2021 3

State machine replication protocols, like MultiPaxos and Raft, are at the heart of numerous distributed systems. To tolerate machine failures, these protocols must replace failed machines with new machines, a process known as reconfiguration. Reconfiguration has become increasingly important over time as the need for frequent reconfiguration has grown. Despite this, reconfiguration has largely been neglected in the literature. In this paper, we present Donut Paxos and Donut MultiPaxos, a reconfigurable consensus and state machine replication protocol respectively. Our protocols can perform a reconfiguration with little to no impact on the latency or throughput of command processing; they can perform a reconfiguration in a few milliseconds; and they present a framework that can be generalized to other replication protocols in a way that previous reconfiguration techniques can not. We provide proofs of correctness for the protocols and
optimizations, and present empirical results from an open source implementation showing that throughput and latency do not change significantly during a reconfiguration.
SoK: Function-as-a-Service: From An Application Developer's Perspective
Authors: Ali Raza, Ibrahim Matta, Nabeel Akhtar, Vasiliki Kalavri, Vatche Isahagian
Date: 2021-03-02 00:00:00
Proceeding: JSYS Mar_Papers 2021 3
Tasks: Management

In the past few years, FaaS has gained significant popularity and became a go-to choice for deploying cloud applications and micro-services. FaaS with its unique 'pay as you go' pricing model and key performance benefits over other cloud services, offers an easy and intuitive programming model to build cloud applications. In this model, a developer focuses on writing the code of the application while infrastructure management is left to the cloud provider who is responsible for the underlying resources, security, isolation, and scaling of the application. Recently, a number of commercial and open-source FaaS platforms have emerged, offering a wide range of features to application developers. In this paper, first, we present measurement studies demystifying various features and performance of commercial and open-source FaaS platforms that can help developers with deploying and configuring their serverless applications. Second, we discuss the distinct performance and cost benefits of FaaS and interesting use cases that leverage the performance, cost, or both aspects of FaaS. Lastly, we discuss challenges a developer may face while developing or deploying a serverless application. We also discuss state of the art solutions and open problems.
SURFBoard: Reproducible Performance Analysis for Distributed Machine Learning Workflows
Authors: Anonymous
Date: 2021-03-02 00:00:00
Proceeding: JSYS Mar_Papers 2021 3
Tasks: BIG-bench Machine Learning

Large-scale HPC infrastructures are enablers for scientific research in many domains. The recent advances in machine learning (ML) have led to an ever increasing demand for computation power, as well as the design of complex operational workflows. Understanding the performance and efficiency of these workflows is key to productivity, knowledge and model sharing, and energy efficiency. Even though there have been efforts in studying and designing portability protocols, performance analysis of large-scale ML is still an expert-driven task, tightly locked-in to specific physical and software infrastructure. Much like in other domains, this hinders reproducibility of both results and overall workflow performance. To overcome this challenge, we propose the design of a container-based framework for reproducible performance analysis of ML workflows at scale. We validate our framework using a case-study on two different large-scale production systems running ML workflows. We show empirically that our containerized approach is portable and allows arbitrarily low-level performance evaluation when run on two different, production-based HPC clusters with hundreds of GPUs. We report our findings on widely-used open-source software stacks and datasets and offer practitioners insights into what types of analyses our framework enables. To benefit the community, we open-source our software and results.
Test Submission
Authors: Anonymous
Date: 2021-03-01 00:00:00
Proceeding: JSYS May_Papers 2021 1

Test submission
ALCC: Migrating Congestion Control to the Application Layer in Cellular Networks
Authors: Anonymous
Date: 2021-05-03 00:00:00
Proceeding: JSYS May_Papers 2021 1

TCP is known to perform poorly in cellular network environments. Yet, most mobile applications are explicitly built on the conventional TCP stack or implicitly leverage TCP tunnels to various cellular middleboxes, including performance-enhancing proxies, application-specific edge proxies, VPN proxies and NAT boxes.  Despite significant advances in the design of new congestion control (CC) protocols for cellular networks, deploying these protocols without bypassing the underlying TCP tunnels has remained a challenging proposition.
    This paper proposes the design of a new \emph{Application Layer Congestion Control (ALCC)} framework that allows any new CC protocol to be implemented easily at the application layer, within or above an application-layer protocol that sits atop a legacy TCP stack. It drives it to deliver approximately the same as the native performance. The ALCC socket sits on top of a traditional TCP socket. Still, it can leverage the large congestion windows opened by TCP connections to carefully execute an application-level CC within the window bounds of the underlying TCP connection. This paper demonstrates how ALCC can be applied to three well-known cellular CC protocols: Verus, Copa, and Sprout. For these protocols, ALCC can achieve comparable throughput and delay characteristics (within 3-10\%) as the native protocols at the application layer across different networks and traffic conditions. ALCC allows a server-side implementation of these protocols with no client modifications and with zero bytes overhead. The ALCC framework can be easily integrated with off-the-shelf applications such as file transfers and video streaming.
Solution: SRB: SCALABLE AND ROBUST BFT FOR DECENTRALIZED NETWORKS
Authors: Anonymous
Date: 2021-05-03 00:00:00
Proceeding: JSYS May_Papers 2021 1

  This paper presents SRB, a robust Byzantine fault-tolerant (BFT) total order broadcast protocol
  aimed at maximizing throughput on wide-area networks (WANs),
  targeting deployments in decentralized networks,
  such as permissioned and Proof-of-Stake permissionless blockchain systems.
 SRB is developed open-source and is planned to be integrated in a major permissioned blockchain project.

  SRB is the first BFT protocol that allows multiple leaders to propose request batches independently
  (i.e., parallel leaders), while effectively precluding performance degradation due to request duplication
  by rotating the assignment of a partitioned request hash space to leaders.
  As this mechanism removes the single-leader bandwidth bottleneck
  and exposes a computation bottleneck related to authenticating clients even on a WAN,
  our protocol further boosts throughput using a client signature verification sharding optimization.
  Our evaluation shows that SRB outperforms state-of-the-art
  single-leader protocols
  and orders more than 60000 signed Bitcoin-sized (500-byte) transactions per second
  on a widely distributed 100 nodes, 1 Gbps WAN setup, with typical latencies of few seconds.
  Moreover, our evaluation exposes the impact of duplicate requests on parallel leader protocols which SRB eliminates.
  We also evaluate SRB under different crash and Byzantine faults, demonstrating its performance robustness.

  SRB relies on classical BFT protocol constructs, which simplifies reasoning about its correctness.
  Specifically, SRB is a generalization of the celebrated and scrutinized PBFT protocol.
  In a nutshell, SRB follows PBFT ``safety-wise'', with changes needed to accommodate novel features restricted to PBFT liveness.
Prepare your video for streaming with Segue
Authors: Anonymous
Date: 2021-11-01 00:00:00
Proceeding: JSYS Nov_Papers 2021 9
Tasks: Chunking

We identify new opportunities in video streaming, involving the joint consideration of offline video chunking and online rate adaptation. We observe that due to a video's complexity varying over time, certain parts are more likely to cause performance impairments during playback with a particular rate adaptation algorithm. To address this, we propose careful use of variable-length video segments, and augmentation of certain segments with additional bitrate tracks. The key novelty of Segue is in making these decisions based on the video's time-varying complexity and the expected rate adaptation  behavior over time. We propose and implement several methods for such adaptation-aware chunking. Our results show that Segue substantially reduces rebuffering and quality fluctuations, while maintaining video quality delivered; Segue improves QoE by $9\%$ on average, and by $22\%$ in low-bandwidth conditions. Beyond our specific approach, we view our problem framing as a first step in a new thread on algorithmic and design innovation in video streaming, and leave the reader with several interesting open questions.
ML Reproducibility Systems: Status and Research Agenda
Authors: Anonymous
Date: 2021-11-02 00:00:00
Proceeding: JSYS Nov_Papers 2021 9
Tasks: Management, Navigate

As companies are more and more leveraging the power of machine learning (ML), ML models, the data they were trained on, and the training pipelines themselves, are becoming increasingly important assets. Hence, a new set of tools is being developed, which aim to help manage the ML model lifecycle in a more structured way. As the model lifecycle involves a lot of experimental back-and-forth, reproducibility is an important aspect that such tools need to provide. However, as model lifecycle management is an emerging field, only few best practices on how to support reproducibility exist. This led to a large variety of tools being developed that all have the same goal of providing reproducibility but with major differences in how this goal is achieved. As a result, users are overwhelmed with having to navigate this vast tooling landscape and having to choose a tool that best fits their needs. This is a difficult task as the reproducibility capabilities of different tools can vary and users need to determine themselves, what is supported and what functionalities would fit their specific use case.

In this paper, our goal is to add structure to the process of deciding on a specific tool in terms of its reproducibility capabilities. We identify the most significant artifacts of the ML model lifecycle and, based on these, propose a generic classification framework that allows to assess the reproducibility capabilities of a specific tool and make it comparable to other tools. To evaluate our framework, we conduct an analysis of 12 popular ML lifecycle management tools. We study each tool in detail and classify it according to our framework. We then compare the tools to each other to determine what degree of reproducibility is provided in general and where reproducibility support is still lacking. While overall we find that the majority of tools offers most features that are required for full reproducibility, there still exist gaps in terms of automating reproducibility and cross-tool reproducibility. Based on these findings, we provide a set of research challenges which need to be addressed in order to better understand reproducibility and to fill the gaps of current systems.
Solution: End-to-end Scheduling of Real-time Task Pipelines on Multiprocessors
Authors: Anonymous
Date: 2021-11-01 00:00:00
Proceeding: JSYS Nov_Papers 2021 9
Tasks: Scheduling

Task pipelines are common in today's embedded systems, as data moves from source to sink in a sensing-processing-actuation chain. A real-time task pipeline is constructed by connecting a series of periodic tasks with data buffers. In a time-critical system, end-to-end timing and data-transfer properties of a task pipeline must be guaranteed. A guarantee could be mathematically expressed by assigning constraints to the tasks of a pipeline. However, deriving task scheduling parameters under the constraints is a constraint optimization problem that is NP-hard. Hence, a traditional constraint solver is not a suitable runtime solution.

In this paper, we present a heuristic constraint solver algorithm, CoPi, to derive the execution times and periods of pipelined tasks that meet the end-to-end constraints and schedulability requirements. We consider two upper bound constraints on a task pipeline: end-to-end delay and loss-rate. After satisfying these constraints, CoPi schedules a pipeline as a set of asynchronous and data independent periodic tasks, under the rate-monotonic scheduling algorithm. Simulations show that CoPi has a comparable pipeline acceptance ratio and significantly better runtime than open-source MINLP-solvers. Furthermore, we use CoPi to map multiple task pipelines to a multiprocessor system. We demonstrate that a partitioned multiprocessor scheduling algorithm coupled with CoPi accommodates dynamically appearing pipelines, while attempting to minimize task migrations.
Uncertain multi-agent MILPs: A data-driven decentralized solution with probabilistic feasibility guarantees
Authors: Alessandro Falsone, Federico Molinari, Maria Prandini
Date: 2020-06-08 00:00:00
Proceeding: L4DC 2020 6
Tasks: Learning Theory

We consider uncertain multi-agent optimization problems that are formulated as Mixed Integer Linear Programs (MILPs) with an almost separable structure. Specifically, agents have their own cost function and constraints, and need to set their local decision vector subject to coupling constraints due to shared resources. The problem is affected by uncertainty that is only known from data. We introduce a data-driven decentralized scheme for handling the combinatorial complexity of the resulting MILP, while providing a probabilistic feasibility certificate that depends on the size of the data-set. The proposed approach rests on a decentralized multi-agent MILP resolution algorithm recently introduced in the literature, which is extended here to an uncertain framework by using tools from statistical learning theory.
Safe non-smooth black-box optimization with application to policy search
Authors: Ilnura Usmanova, Andreas Krause, Maryam Kamgarpour
Date: 2020-06-08 00:00:00
Proceeding: L4DC 2020 6

For safety-critical black-box optimization tasks, observations of the constraints and the objective are often noisy and available only for the feasible points. We propose an approach based on log barriers to find a local solution of a non-convex non-smooth black-box optimization problem $\min f^0(x)$ subject to  $f^i(x)\leq 0, i = 1,\ldots, m$, at the same time, guaranteeing constraint satisfaction while learning with high probability. Our proposed algorithm exploits noisy observations to iteratively improve on an initial safe point until convergence.  We derive the convergence rate and prove safety of our algorithm. We demonstrate its performance in an application to an iterative control design problem.
Efficient Large-Scale Gaussian Process Bandits by Believing only Informative Actions
Authors: Amrit Singh Bedi, Dheeraj Peddireddy, Vaneet Aggarwal, Alec Koppel
Date: 2020-06-08 00:00:00
Proceeding: L4DC 2020 6
Tasks: Bayesian Optimization

In this work, we cast Bayesian optimization as a multi-armed bandit problem, where the payoff function is sampled from a Gaussian process (GP). Further, we focus on action selections via the GP upper confidence bound (UCB). While numerous prior works use GPs in bandit settings, they do not apply to settings where the total number of iterations T may be large-scale, as the complexity of computing the posterior parameters scales cubically with the number of past observations. To circumvent this computational burden, we propose a simple statistical test: only incorporate an action into the GP posterior when its conditional entropy exceeds an  threshold. Doing so permits us to derive sublinear regret bounds of GP bandit algorithms up to factors depending on the compression parameter  for both discrete and continuous action sets. Moreover, the complexity of the GP posterior remains provably finite. Experimentally, we observe state of the art accuracy and complexity tradeoffs for GP bandit algorithms on various hyper-parameter tuning tasks, suggesting
the merits of managing the complexity of GPs in bandit settings
A Duality Approach for Regret Minimization in Average-Award Ergodic Markov Decision Processes
Authors: Hao Gong, Mengdi Wang
Date: 2020-06-08 00:00:00
Proceeding: L4DC 2020 6

In light of the Bellman duality, we propose a novel value-policy gradient algorithm to explore and act in infinite-horizon Average-reward Markov Decision Process (AMDP) and show that it has sublinear regret. The algorithm is motivated by the Bellman saddle point formulation. It learns the optimal state-action distribution, which encodes a randomized policy, by interacting with the environment along a single trajectory and making primal-dual updates. The key to the analysis is to establish a connection between the min-max duality gap of Bellman saddle point and the cumulative regret of the learning agent. 
 We show that, for ergodic AMDPs with finite state space $\mathcal{S}$ and action space $\mathcal{A}$ and uniformly bounded mixing times, the algorithm's $T$-time step regret is 
 $$
  R(T)=\tilde{\mathcal{O}}\left( \left(t_{mix}^*\right)^2 \tau^{\frac{3}{2}} \sqrt{(\tau^3 + |\mathcal{A}|) |\mathcal{S}| T} \right),
 $$
where $t_{mix}^*$ is the worst-case mixing time, $\tau$ is an ergodicity parameter, $T$ is the number of time steps and $\tilde{\mathcal{O}}$ hides polylog factors.
Data-Driven Distributed Predictive Control via Network Optimization
Authors: Ahmed Allibhoy, Jorge Cortes
Date: 2020-06-08 00:00:00
Proceeding: L4DC 2020 6

We consider a networked linear system where system matrices are unknown to the individual agents but sampled data is available to them.  We propose a data-driven method for designing a distributed linear-quadratic controller where agents learn a non-parametric system model from a single sample trajectory in which nodes can predict future trajectories using only data available to themselves and their neighbors. Based on this system representation, we propose a control scheme where a network optimization problem is solved in a receding horizon manner. We show that the proposed control scheme is stabilizing and validate our results through numerical experiments.
L1-GP: L1 Adaptive Control with Bayesian Learning
Authors: Aditya Gahlawat, Pan Zhao, Andrew Patterson, Naira Hovakimyan, Evangelos Theodorou
Date: 2020-06-08 00:00:00
Proceeding: L4DC 2020 6
Tasks: GPR, regression

We present L1-GP, an architecture based on L1 adaptive control and Gaussian Process Regression (GPR) for safe simultaneous control and learning. On one hand, the L1 adaptive control provides stability and transient performance guarantees, which allows for GPR to efficiently and safely learn the uncertain dynamics. On the other hand, the learned dynamics can be conveniently incorporated into the L1 control architecture without sacrificing robustness and tracking performance. Subsequently, the learned dynamics can lead to less conservative designs for performance/robustness tradeoff. We illustrate the efficacy of the proposed architecture via numerical simulations.
Learning to Plan via Deep Optimistic Value Exploration
Authors: Tim Seyde, Wilko Schwarting, Sertac Karaman, Daniela Rus
Date: 2020-06-08 00:00:00
Proceeding: L4DC 2020 6
Tasks: Benchmarking, Model-based Reinforcement Learning, Reinforcement Learning (RL)

Deep exploration requires coordinated long-term planning. We present a model-based reinforcement learning algorithm that guides policy learning through a value function that exhibits optimism in the face of uncertainty. We capture uncertainty over values by combining predictions from an ensemble of models and formulate an upper confidence bound (UCB) objective to recover optimistic estimates. Training the policy on ensemble rollouts with the learned value function as the terminal cost allows for projecting long-term interactions into a limited planning horizon, thus enabling deep optimistic exploration. We do not assume a priori knowledge of either the dynamics or reward function. We demonstrate that our approach can accommodate both dense and sparse reward signals, while improving sample complexity on a variety of benchmarking tasks.