Consider public health officials aiming to spread awareness about a new vaccine in a community interconnected by a social network. How can they distribute information with minimal resources, so as to avoid polarization and ensure community-wide convergence of opinion? To tackle such challenges, we initiate the study of sample complexity of opinion formation in networks. Our framework is built on the recognized opinion formation game, where we regard each agent’s opinion as a data-derived model, unlike previous works that treat opinions as data-independent scalars. The opinion model for every agent is initially learned from its local samples and evolves game-theoretically as all agents communicate with neighbors and revise their models towards an equilibrium. Our focus is on the sample complexity needed to ensure that the opinions converge to an equilibrium such that every agent’s final model has low generalization error. Our paper has two main technical results. First, we present a novel polynomial time optimization framework to quantify the total sample complexity for arbitrary networks, when the underlying learning problem is (generalized) linear regression. Second, we leverage this optimization to study the network gain which measures the improvement of sample complexity when learning over a network compared to that in isolation. Towards this end, we derive network gain bounds for various network classes including cliques, star graphs, and random regular graphs. Additionally, our framework provides a method to study sample distribution within the network, suggesting that it is sufficient to allocate samples inversely to the degree. Empirical results on both synthetic and real-world networks strongly support our theoretical findings.

Previous work in fair machine learning has characterised the Fair Bayes Optimal Classifier (BOC) on a given distribution for both deterministic and randomized classifiers. We study the robustness of the Fair BOC to adversarial noise in the data distribution. Kearns & Li (1988) implies that the accuracy of the deterministic BOC without any fairness constraints is robust (Lipschitz) to malicious noise in the data distribution. We demonstrate that their robustness guarantee breaks down when we add fairness constraints. Hence, we consider the randomized Fair BOC, and our central result is that its accuracy is robust to malicious noise in the data distribution. Our robustness result applies to various fairness constraints---Demographic Parity, Equal Opportunity, Predictive Equality. Beyond robustness, we demonstrate that randomization leads to better accuracy and efficiency. We show that the randomized Fair BOC is nearly-deterministic, and gives randomized predictions on at most one data point, hence availing numerous benefits of randomness, while using very little of it.

Abstract It is natural to generalize the online $$k$$ k -Server problem by allowing each request to specify not only a point p, but also a subset S of servers that may serve it. To date, only a few special cases of this problem have been studied. The objective of the work presented in this paper has been to more systematically explore this generalization in the case of uniform and star metrics. For uniform metrics, the problem is equivalent to a generalization of Paging in which each request specifies not only a page p, but also a subset S of cache slots, and is satisfied by having a copy of p in some slot in S. We call this problem Slot-Heterogenous Paging. In realistic settings only certain subsets of cache slots or servers would appear in requests. Therefore we parameterize the problem by specifying a family $${\mathcal {S}}\subseteq 2^{[k]}$$ S ⊆ 2 [ k ] of requestable slot sets, and we establish bounds on the competitive ratio as a function of the cache size k and family $${\mathcal {S}}$$ S : If all request sets are allowed ( $${\mathcal {S}}=2^{[k]}\setminus \{\emptyset \}$$ S = 2 [ k ] \ { ∅ } ), the optimal deterministic and randomized competitive ratios are exponentially worse than for standard Paging ( $${\mathcal {S}}=\{[k]\}$$ S = { [ k ] } ). As a function of $$|{\mathcal {S}}|$$ | S | and k, the optimal deterministic ratio is polynomial: at most $$O(k^2|{\mathcal {S}}|)$$ O ( k 2 | S | ) and at least $$\Omega (\sqrt{|{\mathcal {S}}|})$$ Ω ( | S | ) . For any laminar family $${\mathcal {S}}$$ S of height h, the optimal ratios are O(hk) (deterministic) and $$O(h^2\log k)$$ O ( h 2 log k ) (randomized). The special case of laminar $${\mathcal {S}}$$ S that we call All-or-One Paging extends standard Paging by allowing each request to specify a specific slot to put the requested page in. The optimal deterministic ratio for weighted All-or-One Paging is $$\Theta (k)$$ Θ ( k ) . Offline All-or-One Paging is

It is natural to generalize the online $k$-Server problem by allowing each request to specify not only a point $p$, but also a subset $S$ of servers that may serve it. For uniform metrics, the problem is equivalent to a generalization of Paging in which each request specifies not only a page $p$, but also a subset $S$ of cache slots, and is satisfied by having a copy of $p$ in some slot in $S$. We call this problem Slot-Heterogenous Paging. We parameterize the problem by specifying a family $\mathcal S \subseteq 2^{[k]}$ of requestable slot sets, and we establish bounds on the competitive ratio as a function of the cache size $k$ and family $\mathcal S$: - If all request sets are allowed ($\mathcal S=2^{[k]}\setminus\{\emptyset\}$), the optimal deterministic and randomized competitive ratios are exponentially worse than for standard \Paging ($\mathcal S=\{[k]\}$). - As a function of $|\mathcal S|$ and $k$, the optimal deterministic ratio is polynomial: at most $O(k^2|\mathcal S|)$ and at least $Ω(\sqrt{|\mathcal S|})$. - For any laminar family $\mathcal S$ of height $h$, the optimal ratios are $O(hk)$ (deterministic) and $O(h^2\log k)$ (randomized). - The special case of laminar $\mathcal S$ that we call All-or-One Paging extends standard Paging by allowing each request to specify a specific slot to put the requested page in. The optimal deterministic ratio for weighted All-or-One Paging is $Θ(k)$. Offline All-or-One Paging is NP-hard. Some results for the laminar case are shown via a reduction to the generalization of Paging in which each request specifies a set $\mathcal P of pages, and is satisfied by fetching any page from $\mathcal P into the cache. The optimal ratios for the latter problem (with laminar family of height $h$) are at most $hk$ (deterministic) and $h\,H_k$ (randomized).

The study of strategic or adversarial manipulation of testing data to fool a classifier has attracted much recent attention. Most previous works have focused on two extreme situations where any testing data point either is completely adversarial or always equally prefers the positive label. In this paper, we generalize both of these through a unified framework by considering strategic agents with heterogenous preferences, and introduce the notion of strategic VC-dimension (SVC) to capture the PAC-learnability in our general strategic setup. SVC provably generalizes the recent concept of adversarial VC-dimension (AVC) introduced by Cullina et al. (2018). We instantiate our framework for the fundamental strategic linear classification problem. We fully characterize: (1) the statistical learnability of linear classifiers by pinning down its SVC; (2) its computational tractability by pinning down the complexity of the empirical risk minimization problem. Interestingly, the SVC of linear classifiers is always upper bounded by its standard VC-dimension. This characterization also strictly generalizes the AVC bound for linear classifiers in (Cullina et al., 2018). Finally, we briefly investigate the power of randomization in our strategic classification setup. We show that randomization may strictly increase the accuracy in general, but will not help in the special case of adversarial classification with zero-manipulation-cost.

The study of strategic or adversarial manipulation of testing data to fool a classifier has attracted much recent attention. Most previous works have focused on two extreme situations where any testing data point either is completely adversarial or always equally prefers the positive label. In this paper, we generalize both of these through a unified framework for strategic classification and introduce the notion of strategic VC-dimension (SVC) to capture the PAC-learnability in our general strategic setup. SVC provably generalizes the recent concept of adversarial VC-dimension (AVC) introduced by Cullina et al. (2018). We instantiate our framework for the fundamental strategic linear classification problem. We fully characterize: (1) the statistical learnability of linear classifiers by pinning down its SVC; (2) it’s computational tractability by pinning down the complexity of the empirical risk minimization problem. Interestingly, the SVC of linear classifiers is always upper bounded by its standard VC-dimension. This characterization also strictly generalizes the AVC bound for linear classifiers in (Cullina et al., 2018).

We initiate the algorithmic study of retracting a graph into a cycle in the graph, which seeks a mapping of the graph vertices to the cycle vertices, so as to minimize the maximum stretch of any edge, subject to the constraint that the restriction of the mapping to the cycle is the identity map. This problem has its roots in the rich theory of retraction of topological spaces, and has strong ties to well-studied metric embedding problems such as minimum bandwidth and 0-extension. Our first result is an O(min{k, sqrt{n}})-approximation for retracting any graph on n nodes to a cycle with k nodes. We also show a surprising connection to Sperner's Lemma that rules out the possibility of improving this result using natural convex relaxations of the problem. Nevertheless, if the problem is restricted to planar graphs, we show that we can overcome these integrality gaps using an exact combinatorial algorithm, which is the technical centerpiece of the paper. Building on our planar graph algorithm, we also obtain a constant-factor approximation algorithm for retraction of points in the Euclidean plane to a uniform cycle.

We address the problem of serving Deep Neural Networks (DNNs) efficiently from a cluster of GPUs. In order to realize the promise of very low-cost processing made by accelerators such as GPUs, it is essential to run them at sustained high utilization. Doing so requires cluster-scale resource management that performs detailed scheduling of GPUs, reasoning about groups of DNN invocations that need to be co-scheduled, and moving from the conventional whole-DNN execution model to executing fragments of DNNs. Nexus is a fully implemented system that includes these innovations. In large-scale case studies on 16 GPUs, when required to stay within latency constraints at least 99% of the time, Nexus can process requests at rates 1.8-12.7X higher than state of the art systems can. A long-running multi-application deployment stays within 84% of optimal utilization and, on a 100-GPU cluster, violates latency SLOs on 0.27% of requests.

We propose a new model for the study of resilience of coevolving multiplex scale-free networks. Our network model, called preferential interdependent networks, is a novel continuum over scale-free networks parameterized by their correlation p, 0 ≤ p ≤1. Our failure and recovery model ties the propensity of a node, both to fail and to assist in recovery, to its importance. We show, analytically, that our network model can achieve any γ, 2 ≤ γ ≤ 3 for the exponent of the power law of the degree distribution; this is superior to existing multiplex models and allows us better fidelity in representing real-world networks. Our failure and recovery model is also a departure from the much studied cascading error model based on the giant component; it allows for surviving important nodes to send assistance to the damaged nodes to enable their recovery. This better reflects the reality of recovery in man-made networks such as social networks and infrastructure networks. Our main finding, based on simulations, is that resilient preferential interdependent networks are those in which the layers are neither completely correlated (p = 1) nor completely uncorrelated (p= 0) but instead semi-correlated (p ≈ 0.1 - 0.3). This finding is consistent with the real-world experience where complex man-made networks typically bounce back quickly from stress. In an attempt to explain our intriguing empirical discovery we present an argument for why semi-correlated multiplex networks can be the most resilient. Our argument can be seen as an explanation of plausibility or as an incomplete mathematical proof subject to certain technical conjectures that we make explicit.

We introduce a variant of the classical PAC multi-armed bandit problem. There is an ordered set of n arms A[1], ⋯, A[n], each with some stochastic reward drawn from some unknown bounded distribution. The goal is to identify the skyline of the set A, consisting of all arms A[i] such that A[i] has larger expected reward than all lower-numbered arms A[1], ⋯, A[i-1]. We define a natural notion of an ε-approximate skyline and prove matching upper and lower bounds for identifying an ε-skyline. Specifically, we show that in order to identify an ε -skyline from among arms with probability 1-δ, Θ([n/(ε2)]·min{log([1/(εδ)]), log([n/(δ)])}) samples suffice and are necessary in the -worst case. When ε ≫ 1/n, our results improve over the naïve algorithm, which draws enough samples to approximate the expected reward of every arm; the algorithm of (Auer et al., AISTATS'16) for Pareto-optimal arm identification is likewise superseded. Our results show that the sample complexity of the skyline problem lies strictly in between that of best arm identification (Even-Dar et al., COLT'02) and that of approximating the expected reward of every arm. [Full version available on arXiv: arxiv.org/abs/1711.04213].

Motivated by denial-of-service network attacks, we introduce the symmetric interdiction model, where both the interdictor and the optimizer are subject to the same constraints of the underlying optimization problem. We give a general framework that relates optimization to symmetric interdiction for a broad class of optimization problems. We then study the symmetric matching interdiction problem - with applications in traffic engineering - in more detail. This problem can be simply stated as follows: find a matching whose removal minimizes the size of the maximum matching in the remaining graph. We show that this problem is APX-hard, and obtain a 3/2-approximation algorithm that improves on the approximation guarantee provided by the general framework.

k-HA (high-Availability) is an important faulttolerance property of VM placement in clouds and clusters - it is the ability to tolerate up to k host failures by relocating VMs from failed hosts without disrupting other VMs. It has long been assumed [1] that deciding the existence of a k-HA placement is ΣP 3 -hard. In a surprising yet simple result we show that k-HA reduces to multiple knapsack and hence is in NP= ΣP 1 . We propose a stochastic model for multiple knapsack that not only captures real-world workloads but also provides a uniform basis for comparing the efficiencies of different polynomial-time heuristics. We prove, using the central limit theorem and linear programming, that, there exists a best polynomial-time heuristic, albeit impractical from the standpoint of implementation. We turn to industry practice and discuss the drawbacks of commonly used heuristics-First- fit,Best-fit,Worst-fit,MTHM and CSP. Load-balancing is a fundamental customer requirement in industry. Based on a large real-world dataset of cluster workloads (from industry leader Nutanix) we show that the natural load-balancing heuristic - Water- filling - has several excellent properties. We compare and contrast Water-filling with MTHM using our stochastic model and find that Water-filling is a heuristic of choice.

We define and construct a novel pseudorandom tool, the Markovian hitter. Given an input sequence of n independent random bits, a Markovian hitter produces a sequence of pseudorandom samples in {0, 1}k, in an online fashion, that hits any subset W ⊂ {0, 1}k of size ∊2k with probability ≈ 1 – 2–(n–k)∊. This is comparable to the behavior of truly random samples or classical pseudorandom hitting sets. A Markovian hitter has an additional “Markovian” property of interest: each pseudorandom sample is a function of only the O(k) most recent bits of the input sequence (of random bits). Such Markovian properties are useful in distributed online settings. In particular, we apply Markovian hitters to obtain a new algorithm for the well-studied blind rendezvous problem for cognitive radios. This is the problem faced by two parties equipped with radios that can access channels in potentially different subsets, S1 and S2, of a universe of n channels. Their challenge is to discover each other (by tuning their radios to the same channel at the same time) as quickly as possible. In prior work [3] it was shown that deterministic schedules have a lower bound for rendezvous time of Ω(|S1| · |S2|). We beat this quadratic barrier by utilizing a public source of randomness in conjunction with a Markovian hitter to achieve rendezvous in expected time We counterbalance this result by establishing two lower bounds on expected rendezvous time: an bound for the setting with public randomness, and an Ω(|S1| · |S2|) bound in the setting with private randomness but no public randomness, which is a strengthening of the result for deterministic schedules.

From the publish-subscribe systems of the early days of the Internet to the recent emergence of Web 3.0 and IoT (Internet of Things), new problems arise in the design of networks centered at producers and consumers of constantly evolving information. In a typical problem, each terminal is a source or sink of information and builds a physical network in the form of a tree or an overlay network in the form of a star rooted at itself. Every pair of pub-sub terminals that need to be coordinated (e.g. the source and sink of an important piece of control information) define an edge in a bipartite demand graph; the solution must ensure that the corresponding networks rooted at the endpoints of each demand edge overlap at some node. This simple overlap constraint, and the requirement that each network is a tree or a star, leads to a variety of new questions on the design of overlapping networks. In this paper, for the general demand case of the problem, we show that a natural LP formulation has a non-constant integrality gap; on the positive side, we present a logarithmic approximation for the general demand case. When the demand graph is complete, however, we design approximation algorithms with small constant performance ratios, irrespective of whether the pub networks and sub networks are required to be trees or stars.

Real-world networks often consist of multiple layers, be they infrastructure such as airline networks or social such as collaboration networks. A common aspect to these networks is that there are multiple sub-networks that evolve in parallel on the same node set -- these are referred to as multiplex networks. For example, in the case of airline networks, the cities (nodes) have been well-established for several decades if not centuries, but over time new airlines (sub-networks) emerge and each airline creates its own flight linkages between cities. Similarly multiple modalities of communications evolve in parallel between individuals (nodes) such as E-mail, SMS, and Online Social Networks, e.g., Facebook and Twitter. While in some multiplex networks, each layer evolves independently from other layers over time, in other multiple networks, the evolution of a layer is coupled with that of other layers -- a process referred to as co-evolution.

We study the problem of computing a minimum time schedule to spread rumors in a given graph under several models: In the radio model, all neighbors of a transmitting node listen to the messages and are able to record it only when no other neighbor is transmitting; In the wireless model (also called the edge-star model), each transmitter is at a different frequency to which any neighbor can tune to, but only one neighboring transmission can be accessed in this way; In the telephone model, the set of transmitter-receiver pairs form a matching in the graph. The rumor spreading problems assume a message at one or several nodes of the graph that must reach a target node or set of nodes. The transmission proceeds in synchronous rounds under the rules of the corresponding model. The goal is to compute a schedule that completes in the minimum number of rounds. We present a comprehensive study of approximation algorithms for these problems, and show several reductions from the harder to the easier models for special demands. We show a new hardness of approximation of Omega(n^1/2 - epsilon) for the minimum radio gossip time by a connection to maximum induced matchings. We give the first sublinear approximation algorithms for the most general case of the problem under the wireless model; we also consider various special cases such as instances with symmetric demands and give better approximation algorithms. Our work exposes the relationships across the models and opens up several new avenues for further study.

Abstract Confidential Content-Based Publish/Subscribe (C-CBPS) is an interaction model that allows parties to exchange content while protecting their security and privacy interests. In this paper we advance the state of the art in C-CBPS by showing how all predicate circuits in NC1 (logarithmic-depth, bounded fan-in) can be confidentially computed by a broker while guaranteeing perfect information-theoretic security. Previous work could handle only strictly shallower circuits (e.g. those with depth O(ℑ)). We present three protocols—UGP-Match, FSGP-Match and OFSGP-Match—based on 2-decomposable randomized encodings of group programs for circuits in NC1. UGP-Match is conceptually simple and has a clean proof of correctness but its running time is a polynomial with a high exponent and hence impractical. FSGP-Match uses a “fixed structure” construction that reduces the exponent drastically and achieves efficiency and scalability. OFSGP-Match optimizes the group programs further to shave off a linear factor.

We consider the problem of determining the structural differences between different types of social networks and using these differences for applications concerning prediction of their structures. Much research on this problem has been conducted in the context of social media such as Facebook and Twitter, within which one would like to characterize and classify different types of individuals such as leaders, followers, and influencers. However, we consider the problem in the context of information gathered from law-enforcement agencies, financial institutions, and similar organizations, within which one would like to characterize and classify different types of persons of interest. The members of these networks tend to form special communities and thus new techniques are required. We propose a new generative model called Cliqster, for unweighted networks, and we describe an interpretable, and efficient algorithm for representing networks within this model. Our representation preserves the important underlying characteristics of the network and is both concise and discriminative. We demonstrate the discriminative power of our method by comparing to a traditional SVD method as well as a state-of-the-art Graphlet algorithm. Our results are general in that they can be applied to “person of interest” networks as well as traditional social media networks.

Blind rendezvous is a fundamental problem in cognitive radio networks. The problem involves a collection of agents (radios) that wish to discover each other (i.e., rendezvous) in the blind setting where there is no shared infrastructure and they initially have no knowledge of each other. Time is divided into discrete slots and spectrum is divided into discrete channels, [n] = 1, 2, ..., n. Each agent may access (or hop on) a single channel in a single time slot and two agents rendezvous when they hop on the same channel in the same time slot. The goal is to design deterministic channel hopping schedules for each agent so as to guarantee rendezvous between any pair of agents with access to overlapping sets of channels. The problem has three complicating considerations: first, the agents are asymmetric, i.e., each agent Ai only has access to a particular subset Si⊂ [n] of the channels and different agents may have access to different subsets of channels (clearly, two agents can rendezvous only if their channel subsets overlap), second, the agents are synchronous, i.e., they do not possess a common sense of absolute time, so different agents may commence their channel schedules at different times (they do have a common sense of slot duration), lastly, agents are anonymous i.e., they do not possess an identity, and hence the schedule for Ai must depend only on Si. Whether guaranteed blind rendezvous in the asynchronous model was even achievable was an open problem. In a recent breakthrough, two independent sets of authors, Shin et al. (Communications Letters, 2010) and Lin et al. (INFOCOM, 2011), gave the first constructions guaranteeing asynchronous blind rendezvous in O (n2) and O (n3) time, respectively. We present a substantially improved and conceptually simpler construction guaranteeing that any two agents, Ai, Aj, will rendezvous in O (|Si||Sj| log log n) time. Our results are the first that achieve nontrivial dependence on |Si|, the sizes of the sets of available channels. This allows us, for example, to save roughly a quadratic factor over the best previous results in the important case when channel subsets have constant size. We also achieve the best possible bound of O (1) rendezvous time for the symmetric situation, previous works could do no better than O (n). Using techniques from the probabilistic method and Ramsey theory we establish that our construction is nearly optimal: we show both an Ω (|Si||Sj|) lower bound and an Ω(log log n) lower bound when |Si|, |Sj| ≤ n/2.

Over the past two decades, the web has provided dramatic improvements in the ease of sharing content. Unfortunately, the costs of distributing this content are largely incurred by web site operators; popular web sites are required to make substantial monetary investments in serving infrastructure or cloud computing resources---or must pay other organizations (e.g., content distribution networks)---to help serve content. Previous approaches to offloading some of the distribution costs onto end users have relied on client-side software or web browser plug-ins, providing poor user incentives and dramatically limiting their scope in practice.

In hardware virtualization a hypervisor provides multiple Virtual Machines (VMs) on a single physical system, each executing a separate operating system instance. The hypervisor schedules execution of these VMs much as the scheduler in an operating system does, balancing factors such as fairness and I/O performance. As in an operating system, the scheduler may be vulnerable to malicious behavior on the part of users seeking to deny service to others or maximize their own resource usage. Recently, publically available cloud computing services such as Amazon EC2 have used virtualization to provide customers with virtual machines running on the provider's hardware, typically charging by wall clock time rather than resources consumed. Under this business model, manipulation of the scheduler may allow theft of service at the expense of other customers, rather than merely re-allocating resources within the same administrative domain. We describe a flaw in the Xen scheduler allowing virtual machines to consume almost all CPU time, in preference to other users, and demonstrate kernel-based and user-space versions of the attack. We show results demonstrating the vulnerability in the lab, consuming as much as 98% of CPU time regardless of fair share, as well as on Amazon EC2, where Xen modifications protect other users but still allow theft of service (following the responsible disclosure model, we have reported this vulnerability to Amazon; they have since implemented a fix that we have tested and verified). We provide a novel analysis of the necessary conditions for such attacks, and describe scheduler modifications to eliminate the vulnerability. We present experimental results demonstrating the effectiveness of these defenses while imposing negligible overhead. Also, cloud providers such as Amazon's EC2 do not explicitly reveal the mapping of virtual machines to physical hosts [in: ACM CCS, 2009]. Our attack itself provides a mechanism for detecting the co-placement of VMs, which in conjunction with appropriate algorithms can be utilized to reveal this mapping. Other cloud computing attacks may use this mapping algorithm to detect the placement of victims.

We resolve the computational complexity of a number of outstanding open problems with practical applications. Here is the list of problems we show to be ${\bf{PPAD}}$-complete, along with the domains of practical significance: fractional stable paths problem (FSPP)---Internet routing; core of balanced games---economics and game theory; Scarf's lemma---combinatorics; hypergraph matching---social choice and preference systems; fractional bounded budget connection games (FBBC)---social networks; and strong fractional kernel---graph theory. In fact, we show that no fully polynomial-time approximation schemes exist (unless ${\bf{PPAD}}$ is in ${\bf{FP}}$). This paper is entirely a series of reductions that build in nontrivial ways on the framework established in previous work. In the course of deriving these reductions, we created two new concepts---preference games and personalized equilibria. The entire set of new reductions can be presented as a lattice with the above problems sandwiched between preference games (at the “easy” end) and personalized equilibria (at the “hard” end). Our completeness results extend to natural approximate versions of most of these problems.

Many emerging scientific and industrial applications require transferring multiple terabytes of data on a daily basis. Examples include pushing scientific data from particle accelerators/colliders to laboratories around the world, synchronizing datacenters across continents, and replicating collections of high-definition videos from events taking place at different time-zones. A key property of all above applications is their ability to tolerate delivery delays ranging from a few hours to a few days. Such delay-tolerant bulk (DTB) data are currently being serviced mostly by the postal system using hard drives and DVDs, or by expensive dedicated networks. In this paper, we propose transmitting such data through commercial ISPs by taking advantage of already-paid-for off-peak bandwidth resulting from diurnal traffic patterns and percentile pricing. We show that between sender-receiver pairs with small time-zone difference, simple source scheduling policies are able to take advantage of most of the existing off-peak capacity. When the time-zone difference increases, taking advantage of the full capacity requires performing store-and-forward through intermediate storage nodes. We present an extensive evaluation of the two options based on traffic data from 200+ links of a large transit provider with points of presence (PoPs) at three continents. Our results indicate that there exists huge potential for performing multiterabyte transfers on a daily basis at little or no additional cost.

Most of the networks observed in real life obey power-law degree distribution. It is hypothesized that the emergence of such a degree distribution is due to preferential attachment of the nodes. Barabasi-Albert model is a generative procedure that uses preferential attachment based on degree and one can use this model to generate networks with power-law degree distribution. In this model, the network is assumed to grow one node every time step. After the evolution of such a network, it is impossible for one to predict the exact order of node arrivals. We present in this article, a novel strategy to partially predict the order of node arrivals in such an evolved network. We show that our proposed method outperforms other centrality measure based approaches. We bin the nodes and predict the order of node arrivals between the bins with an accuracy of above 80%.

Today, the data exchanged over online social networks (OSNs) represents a significant fraction of Internet traffic. However, OSN content is different from more traditional web content, as it is more likely to be generated at the edge of the network, to be exchanged within a local geographic region, and to possess a more even popularity distribution with fewer popular objects. Unfortunately, most OSNs still use largely centralized approaches to distribute content (e.g., CDNs and web caches), resulting in lower performance due to the different workload. In this paper, we take a first step towards addressing this situation by proposing Web Cloud, a content distribution system for OSNs that works by repurposing client web browsers to help serve content to others. When a user browses content, Web Cloud tries to serve the request from one of that user's friends' browsers, instead of from the OSN directly. Unlike other systems, Web Cloud works with existing browsers and does not require any plug-ins, and therefore can be directly applied to today's OSNs. We demonstrate the practicality of Web Cloud with micro benchmarks, simulations of a Facebook deployment, a real-world deployment, and evaluations of a proof-of-concept iOS app.

Recently, cloud computing services such as Amazon EC2 have used virtualization to provide customers with virtual machines running on the provider's hardware, typically charging by wall clock time rather than resources consumed. Under this business model, manipulation of the scheduler may allow theft-of-service at the expense of other customers. We have discovered and implemented an attack scenario which when implemented on Amazon EC2 allowed virtual machines to consume more CPU time regardless of fair share. We provide a novel analysis of the necessary conditions for such attacks, and describe scheduler modifications to eliminate the vulnerability. We present experimental results demonstrating the effectiveness of these defenses while imposing negligible overhead. Cloud providers such as Amazon's EC2 do not explicitly provide the mapping of VMs to physical hosts. Our attack itself provides a mechanism for detecting the co-placement of VMs, which in conjunction with appropriate algorithms can be utilized to reveal this mapping. We abstract mapping discovery as a problem of finding an unknown partition (i.e. of VMs among physical hosts) using a minimum number of co-location queries. We present an algorithm that is provably optimal when the maximum partition size is bounded. In the unbounded case we show upper and lower bounds using the probabilistic method in conjunction with a sieving technique. Our work has implications beyond this attack, for other cases of system and network topology inference from limited data.

In recent years there has been renewed interest in the problem of transferring bulk data (terabytes) utilizing commercial ISPs. The need to transfer bulk data arises in various scientific and industrial applications. Today, this data is moved using postal service in conjunction with hard drives and DVDs or special high performance dedicated networks. The key insight underlying the recent work was that many of the applications are delay- tolerant and hence the bulk data can be transferred at minimal cost, utilizing already paid-for off-peak bandwidth resulting from diurnal traffic patterns, using store-and-forward through intermediate storage nodes. In this paper we expand on this theme and consider the computational complexity of transferring data over a network whose links have time-varying capacities. We show that the general problem of finding a cost-optimal transfer of the bulk data can be solved in polynomial-time using minimum cost flow algorithms on a time-expanded version of the underlying network. Our solution involves graph transformations. We present additional transformations that enable the handling of half-duplex links (e.g. fiber-optic links) as well as node processing constraints (e.g. limitations on the processing power available for filtering or archiving). An important characteristic of our solution is the ability to handle nodes with storage. We consider nodes with storage that varies over time in terms of both capacity and cost. We show that our approach provably extends to cover the case of linear costs, providing polynomial- time algorithms. However, the flat-fee storage model is NP- complete and hence unlikely to be tractable in polynomial-time. Interestingly, with constrained storage, the optimal solutions may involve loops, i.e. the data may pass through the same node more than once on its way from the destination to the source along the optimal route. We use data from one of the world's leading ISPs and perform a comprehensive evaluation of our algorithm. We show that there exists a huge potential for cost savings in real-world networks with time-varying costs for both link capacities and node storage.

Aspnes et al introduced an innovative game for modeling the containment of the spread of viruses and worms (security breaches) in a network. In this model, nodes choose to install anti-virus software or not on an individual basis while the viruses or worms start from a node chosen uniformly at random and spread along paths consisting of insecure nodes. They showed the surprising result that a pure Nash Equilibrium always exists when all nodes have identical installation costs and identical infection costs. In this paper we present a substantial generalization of the model of that allows for arbitrary security and infection costs, and arbitrary distributions for the starting point of the attack. More significantly, our model GNS(d) incorporates a network locality parameter d which represents a hop-limit on the spread of infection as accounted for in the strategic decisions, due to either the intrinsic nature of the infection or the extent of neighborhood information that is available to a node. We determine that the network locality parameter plays a key role in the existence of pure Nash equilibria (NE): local (d = 1) and global games (d = ∞) have pure NE, while for GNS(d) games with 11.5n) of achieved for a special case of our global model. We study the characteristics of NE and the quality of our approximations empirically in two distinct classes of graphs: random geometric graphs and power law graphs. We find that in local and global games on these real-world networks, best response dynamics converge in linear or sub-linear time and have costs comparable to the social optimum. Finally, we study the performance of our approximation algorithms, and find that the approximation guarantees with respect to social cost are much better in practice than our theoretical bounds.

In a landmark paper, Papadimitriou introduced a number of syntactic subclasses of TFNP based on proof styles that (unlike TFNP) admit complete problems. A recent series of results has shown that finding Nash equilibria is complete for PPAD, a particularly notable subclass of TFNP. A major goal of this work is to expand the universe of known PPAD-complete problems. We resolve the computational complexity of a number of outstanding open problems with practical applications. Here is the list of problems we show to be PPAD-complete, along with the domains of practical significance: Fractional Stable Paths Problem (FSPP) - Internet routing; Core of Balanced Games - Economics and Game theory; Scarf's Lemma - Combinatorics; Hypergraph Matching - Social Choice and Preference Systems; Fractional Bounded Budget Connection Games (FBBC) - Social networks; and Strong Fractional Kernel - Graph Theory. In fact, we show that no fully polynomial-time approximation schemes exist (unless PPAD is in FP). This paper is entirely a series of reductions that build in nontrivial ways on the framework established in previous work. In the course of deriving these reductions, we created two new concepts - preference games and personalized equilibria. The entire set of new reductions can be presented as a lattice with the above problems sandwiched between preference games (at the "easy" end) and personalized equilibria (at the "hard" end). Our completeness results extend to natural approximate versions of most of these problems. On a technical note, we wish to highlight our novel "continuous-to-discrete" reduction from exact personalized equilibria to approximate personalized equilibria using a linear program augmented with an exponential number of "min" constraints of a specific form. In addition to enhancing our repertoire of PPAD-complete problems, we expect the concepts and techniques in this paper to find future use in algorithmic game theory.

The domain name service (DNS) provides a critical function in directing Internet traffic. Defending DNS servers from bandwidth attacks is assisted by the ability to effectively mine DNS log data for statistical patterns. Processing DNS log data can be classified as a data-intensive problem, and as such presents challenges unique to this class of problem. When problems occur in capturing log data, or when the DNS server experiences an outage (scheduled or unscheduled), the normal pattern of traffic for that server becomes clouded. Simple linear interpolation of the holes in the data does not preserve features such as peaks in traffic (which can occur during an attack, making them of particular interest). We demonstrate a method for estimating values for missing portions of time sensitive DNS log data. This method would be suitable for use with a variety of datasets containing time series values where certain portions are missing.

Motivated by applications in social networks, peer-to-peer and overlay networks, we define and study the Bounded Budget Connection (BBC) game- we have a collection of n players or nodes each of whom has a budget for purchasing links; each link has a cost as well as a length and each node has a set of preference weights for each of the remaining nodes; the objective of each node is to use its budget to buy a set of outgoing links so as to minimize its sum of preference-weighted distances to the remaining nodes. We study the structural and complexity-theoretic properties of pure Nash equilibria in BBC games. We show that determining the existence of a pure Nash equilibrium in general BBC games is NP-hard. We counterbalance this result by considering a natural variant, fractional BBC games- where it is permitted to buy fractions of links- and show that a pure Nash equilibrium always exists in such games. A major focus is the study of (n, k)-uniform BBC games- those in which all link costs, link lengths and preference weights are equal (to 1) and all budgets are equal (to k). We show that a pure Nash equilibrium or stable graph exists for all (n, k)-uniform BBC games and that all stable graphs are essentially fair (i.e. all nodes have similar costs). We provide an explicit construction of a family of stable graphs that spans the spectrum from minimum total social cost to maximum total social cost. To be precise we show that that the price of stability is Θ(1) and the price of anarchy is Ω( n/k) and O( logk n

In this paper, we address the problem of cross-layer denial of service attack in wireless data networks. We introduce SPREAD -a novel adaptive diversification approach to provide resiliency against such attacks. SPREAD relies on a mechanism-hopping technique, which can be seen as a multi-layer extension of the frequency-hopping technique. We apply a game-theoretic framework for modeling the interaction of the communicating nodes and the adversaries and analyze the proposed approach. We reason about the advantages of SPREAD against various types of jammers and demonstrate the effectiveness of our approach in the case of IEEE 802.11 protocol stack by studying the EIFS attack, periodical jamming and a Packet-Size Game. As an example, we show that mechanism-hopping over two instances of IEEE 802.11 can achieve several orders of magnitude gain in throughput over a single-instance network under the EIFS attack.

We introduce a game-theoretic framework for reasoning about bandwidth attacks, a common form of distributed denial of service (DDoS) attacks. In particular, our traffic injection game models the attacker as a rational but limited-resource entity who uses limited knowledge of traffic patterns to launch IP spoofing based bandwidth attacks on a server. We model the defender as a coarse-grained, relative volume based statistical filter. We analyze the effectiveness of the defender against the attacker by analyzing the payoffs of various strategies in the traffic injection game. Furthermore, we analyze how these payoffs change in the presence of random noise. Our results show that there is potential for using statistical methods for creating defense mechanisms that can detect a DDoS attack and that even when an attacker has a priori knowledge of the expected traffic volume for the dimension and divisions employed in the attack, the attack traffic can still be exposed to the defender.

A flow of a commodity is said to be confluent if at any node all the flow of the commodity leaves along a single edge. In this article, we study single-commodity confluent flow problems, where we need to route given node demands to a single destination using a confluent flow. Single- and multi-commodity confluent flows arise in a variety of application areas, most notably in networking; in fact, most flows in the Internet are (multi-commodity) confluent flows since Internet routing is destination based. We present near-tight approximation algorithms, hardness results, and existence theorems for minimizing congestion in single-commodity confluent flows. The maximum edge congestion of a single-commodity confluent flow occurs at one of the incoming edges of the destination. Therefore, finding a minimum-congestion confluent flow is equivalent to the following problem: given a directed graph G with k sinks and non-negative demands on all the nodes of G , determine a confluent flow that routes every node demand to some sink such that the maximum congestion at a sink is minimized. The main result of this article is a polynomial-time algorithm for determining a confluent flow with congestion at most 1 + ln( k ) in G , if G admits a splittable flow with congestion at most 1. We complement this result in two directions. First, we present a graph G that admits a splittable flow with congestion at most 1, yet no confluent flow with congestion smaller than H k , the k th harmonic number, thus establishing tight upper and lower bounds to within an additive constant less than 1. Second, we show that it is NP-hard to approximate the congestion of an optimal confluent flow to within a factor of (log 2 k )/2, thus resolving the polynomial-time approximability to within a multiplicative constant. We also consider a demand maximization version of the problem. We show that if G admits a splittable flow of congestion at most 1, then a variant of the congestion minimization algorithm yields a confluent flow in G with congestion at most 1 that satisfies 1/3 fraction of total demand. We show that the gap between confluent flows and splittable flows is much smaller, if the underlying graph is k -connected. In particular, we prove that k -connected graphs with k sinks admit confluent flows of congestion less than C + d max , where C is the congestion of the best splittable flow, and d max is the maximum demand of any node in G . The proof of this existence theorem is non-constructive and relies on topological techniques introduced by Lovász.

Using shortest paths, the Internet scales very poorly with respect to congestion [2]. Two main reasons for using shortest paths are dilation (or delay) and size of routing tables. As the Internet grows, the small size of routing tables is important for scaling, but it does not require shortest paths. As long as the paths are confluent, the routing table size is unchanged. In this paper we study the confluent capacity of the Internet. We use the preferential attachment model [5] for the Internet, and all-pair uniform demand for the traffic pattern. Our main theoretical result is that the confluent congestion1 is within a logarithmic factor of the optimal splittable congestion and can be achieved using a simple randomized and distributed scheme called Locally Independent Rounding Algorithm (LIRA). We reinforce this result experimentally by employing simulations to demonstrate that for almost all instances the confluent congestion is (nearly) equal to the splittable congestion. Thus we conclude that the Internet scales well using confluent paths. We combine known results on expanders and the expansion properties of the preferential attachment model to show that for almost all Internet-like networks, we can find a confluent flow that simultaneously achieves O(log n)- approximate congestion and O(1)-approximate dilation. We confirm, using simulations, the intuition that confluence does not come at the cost of dilation.

In this paper, we propose to address the energy efficient routing problem in multi-hop wireless networks with accumulative relay. In the accumulative relay model, partially overheard signals of previous transmissions for the same packet are used to decode it using a maximal ratio combiner technique [J.G. Proakis, 2001]. Therefore, additional energy saving can be achieved over traditional energy efficient routing. The idea of accumulative relay originates from the study of relay channel in information theory with a main focus on network capacity. It has been independently applied to minimum-energy broadcasting in L.G. Manish Agrawal et al. (2004), I. Maric and R. Yates (2002). We formulate the minimum energy accumulative routing problem (MEAR) and study it. We obtain hardness of approximation results counterbalanced with good heuristic solutions which we validate using simulations. Without energy accumulation, the classic shortest path (SP) algorithm finds the minimum energy path for a source-destination pair. However, we show that with energy accumulation, the SP can be arbitrarily bad. We turn our attention to heuristics and show that any optimal solution of MEAR can be converted to a canonical form - wave path. Armed with this insight, we develop a polynomial time heuristic to efficiently search over the space of all wavepaths. Simulation results show that our heuristic can provide more than 30% energy saving over minimum energy routing without accumulative relay. We also discuss the implementation issues of such a scheme.

We develop an algorithmic framework to decompose a collection of time-stamped text documents into semantically coherent threads. Our formulation leads to a graph decomposition problem on directed acyclic graphs, for which we obtain three algorithms --- an exact algorithm that is based on minimum cost flow and two more efficient algorithms based on maximum matching and dynamic programming that solve specific versions of the graph decomposition problem. Applications of our algorithms include superior summarization of news search results, improved browsing paradigms for large collections of text-intensive corpora, and integration of time-stamped documents from a variety of sources. Experimental results based on over 250,000 news articles from a major newspaper over a period of four years demonstrate that our algorithms efficiently identify robust threads of varying lengths and time-spans.

We introduce a notion of universality in the context of optimization problems with partial information. Universality is a framework for dealing with uncertainty by guaranteeing a certain quality of goodness for all possible completions of the partial information set. Universal variants of optimization problems can be defined that are both natural and well-motivated. We consider universal versions of three classical problems: TSP, Steiner Tree and Set Cover.We present a polynomial-time algorithm to find a universal tour on a given metric space over n vertices such that for any subset of the vertices, the sub-tour induced by the subset is within O(log4n/log log n) of an optimal tour for the subset. Similarly, we show that given a metric space over n vertices and a root vertex, we can find a universal spanning tree such that for any subset of vertices containing the root, the sub-tree induced by the subset is within O(log4n/log log n) of an optimal Steiner tree for the subset. Our algorithms rely on a new notion of sparse partitions, that may be of independent interest. For the special case of doubling metrics, which includes both constant-dimensional Euclidean and growth-restricted metrics, our algorithms achieve an O(log n) upper bound. We complement our results for the universal Steiner tree problem with a lower bound of Ω(log n/log log n) that holds even for n vertices on the plane. We also show that a slight generalization of the universal Steiner Tree problem is coNP-hard and present nearly tight upper and lower bounds for a universal version of Set Cover.

This paper introduces a methodology for estimating interdomain Web traffic lows between all clients worldwide and the ervers belonging to over one housand content providers. The idea is to use the server logs from a large ontent Delivery Network (CDN) to identify client downloads of content provider (i.e., publisher) Web pages. For each of these Web pages, a client typically downloads some objects from the content provider, some from the CDN, and perhaps some from third parties such as banner advertisement agencies. The sizes and sources of the non-CDN downloads associated with each CDN download are estimated separately by examining Web accesses in packet traces collected at several universities.

In recent years, several architectures have been proposed and developed for supporting streaming applications that take advantage of multiple paths through the network simultaneously. We consider the problem of computing a set of paths and the relative amounts of data conveyed through them in order to provide the desired level of performance for data streams. Given the expectation, variance, and covariance of an appropriate metric of interest for overlay links, we attempt to solve the underlying resource allocation problem by applying methods used in managing a finance portfolio. We observe that the flow allocation problem requires constrained application of these methods, and we discuss the tractability of enforcing the constraints. We finally present some simulation results to evaluate the effectiveness of our proposed techniques.

A flow is said to be confluent if at any node all the flow leaves along a single edge. Given a directed graph G with k sinks and non-negative demands on all the nodes of G, we consider the problem of determining a confluent flow that routes every node demand to some sink such that the maximum congestion at a sink is minimized. Confluent flows arise in a variety of application areas, most notably in networking; in fact, most flows in the Internet are confluent since Internet routing is destination based.We present near-tight approximation algorithms, hardness results, and existence theorems for confluent flows. The main result of this paper is a polynomial-time algorithm for determining a confluent flow with congestion at most 1 + ln(k) in G, if G admits a splittable flow with congestion at most 1. We complement this result in two directions. First, we present a graph G that admits a splittable flow with congestion at most 1, yet no confluent flow with congestion smaller than Hk, thus establishing tight upper and lower bounds to within an additive constant less than 1. Second, we show that it is NP-hard to approximate the congestion of an optimal confluent flow to within a factor of (lg k)/2, thus resolving the polynomial-time approximability to within a multiplicative constant. We also consider a demand maximization version of the problem. We show that if G admits a splittable flow of congestion at most 1, then a variant of the congestion minimization algorithm yields a confluent flow in G with congestion at most 1 that satisfies 1/3 fraction of total demand.We show that the gap between confluent flows and splittable flows is much smaller, if the underlying graph were k connected. In particular, we prove that k-connected graphs with k sinks admit confluent flows of congestion less than C + dmax, where C is the congestion of the best splittable flow, and dmax is the maximum demand of any node in G. The proof of this existence theorem is non-constructive and relies on topological techniques introduced in [16].

In this paper we investigate the problem ofdetermining confluent flows with minimum congestion. A flow of a given commodity is said to be confluent if at any node all the flow of the commodity departs along a single edge. Confluent flows appear in a variety of application areas ranging from wireless communications to evacuations; in fact, most flows in the Internet are confluent since Internet routing is destination based.We consider the single commodity confluent flow problem, in which we are given an n-node directed network G, a sink t and supplies at each node, and the goal is to find a confluent flow that routes all the supplies to the sink while minimizing the maximum edge congestion. Our main result is an approximation algorithm, based on randomized rounding, for the special case when all the supplies are uniform; the algorithm finds a confluent flow with edge congestion O(C2 log3 n) where C is the node congestion of an optimal splittable flow. This implies an Õ(√n) approximation algorithm for the problem. Our result relies on the analysis of a natural probabilistic process defined on directed acyclic graphs, that may be of independent interest.For tree networks, we present an optimal polynomial-time algorithm for a multi-sink generalization of the above confluent flow problem. We show that it is NP-hard to approximate the congestion of the optimal confluent flow for general networks to within a factor of 4/3. We also establish a lower bound on the gap between confluent and splittable flows, and consider multicommodity and fractional versions of confluent flow problems.

All-optical networks using wavelength division multiplexing are increasingly coming to be regarded as the technology of choice for the next generation of wide-area backbone networks. These networks incorporate optical switches that employ the concept of Latin Routers for assigning wavelengths to routes. The issue of maximizing wavelength utilization at these switching devices is of great importance since it lends to significant improvements in overall network performance. In this paper we present two fast approximation algorithms-GREEDY and MATCH for the problem of maximizing wavelength utilization at Latin Routers. These are the first known polynomial-time approximation algorithms for the problem of maximizing the number of entries that can be added to a partially filled Latin Square that achieve non-trivial worst-case performance guarantees. These algorithms are easily implementable and have very small constants in their running times making them eminently suitable far actual use in real-world optical switches. We also provide strong experimental evidence to show that, in practice, these algorithms are near-optimal.

Bandwidth is a very valuable resource in wavelength division multiplexed optical networks. The problem of finding an optimal assignment of wavelengths to requests is of fundamental importance in bandwidth utilization. We present a polynomial-time algorithm for this problem on fixed constant-size topologies. We combine this algorithm with ideas from Raghavan and Upfal (1994) to obtain an optimal assignment of wavelengths on constant degree undirected trees. Mihail, Kaklamanis, and Rao (1995) posed the following open question: what is the complexity of this problem on directed trees? We show that it is NP-complete both on binary and constant depth directed trees.

We study the problem of finding small trees. Classical network design problems are considered with the additional constraint that only a specified number k of nodes are required to be connected in the solution. A prototypical example is the kMST problem in which we require a tree of minimum weight spanning at least k nodes in an edge-weighted graph. We show that the kMST problem is NP-hard even for points in the Euclidean plane. We provide approximation algorithms with performance ratio $2\sqrt{k} $ for the general edge-weighted case and $O(k^{1/4} )$ for the case of points in the plane. Polynomial-time exact solutions are also presented for the class of treewidth-bounded graphs, which includes trees, series-parallel graphs, and bounded bandwidth graphs, and for points on the boundary of a convex region in the Euclidean plane. We also investigate the problem of finding short trees and, more generally, that of finding networks with minimum diameter. A simple technique is used to provide a polynomial-time solution for finding k-trees of minimum diameter. We identify easy and hard problems arising in finding short networks using a framework due to T. C. Hu.

The treewidth of a graph is one of the most important graph-theoretic parameters from the algorithmic point of view. However, computing the treewidth and constructing a corresponding tree-decomposition for a general graph is NP-complete. This paper presents an algorithm for computing the treewidth and constructing a corresponding tree-decomposition for circular-arc graphs in $O( n^3 )$ time.