Monitoring and debugging modern cloud-based applications is challenging since even a single API call can involve many interdependent distributed microservices. To provide observability for such complex systems, distributed tracing frameworks track request flow across the microservice call tree. However, such solutions require instrumenting every component of the distributed application to add and propagate tracing headers, which has slowed adoption. This paper explores whether we can trace requests without any application instrumentation, which we refer to as request trace reconstruction. To that end, we develop TraceWeaver, a system that incorporates readily available information from production settings (e.g., timestamps) and test environments (e.g., call graphs) to reconstruct request traces with usefully high accuracy. At the heart of TraceWeaver is a reconstruction algorithm that uses request-response timestamps to effectively prune the search space for mapping requests and applies statistical timing analysis techniques to reconstruct traces. Evaluation with (1) benchmark microservice applications and (2) a production microservice dataset demonstrates that TraceWeaver can achieve a high accuracy of ~90% and can be meaningfully applied towards multiple use cases (e.g., finding slow services and A/B testing).

We show that the Adaptive Greedy algorithm of Golovin and Krause achieves an approximation bound of (ln(Q/η)+1) for Stochastic Submodular Cover: here Q is the “goal value” and η is the minimum gap between Q and any attainable utility value Q'

Constrained maximization of non-decreasing utility functions with submodularity-like properties is at the core of several AI and ML applications including viral marketing, pool-based active learning, adaptive feature selection, and sensor deployment. In this work, we develop adaptive policies for maximizing such functions when both the utility function and item costs may be stochastic. First, we study maximization of an adaptive weak submodular function which is submodular in an approximate and probabilistic sense, subject to a stochastic fractional knapsack constraint, which requires total expected item cost to be within a given capacity. We present the $\beta$-GREEDY policy for this problem; our approximation guarantee for it recovers many known greedy maximization guarantees as special cases. Next, we study maximization of an adaptive submodular function, which is submodular in a probabilistic sense, subject to a stochastic knapsack constraint, which requires the total item cost to be within a given capacity with probability one. We present the MIX policy for this problem; our approximation guarantee for it is the first known approximation guarantee for maximizing a non-linear utility function subject to a stochastic knapsack constraint. Using alternative parameterizations of MIX, we also derive the first known approximation guarantees for maximizing an adaptive submodular function subject to a deterministic knapsack constraint. Our guarantees are powered by an innovative differential analysis technique which models the $\beta$-GREEDY policy using a continuous-time stochastic reward process of a particle whose reward is related to the optimal utility through a differential inequality. The solution to this inequality yields our $\beta$-GREEDY guarantee. We combine differential analysis with a variety of other ideas to derive our MIX guarantees.

We consider the stochastic multi-armed bandit problem and the contextual bandit problem with historical observations and pre-clustered arms. The historical observations can contain any number of instances for each arm, and the pre-clustering information is a fixed clustering of arms provided as part of the input. We develop a variety of algorithms which incorporate this offline information effectively during the online exploration phase and derive their regret bounds. In particular, we develop the META algorithm which effectively hedges between two other algorithms: one which uses both historical observations and clustering, and another which uses only the historical observations. The former outperforms the latter when the clustering quality is good, and vice-versa. Extensive experiments on synthetic and real world datasets on Warafin drug dosage and web server selectionfor latency minimization validate our theoretical insights and demonstrate that META is a robust strategy for optimally exploiting the pre-clustering information.

Outlier detection is the identification of points in a dataset that do not conform to the norm. Outlier detection is highly sensitive to the choice of the detection algorithm and the feature subspace used by the algorithm. Extracting domain-relevant insights from outliers needs systematic exploration of these choices since diverse outlier sets could lead to complementary insights. This challenge is especially acute in an interactive setting, where the choices must be explored in a time-constrained manner. In this work, we present REMIX, the first system to address the problem of outlier detection in an interactive setting. REMIX uses a novel mixed integer programming (MIP) formulation for automatically selecting and executing a diverse set of outlier detectors within a time limit. This formulation incorporates multiple aspects such as (i) an upper limit on the total execution time of detectors (ii) diversity in the space of algorithms and features, and (iii) meta-learning for evaluating the cost and utility of detectors. REMIX provides two distinct ways for the analyst to consume its results: (i) a partitioning of the detectors explored by REMIX into perspectives through low-rank non-negative matrix factorization; each perspective can be easily visualized as an intuitive heatmap of experiments versus outliers, and (ii) an ensembled set of outliers which combines outlier scores from all detectors. We demonstrate the benefits of REMIX through extensive empirical validation on real-world data.

Current tools for exploratory data analysis (EDA) require users to manually select data attributes, statistical computations and visual encodings. This can be daunting for large-scale, complex data. We introduce Foresight, a system that helps the user rapidly discover visual insights from large high-dimensional datasets. Formally, an "insight" is a strong manifestation of a statistical property of the data, e.g., high correlation between two attributes, high skewness or concentration about the mean of a single attribute, a strong clustering of values, and so on. For each insight type, Foresight initially presents visualizations of the top k instances in the data, based on an appropriate ranking metric. The user can then look at "nearby" insights by issuing "insight queries" containing constraints on insight strengths and data attributes. Thus the user can directly explore the space of insights, rather than the space of data dimensions and visual encodings as in other visual recommender systems. Foresight also provides "global" views of insight space to help orient the user and ensure a thorough exploration process. Furthermore, Foresight facilitates interactive exploration of large datasets through fast, approximate sketching.

Graphs or networks provide a powerful abstraction to view and analyze relationships among different entities present in a dataset. However, much of the data of interest to analysts and data scientists resides in non-graph forms such as relational databases, JSON, XML, CSV and text. The effort and skill required in identifying and extracting the relevant graph representation from data is often the prohibitive and limits a wider adoption of graph-based analysis of non-graph data. In this paper, we demonstrate our system calledGraphViewer, for accelerated graph-based exploration and analysis. It automatically discovers relevant graphs implicit within a given non-graph dataset using a set of novel rule-based and data-driven techniques, and optimizes their extraction and storage. It computes several node and graph level metrics and detects anomalous entities in data. Finally, it summarizes the results to support interpretation by a human analyst. While the system automates the computationally intensive aspects of the process, it is engineered to leverage human domain expertise and instincts to fine tune the data exploration process.

Exploratory data analysis (EDA) is the process of discovering im-portant characteristics of a dataset or finding data-driven insights in the corresponding domain. EDA is a human intensive process involving data management, analytic flow deployment and model creation, and data visualization and interpretation. It involves ex-tensive use of analyst time, effort, and skill in data processing as well as domain expertise. In this paper, we introduce READ, a mixed initiative system for accelerating exploratory data analysis. The key idea behind READ is to decompose the exploration pro-cess into components that can be independently specified and auto-mated. These components can be defined, reused or extended using simple choice points that are expressed using inference rules, plan-ning logic, and reactive user interfaces and visualization. READ uses a formal specification of the analytic process for automated model space enumeration, workflow composition, deployment, and model validation and clustering. READ aims to reduce the time re-quired for exploration and understanding of a dataset from days to minutes. 1.

We investigate the DHCP churn impact on network characterization by analyzing 18 months of DHCP, DNS, Firewall Alert, and Netflow data collected from an enterprise network of 30,000 clients. We find that DHCP churn has clear impact on network metrics.

We study the problem of throughput maximization in multihop wireless networks with end-to-end delay constraints for each session. This problem has received much attention starting with the work of Grossglauser and Tse (2002), and it has been shown that there is a significant tradeoff between the end-to-end delays and the total achievable rate. We develop algorithms to compute such tradeoffs with provable performance guarantees for arbitrary instances, with general interference models. Given a target delay-bound Δ(c) for each session c, our algorithm gives a stable flow vector with a total throughput within a factor of O(log Δm/loglog Δm) of the maximum, so that the per-session (end-to-end) delay is O(((log Δm/loglog Δm)Δ(c))2), where Δm=maxc{Δ(c)}; note that these bounds depend only on the delays, and not on the network size, and this is the first such result, to our knowledge.

In this paper, we propose to conduct anomaly detection across multiple sources to identify objects that have inconsistent behavior across these sources. We assume that a set of objects can be described from various perspectives (multiple information sources). The underlying clustering structure of normal objects is usually shared by multiple sources. However, anomalous objects belong to different clusters when considering different aspects. For example, there exist movies that are expected to be liked by kids by genre, but are liked by grown-ups based on user viewing history. To identify such objects, we propose to compute the distance between different eigen decomposition results of the same object with respect to different sources as its anomalous score. We also give interpretations from the perspectives of constrained spectral clustering and random walks over graph. Experimental results on several UCI as well as DBLP and Movie Lens datasets demonstrate the effectiveness of the proposed approach.

We study the problem of throughput maximization in multi-hop wireless networks with end-to-end delay constraints for each session. This problem has received much attention starting with the work of Grossglauser and Tse (2002), and it has been shown that there is a significant tradeoff between the end-to-end delays and the total achievable rate. We develop algorithms to compute such tradeoffs with provable performance guarantees for arbitrary instances, with general interference models. Given a target delay-bound Δ(c) for each session c, our algorithm gives a stable flow vector with a total throughput within a factor of O (equation) of the maximum, so that the per-session (end-to-end) delay is O (equation), where Δm= maxc{Δ(c)}; note that these bounds depend only on the delays, and not on the network size, and this is the first such result, to our knowledge.

Equipping wireless nodes with multiple radios can significantly increase the capacity of wireless networks, by making these radios simultaneously transmit over multiple non-overlapping channels. However, due to the limited number of radios and available orthogonal channels, designing efficient channel assignment and scheduling algorithms in such networks is a major challenge. In this paper, we present provably-good distributed algorithms for simultaneous channel allocation of individual links and packet-scheduling, in software-defined radio (SDR) wireless networks. Our distributed algorithms are very simple to implement, and do not require any coordination even among neighboring nodes. A novel access hash function or random oracle methodology is one of the key drivers of our results. With this access hash function, each radio can know the transmitters' decisions for links in its interference set for each time slot without introducing any extra communication overhead between them. Further, by utilizing the inductive-scheduling technique, each radio can also backoff appropriately to avoid collisions. Extensive simulations demonstrate that our bounds are valid in practice.

We develop a single rounding algorithm for scheduling on unrelated parallel machines; this algorithm works well with the known linear programming-, quadratic programming-, and convex programming-relaxations for scheduling to minimize completion time, makespan, and other well-studied objective functions. This algorithm leads to the following applications for the general setting of unrelated parallel machines: (i) a bicriteria algorithm for a schedule whose weighted completion-time and makespan simultaneously exhibit the current-best individual approximations for these criteria; (ii) better-than-two approximation guarantees for scheduling to minimize the L p norm of the vector of machine-loads, for all 1 < p < ∞; and (iii) the first constant-factor multicriteria approximation algorithms that can handle the weighted completion-time and any given collection of integer L p norms. Our algorithm has a natural interpretation as a melding of linear-algebraic and probabilistic approaches. Via this view, it yields a common generalization of rounding theorems due to Karp et al. [1987] and Shmoys & Tardos [1993], and leads to improved approximation algorithms for the problem of scheduling with resource-dependent processing times introduced by Grigoriev et al. [2007].

We study the problem of total throughput maximization in arbitrary multi-hop wireless networks, with constraints on the total power usage (denoted by PETM), when nodes have the capability to adaptively choose their power levels, which is the case with software defined radio devices. The underlying interference graph changes when power levels change, making PETM a complex cross-layer optimization problem. We develop a linear programming formulation for this problem, that leads to a constant factor approximation to the total throughput rate, for any given bound on the total power usage. Our result is a rigorously provable worst case approximation guarantee, which holds for any instance. Our formulation is generic and can accommodate different interference models and objective functions. We complement our theoretical analysis with simulations and compute the explicit tradeoffs between fairness, total throughput and power usage.

A fundamental problem in wireless networks is to estimate its throughput capacity - given a set of wireless nodes, and a set of connections, what is the maximum rate at which data can be sent on these connections. Most of the research in this direction has focused on either random distributions of points, or has assumed simple graph-based models for wireless interference. In this paper, we study capacity estimation problem using the more general Signal to Interference Plus Noise Ratio (SINR) model for interference, on arbitrary wireless networks. The problem becomes much harder in this setting, because of the non-locality of the SINR model. Recent work by Moscibroda et al. (2006) has shown that the throughput in this model can differ from graph based models significantly. We develop polynomial time algorithms to provably approximate the total throughput in this setting.

We study the throughput capacity of wireless networks which employ (asynchronous) random-access scheduling as opposed to deterministic scheduling. The central question we answer is: how should we set the channel-access probability for each link in the network so that the network operates close to its optimal throughput capacity? We design simple and distributed channel-access strategies for random-access networks which are provably competitive with respect to the optimal scheduling strategy, which is deterministic, centralized, and computationally infeasible. We show that the competitiveness of our strategies are nearly the best achievable via random-access scheduling, thus establishing fundamental limits on the performance of random- access. A notable outcome of our work is that random access compares well with deterministic scheduling when link transmission durations differ by small factors, and much worse otherwise. The distinguishing aspects of our work include modeling and rigorous analysis of asynchronous communication, asymmetry in link transmission durations, and hidden terminals under arbitrary link-conflict based wireless interference models.

As mobile nodes roam in a wireless network, they continuously associate with different access points and perform handoff operations. However, frequent handoffs can potentially incur unacceptable delays and even interruptions for interactive applications. To alleviate these negative impacts, we present novel association control algorithms that can minimize the frequency of handoffs occurred to mobile devices. Specifically, we show that a greedy LookAhead algorithm is optimal in the offline setting, where the user's future mobility is known. Inspired by such optimality, we further propose two online algorithms, namely LookBack and Track, that operate without any future mobility information. Instead, they seek to predict the lifetime of an association using randomization and statistical approaches, respectively. We evaluate the performance of these algorithms using both analysis and trace-driven simulations. The results show that the simple LookBack algorithm has surprisingly a competitive ratio .of (log k + 2), where k is the maximum number of APs that a user can hear at any time, and the Track algorithm can achieve near-optimal performance in practical scenarios.

We consider a fundamental flow maximization problem that arises during the evaluation of multiple overlapping queries defined on a data stream, in a heterogenous parallel environment. Each query is a conjunction of boolean filters, and each filter could be shared across multiple queries. We are required to design an evaluation plan that evaluates filters against stream items in order to determine the set of queries satisfied by each item. The evaluation plan specifies for each item: (i) the subset of filters evaluated for this item and the order of their evaluations, and (ii) the processor on which each filter evaluation occurs. Our goal is to design an evaluation plan which maximizes the total throughput (flow) of the stream handled by the plan, without violating the processor capacities.

We consider the problem of evaluating multiple overlapping queries defined on data streams, where each query is a conjunction of multiple filters and each filter may be shared across multiple queries. Efficient support for overlapping queries is a critical issue in the emerging data stream systems, and this is particularly the case when filters are expensive in terms of their computational complexity and processing time. This problem generalizes other well-known problems such as pipelined filter ordering and set cover, and is not only NP-Hard but also hard to approximate within a factor of o(log n) from the optimum, where n is the number of queries. In this paper, we present two near-optimal approximation lgorithms with provably-good performance guarantees for the evaluation of overlapping queries. We present an edge-coverage based Greedy algorithm which achieves an approximation ratio of (1 + log(n) + log(α)), where n is the number of queries and α is the average number of filters in a query. We also present a randomized, fast and easily parallelizable Harmonic algorithm which achieves an approximation ratio of 2β, where β is the maximum number of filters in a query. We have implemented these algorithms in a prototype system, and evaluated their performance using extensive experiments in the context of multimedia stream analysis. The results show that our Greedy algorithm consistently outperforms other known algorithms under various settings and scales well as the numbers of queries and filters increase.

Recently, there has been substantial interest in the design of cross-layer protocols for wireless networks. These protocols optimize certain performance metric(s) of interest (e.g. latency, energy, rate) by jointly optimizing the performance of multiple layers of the protocol stack. Algorithm designers often use geometric-graph-theoretic models for radio interference to design such cross-layer protocols. In this paper we study the problem of designing cross-layer protocols for multi-hop wireless networks using a more realistic Signal to Interference plus Noise Ratio (SINR) model for radio interference. The following cross-layer latency minimization problem is studied: Given a set V of transceivers, and a set of source-destination pairs, (i) choose power levels for all the transceivers, (ii) choose routes for all connections, and (iii) construct an end-to-end schedule such that the SINR constraints are satisfied at each time step so as to minimize the make-span of the schedule (the time by which all packets have reached their respective destinations). We present a polynomial-time algorithm with provable worst-case performance guarantee for this cross-layer latency minimization problem. As corollaries of the algorithmic technique we show that a number of variants of the cross-layer latency minimization problem can also be approximated efficiently in polynomial time. Our work extends the results of Kumar et al. (Proc. SODA, 2004) and Moscibroda et al. (Proc. MOBIHOC, 2006). Although our algorithm considers multiple layers of the protocol stack, it can naturally be viewed as compositions of tasks specific to each layer --- this allows us to improve the overall performance while preserving the modularity of the layered structure.

We develop a new randomized rounding approach for fractional vectors defined on the edge-sets of bipartite graphs. We show various ways of combining this technique with other ideas, leading to improved (approximation) algorithms for various problems. These include:---low congestion multi-path routing;---richer random-graph models for graphs with a given degree-sequence;---improved approximation algorithms for: (i) throughput-maximization in broadcast scheduling, (ii) delay-minimization in broadcast scheduling, as well as (iii) capacitated vertex cover; and---fair scheduling of jobs on unrelated parallel machines.

We develop a single rounding algorithm for scheduling on unrelated parallel machines; this algorithm works well with the known linear programming, quadratic programming, and convex programming-relaxations for scheduling to minimize completion time, makespan, and other well-studied objective functions. We obtain the following applications for the general setting of unrelated parallel machines: (i) a bicriteria algorithm for a schedule whose weighted completion-time and makespan simultaneously exhibit the current-best individual approximations for these criteria (3/2 and 2, respectively); (ii) better-than-two approximation guarantees for scheduling under the L/sub p/ norm for all 1 < p < /spl infin/, improving on the 2-approximation algorithms of Azar & Epstein; and (iii) the first constant-factor multicriteria approximation algorithms that handle the weighted completion-time and any given collection of integer L/sub p/ norms. Our algorithm yields a common generalization of rounding theorems due to Karp et al and Shmoys & Tardos; among other applications, this yields an improved approximation for scheduling with resource-dependent processing times studied by Grigoriev et al.

We consider the problem of handling similarity queries in peer-to-peer databases. We propose an indexing and searching mechanism which, given a query object, returns the set of objects in the database that are semantically related to the query. We propose an indexing scheme which clusters data such that semantically related objects are partitioned into a small set of clusters, allowing for a simple and efficient similarity search strategy. Our indexing scheme also decouples object and node locations. Our adaptive replication and randomized lookup schemes exploit this feature and ensure that the number of copies of an object is proportional to its popularity and all replicas are equally likely to serve a given query, thus achieving perfect load balancing. The techniques developed in this work are oblivious to the underlying DHT topology and can be implemented on a variety of structured overlays such as CAN, CHORD, Pastry, and Tapestry. We also present DHT-independent analytical guarantees for the performance of our algorithms in terms of search accuracy, cost, and load-balance; the experimental results from our simulations confirm the insights derived from these analytical models

This paper considers two inter-related questions: (i) Given a wireless ad-hoc network and a collection of source-destination pairs {(si,ti)}, what is the maximum throughput capacity of the network, i.e. the rate at which data from the sources to their corresponding destinations can be transferred in the network? (ii) Can network protocols be designed that jointly route the packets and schedule transmissions at rates close to the maximum throughput capacity? Much of the earlier work focused on random instances and proved analytical lower and upper bounds on the maximum throughput capacity. Here, in contrast, we consider arbitrary wireless networks. Further, we study the algorithmic aspects of the above questions: the goal is to design provably good algorithms for arbitrary instances. We develop analytical performance evaluation models and distributed algorithms for routing and scheduling which incorporate fairness, energy and dilation (path-length) requirements and provide a unified framework for utilizing the network close to its maximum throughput capacity.Motivated by certain popular wireless protocols used in practice, we also explore "shortest-path like" path selection strategies which maximize the network throughput. The theoretical results naturally suggest an interesting class of congestion aware link metrics which can be directly plugged into several existing routing protocols such as AODV, DSR, etc. We complement the theoretical analysis with extensive simulations. The results indicate that routes obtained using our congestion aware link metrics consistently yield higher throughput than hop-count based shortest path metrics.

Network wide broadcasting is a fundamental operation in ad hoc networks. In broadcasting, a source node end a message to all the other nodes in the network. In this paper, we consider the problem of collision-free broadcasting in ad hoc wireless networks. Our objective is to minimize the latency and the number of retransmission in the broadcast. We show that minimum latency broadcasting i NP-hard for ad hoc wireless networks. We also present a simple and distributed collision-free broadcasting algorithm for broadcasting a message. For networks with bounded node transmission ranges, our algorithm simultaneously guarantees that the latency and the number of retransmission are within O(1)times their respective optimal values. Our algorithm and analysis extends to the case when multiple messages are broadcast from multiple sources. Experimental studies indicate that our algorithm perform much better in practice than the analytical guarantee provided for the worst case.

We combine the pipage rounding technique of Ageev & Sviridenko with a recent rounding method developed by Srinivasan (2001), to develop a new randomized rounding approach for fractional vectors defined on the edge-sets of bipartite graphs. We show various ways of combining this technique with other ideas, leading to the following applications: richer random-graph models for graphs with a given degree-sequence; improved approximation algorithms for: (i) throughput-maximization in broadcast scheduling, (ii) delay-minimization in broadcast scheduling, and (iii) capacitated vertex cover; fair scheduling of jobs on unrelated parallel machines. A useful feature of our method is that it lets us prove certain (probabilistic) per-user fairness properties.