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.

Over the years, there has been extensive work on fully dynamic algorithms for classic graph problems that admit greedy solutions. Examples include (Δ + 1) vertex coloring, maximal independent set, and maximal matching. For all three problems, there are randomized algorithms that maintain a valid solution after each edge insertion or deletion to the n-vertex graph by spending polylog n time, provided that the adversary is oblivious. However, none of these algorithms work against adaptive adversaries whose updates may depend on the output of the algorithm. In fact, even breaking the trivial bound of O (n) against adaptive adversaries remains open for all three problems. For instance, in the case of (Δ + 1) vertex coloring, the main challenge is that an adaptive adversary can keep inserting edges between vertices of the same color, necessitating a recoloring of one of the endpoints. The trivial algorithm would simply scan all neighbors of one endpoint to find a new available color (which always exists) in O (n ) time.

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

Motivated by modern architectures allowing for the partitioning of a GPU into hardware separated instances, we initiate the study of scheduling splittable jobs on configurable machines. We consider machines that can be configured into smaller instances, which we call blocks, in multiple ways, each of which is referred to as a configuration. We introduce the Configurable Machine Scheduling (cms) problem, where we are given n jobs and a set C of configurations. A schedule consists of a set of machines, each assigned some configuration in C with each block in the configuration assigned to process one job. The amount of a job’s demand that is satisfied by a block is given by an arbitrary function of the job and block. The objective is to construct a schedule using as few machines as possible. We provide a tight logarithmic factor approximation algorithm for this problem in the general setting, a factor (3 + ε) approximation algorithm for arbitrary ε > 0 when there are O(1) input configurations, and a polynomial time approximation scheme when both the number and size of configurations are O(1). Finally, we utilize a technique for finding conic integer combinations in fixed dimension to develop an optimal polynomial time algorithm in the case with O(1) jobs, O(1) blocks, and every configuration up to a given size.

In this paper, we revisit the online recoloring problem introduced recently by Azar et al. In online recoloring, there is a fixed set $V$ of $n$ vertices and an initial coloring $c_0: V\rightarrow [k]$ for some $k\in \mathbb{Z}^{>0}$. Under an online sequence $σ$ of requests where each request is an edge $(u_t,v_t)$, a proper vertex coloring $c$ of the graph $G_t$ induced by requests until time $t$ needs to be maintained for all $t$; i.e., for any $(u,v)\in G_t$, $c(u)\neq c(v)$. The objective is to minimize the total weight of vertices recolored for the sequence $σ$. We obtain the first competitive algorithms for capacitated online recoloring and fully dynamic recoloring. Our first set of results is for $2$-recoloring using algorithms that are $(1+\varepsilon)$-resource augmented where $\varepsilon\in (0,1)$ is an arbitrarily small constant. Our main result is an $O(\log n)$-competitive deterministic algorithm for weighted bipartite graphs, which is asymptotically optimal in light of an $Ω(\log n)$ lower bound that holds for an unbounded amount of augmentation. We also present an $O(n\log n)$-competitive deterministic algorithm for fully dynamic recoloring, which is optimal within an $O(\log n)$ factor in light of a $Ω(n)$ lower bound that holds for an unbounded amount of augmentation. Our second set of results is for $Δ$-recoloring in an $(1+\varepsilon)$-overprovisioned setting where the maximum degree of $G_t$ is bounded by $(1-\varepsilon)Δ$ for all $t$, and each color assigned to at most $(1+\varepsilon)\frac{n}Δ$ vertices, for an arbitrary $\varepsilon > 0$. Our main result is an $O(1)$-competitive randomized algorithm for $Δ= O(\sqrt{n/\log n})$. We also present an $O(Δ)$-competitive deterministic algorithm for $Δ\le \varepsilon n/2$. Both results are asymptotically optimal.

A spanning tree T of graph G is a $\rho$-approximate universal Steiner tree (UST) for root vertex r if, for any subset of vertices S containing r, the cost of the minimal subgraph of T connecting S is within a $\rho$ factor of the minimum cost tree connecting S in G. Busch et al. (FOCS 2012) showed that every graph admits $2^{O(\sqrt{\log n})}$-approximate USTs by showing that USTs are equivalent to strong sparse partition hierarchies (up to poly-logs). Further, they posed poly-logarithmic USTs and strong sparse partition hierarchies as open questions.We settle these open questions by giving polynomial-time algorithms for computing both $O\left(\log ^{7} n\right)$-approximate USTs and poly-logarithmic strong sparse partition hierarchies. We reduce the existence of these objects to the previously studied cluster aggregation problem and a class of well-separated point sets which we call dangling nets. For graphs with constant doubling dimension or constant pathwidth we obtain improved bounds by deriving $O(\log n)$-approximate USTs and $O(1)$ strong sparse partition hierarchies. Our doubling dimension result is tight up to second order terms.

We study the problem of scheduling precedence-constrained jobs on heterogenous machines in the presence of non-uniform job and machine communication delays. We are given as input $n$ unit size precedence-ordered jobs and $m$ related machines such that machine $i$ can execute up to $m_i$ jobs at a time. Each machine $i$ has an in-delay $ρ^{\mathrm{in}}_i$ and out-delay $ρ^{\mathrm{out}}_i$. Likewise, each job $v$ has an in-delay $ρ^{\mathrm{in}}_v$ and out-delay $ρ^{\mathrm{out}}_v$. In a schedule, job $v$ may be executed on machine $i$ at time $t$ if each predecessor $u$ of $v$ is completed on $i$ before time $t$ or on any machine $j$ before time $t - (ρ^{\mathrm{in}}_i + ρ^{\mathrm{out}}_j + ρ^{\mathrm{out}}_u + ρ^{\mathrm{in}}_v)$. The goal is to construct a schedule that minimizes makespan. We consider schedules that allow duplication of jobs as well as schedules which do not. When duplication is allowed, we provide an asymptotic $\mathrm{polylog}(n)$-approximation algorithms both when duplication is allowed and when it is not. We also obtain a true $\mathrm{polylog}(n)$-approximation for symmetric machine and job delays. These are the first polylogarithmic approximation algorithms for scheduling with non-uniform communication delays. We also consider a more general model, where the delay can be an arbitrary function of the job and the machine executing it: job $v$ can be executed on machine $i$ at time $t$ if all of $v$'s predecessors are executed on $i$ by time $t-1$ or on any machine by time $t - ρ_{v,i}$. We present an approximation-preserving reduction from the Unique Machines Precedence-constrained Scheduling (UMPS) problem, first defined in [DKRSTZ22], to this job-machine delay model. The reduction entails logarithmic hardness for this delay setting, as well as polynomial hardness if the conjectured hardness of UMPS holds.

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).

We investigate offline and online algorithms for $$\mathsf {Round}\text {-}\mathsf {UFPP}$$ , the problem of minimizing the number of rounds required to schedule a set of unsplittable flows of non-uniform size on a given path with heterogeneous edge capacities. $$\mathsf {Round}\text {-}\mathsf {UFPP}$$ is known to be NP-hard and there are constant-factor approximation algorithms under the no bottleneck assumption (NBA), which stipulates that maximum size of any flow is at most the minimum global edge capacity. In this work, we present improved online and offline algorithms for $$\mathsf {Round}\text {-}\mathsf {UFPP}$$ without the NBA. We first study offline $$\mathsf {Round}\text {-}\mathsf {UFPP}$$ for a restricted class of instances, called $$\alpha $$ -small, where the size of each flow is at most $$\alpha $$ times the capacity of its bottleneck edge, and present an $$O(\log (1/(1-\alpha )))$$ -approximation algorithm. Next, our main result is an online $$O(\log \log c_{\max })$$ -competitive algorithm for $$\mathsf {Round}\text {-}\mathsf {UFPP}$$ where $$c_{\max }$$ is the largest edge capacity, improving upon the previous best bound of $$O(\log c_{\max })$$ due to Epstein et al. (SIAM J Discrete Math 23(2):822–841, 2009). These new results lead to an offline $$O(\min (\log n, \log m, \log \log c_{\max }))$$ -approximation algorithm and an online $$O(\min (\log m, \log \log c_{\max }))$$ -competitive algorithm for $$\mathsf {Round}\text {-}\mathsf {UFPP}$$ , where n is the number of flows and m is the number of edges.

Data-structure dynamization is a general approach for making static data structures dynamic. It is used extensively in geometric settings and in the guise of so-called merge (or compaction) policies in big-data databases such as LevelDB and Google Bigtable. Previous theoretical work is based on worst-case analyses for uniform inputs—insertions of one item at a time and non-varying read rate. In practice, merge policies must not only handle batch insertions and varying read/write ratios, they can take advantage of such non-uniformity to reduce cost on a per-input basis. To model this, we initiate the study of data-structure dynamization through the lens of competitive analysis via two new online set-cover problems. For each, the input is a sequence of disjoint sets of weighted items. The sets are revealed one at a time. The algorithm must respond to each with a set cover that covers all items revealed so far. It obtains the cover incrementally from the previous cover by adding one or more sets and optionally removing existing sets. For each new set the algorithm incurs build cost equal to the weight of the items in the set. In the first problem the objective is to minimize total build cost plus total query cost , where the algorithm incurs a query cost at each time \(t\) equal to the current cover size. In the second problem, the objective is to minimize the build cost while keeping the query cost from exceeding \(k\) (a given parameter) at any time. We give deterministic online algorithms for both variants, with competitive ratios of \(\Theta(\log^{*}n)\) and \(k\) , respectively. The latter ratio is optimal for the second variant.

We consider the problem of scheduling precedence-constrained jobs on uniformly-related machines in the presence of an arbitrary, fixed communication delay. Communication delay is the amount of time that must pass between the completion of a job on one machine and the start of any successor of that job on a different machine. We consider a model that allows job duplication, i.e. processing of the same job on multiple machines, which, as we show, can reduce the length of a schedule (i.e., its makespan) by a logarithmic factor. Our main result is an approximation algorithm for makespan with approximation ratio polylogarithmic in the number of machines and the length of the communication delay, assuming the minimum makespan is at least the delay. Our algorithm is based on rounding a linear programming relaxation for the problem, which includes carefully designed constraints capturing the interaction among communication delay, precedence requirements, varying speeds, and job duplication. To derive a schedule from a solution to the linear program, we balance the benefits of duplication in satisfying precedence constraints early against its drawbacks in increasing overall system load. Our result builds on two previous lines of work, one with communication delay but identical machines (Lepere, Rapine 2002), and the other with uniformly-related machines but no communication delay (Chudak, Shmoys 1999). We next show that the integrality gap of our mathematical program is polylogarithmic in the communication delay. Our gap construction employs expander graphs and exploits a property of robust expansion and its generalization to paths of longer length, which may be of independent interest. Finally, we quantify the advantage of duplication in scheduling with communication delay. We show that the best schedule without duplication can have a larger makespan than the optimal with duplication by a logarithmic factor. Nevertheless, we present a polynomial time algorithm to transform any schedule to a schedule without duplication at the cost of an increase in makespan polylogarithmic in the number of jobs and machines. Together with our makespan approximation algorithm for schedules allowing duplication, this also yields a polylogarithmic-approximation algorithm for the setting where duplication is not allowed.

We study the scheduling of flows on a switch with the goal of optimizing metrics related to the response time of the flows. The input is a sequence of flow requests on a switch, where the switch is represented by a bipartite graph with a capacity on each vertex (port), and a flow request is an edge with associated demand. In each round, a subset of edges can be scheduled under the constraint that the total demand of the scheduled edges incident on any vertex is at most the capacity of the vertex. This class of scheduling problems has applications in datacenter networks, and has been extensively studied. Previous work has essentially settled the complexity of metrics based on completion time. The objective of average or maximum response time, however, is more challenging. To the best of our knowledge, there are no prior approximation algorithms results for these metrics in the context of flow scheduling.

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.

The celebrated Nakamoto consensus protocol [16] ushered in several new consensus applications including cryptocurrencies. A few recent works [7, 17] have analyzed important properties of blockchains, including most significantly, consistency, which is a guarantee that all honest parties output the same sequence of blocks throughout the execution of the protocol. To establish consistency, the prior analysis of Pass, Seeman and Shelat [17] required a careful counting of certain combinatorial events that was difficult to apply to variations of Nakamoto. The work of Garay, Kiayas, and Leonardas [7] provides another method of analyzing the blockchain under the simplifying assumption that the network was synchronous. The contribution of this paper is the development of a simple Markov-chain based method for analyzing consistency properties of blockchain protocols. The method includes a formal way of stating strong concentration bounds as well as easy ways to concretely compute the bounds. We use our new method to answer a number of basic questions about consistency of blockchains: Our new analysis provides a tighter guarantee on the consistency property of Nakamoto's protocol, including for parameter regimes which [17] could not consider; We analyze a family of delaying attacks first presented in [17], and extend them to other protocols; We analyze how long a participant should wait before considering a high-value transaction "confirmed"; We analyze the consistency of CliqueChain, a variation of the Chainweb [14] system; We provide the first rigorous consistency analysis of GHOST [20] and also analyze a folklore "balancing"-attack. In each case, we use our framework to experimentally analyze the consensus bounds for various network delay parameters and adversarial computing percentages. We hope our techniques enable authors of future blockchain proposals to provide a more rigorous analysis of their schemes.

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.

Many modern datacenter applications involve large-scale computations composed of multiple data flows that need to be completed over a shared set of distributed resources. Such a computation completes when all of its flows complete. A useful abstraction for modeling such scenarios is a coflow, which is a collection of flows (e.g., tasks, packets, data transmissions) that all share the same performance goal. In this paper, we present the first approximation algorithms for scheduling coflows over general network topologies with the objective of minimizing total weighted completion time. We consider two different models for coflows based on the nature of individual flows: circuits, and packets. We design constant-factor polynomial-time approximation algorithms for scheduling packet-based coflows with or without given flow paths, and circuit-based coflows with given flow paths. Furthermore, we give an O(log n/log log n)-approximation polynomial time algorithm for scheduling circuit-based coflows without given flow paths (here n is the number of network edges).

Motivated by the growing complexity and heterogeneity of modern data centers, and the prevalence of commodity component failures, this paper studies the failure-aware placement problem of placing tasks of a parallel job on machines in the data center with the goal of increasing availability. We consider two models of failures: adversarial and probabilistic. In the adversarial model, each node has a weight (higher weight implying higher reliability) and the adversary can remove any subset of nodes of total weight at most a given bound W and our goal is to find a placement that incurs the least disruption against such an adversary. In the probabilistic model, each node has a probability of failure and we need to find a placement that maximizes the probability that at least K out of N tasks survive at any time.

Coalescing-branching random walks, or cobra walks for short, are a natural variant of random walks on graphs that can model the spread of disease through contacts or the spread of information in networks. In a k-cobra walk, at each time step a subset of the vertices are active; each active vertex chooses k random neighbors (sampled independently and uniformly with replacement) that become active at the next step, and these are the only active vertices at the next step. A natural quantity to study for cobra walks is the cover time, which corresponds to the expected time when all nodes have become infected or received the disseminated information.

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.

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.

Summary The Area of a schedule Σ for a directed acyclic graph (DAG) is a quality metric that measures the rate at which Σ renders 's nodes eligible for execution. Specifically, AREA(Σ) is the average number of nodes of that are eligible for execution as Σ executes node by node. Extensive simulations suggest that, for many distributions of processor availability and power, DAG‐schedules having larger Areas execute DAGs faster on platforms that are dynamically heterogeneous: the platform's processors change power and availability status in unpredictable ways and at unpredictable times. (Clouds and desktop grids exemplify such platforms.) While Area‐maximal schedules can provably be found for everyDAG, efficient generators of such schedules are known only for families of well‐structured DAGs. Our first result shows that the problem of crafting Area‐maximal schedules for general DAGs is NP‐complete, hence likely computationally intractable. We also provide an efficient algorithm that approximates optimal Area to within a factor of , where n is the number of tasks in the DAG—a factor that is likely interesting only for small DAGs. The lack of efficient Area‐maximizing schedulers for general DAGs has instigated the development of several heuristics for producing DAG‐schedules that have large Areas. We propose a novel polynomial‐time heuristic that produces schedules having quite large Areas; the heuristic is based on the Sidney decomposition of a DAG. (1) Simulations on DAGs having random structure yield the following results. The SIDNEY heuristic produces schedules whose Areas: (a) are at least 85% of maximal; and (b) are at least 1.25 times greater than previously known heuristics. (2) Simulations on DAGs having the structure of random LEGO®;DAGs (as formulated in earlier studies) indicate that the schedules produced by the SIDNEY heuristic have Areas that are at least 1.5 times greater than previously known heuristics. The ‘85%’ result is obtained from formulating the Area‐maximization problem as a linear program (LP); the Areas of DAG‐schedules produced by the SIDNEY heuristic are at least 85% of the Area value produced by the (unrounded) LP. (3) The reported results on random DAGs are essentially matched by a second heuristic, which produces DAG‐schedules by rounding the results of the LP formulation. Copyright © 2015 John Wiley & Sons, Ltd.

We study how to spread k tokens of information to every node on an n-node dynamic network, the edges of which are changing at each round. This basic gossip problem can be completed in O(n + k) rounds in any static network, and determining its complexity in dynamic networks is central to understanding the algorithmic limits and capabilities of various dynamic network models. Our focus is on token-forwarding algorithms, which do not manipulate tokens in any way other than storing, copying and forwarding them. We first consider the strongly adaptive adversary model where in each round, each node first chooses a token to broadcast to all its neighbors (without knowing who they are), and then an adversary chooses an arbitrary connected communication network for that round with the knowledge of the tokens chosen by each node. We show that Ω(nk/log n + n) rounds are needed for any randomized (centralized or distributed) token-forwarding algorithm to disseminate the k tokens, thus resolving an open problem raised in [KLO10]. The bound applies to a wide class of initial token distributions, including those in which each token is held by exactly one node and well-mixed ones in which each node has each token independently with a constant probability. Our result for the strongly adaptive adversary model motivates us to study the weakly adaptive adversary model where in each round, the adversary is required to lay down the network first, and then each node sends a possibly distinct token to each of its neighbors. We propose a simple randomized distributed algorithm where in each round, along every edge (u, v), a token sampled uniformly at random from the symmetric difference of the sets of tokens held by node u and node v is exchanged. We prove that starting from any well-mixed distribution of tokens where each node has each token independently with a constant probability, this algorithm solves the k-gossip problem in O((n + k) log n log k) rounds with high probability over the initial token distribution and the randomness of the protocol. We then show how the above uniform sampling problem can be solved using Õ(log n) bits of communication, making the overall algorithm communication-efficient. We next present a centralized algorithm that solves the gossip problem for every initial distribution in O((n + k) log2 n) rounds in the offline setting where the entire sequence of communication networks is known to the algorithm in advance. Finally, we present an -round centralized offline algorithm in which each node can only broadcast a single token to all of its neighbors in each round.

We study a distributed randomized information propagation mechanism in networks we call the coalescing-branching random walk (cobra walk, for short). A cobra walk is a generalization of the well-studied "standard" random walk, and is useful in modeling and understanding the Susceptible-Infected Susceptible (SIS)-type of epidemic processes in networks. It can also be helpful in performing light-weight information dissemination in resource-constrained networks. A cobra walk is parameterized by a branching factor k. The process starts from an arbitrary node, which is labeled active for step 1. (For instance, this could be a node that has a piece of data, rumor, or a virus.) In each step of a cobra walk, each active node chooses k random neighbors to become active for the next step ("branching"). A node is active for step t + 1 only if it is chosen by an active node in step t ("coalescing"). This results in a stochastic process in the underlying network with properties that are quite different from both the standard random walk (which is equivalent to the cobra walk with branching factor 1) as well as other gossip-based rumor spreading mechanisms.

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.

We study the problem of constructing universal Steiner trees for undirected graphs. Given a graph G and a root node r, we seek a single spanning tree T of minimum stretch, where the stretch of T is defined to be the maximum ratio, over all terminal sets X, of the cost of the minimal sub-tree TXof T that connects X to r to the cost of an optimal Steiner tree connecting X to r in G. Universal Steiner trees (USTs) are important for data aggregation problems where computing the Steiner tree from scratch for every input instance of terminals is costly, as for example in low energy sensor network applications. graphs with 2O(√log n)-stretch. We also give a polynomial time We provide a polynomial time UST construction for general polylog(n)-stretch construction for minor-free graphs. One basic building block of our algorithms is a hierarchy of graph partitions, each of which guarantees small strong diameter for each cluster and bounded neighbourhood intersections for each node. We show close connections between the problems of constructing USTs and building such graph partitions. Our construction of partition hierarchies for general graphs is based on an iterative cluster merging procedure, while the one for minor-free graphs is based on a separator theorem for such graphs and the solution to a cluster aggregation problem that may be of independent interest even for general graphs. To our knowledge, this is the first subpolynomial-stretch (o(nε) for any ε >; 0) UST construction for general graphs, and the first polylogarithmic-stretch UST construction for minor-free graphs.

We study randomized gossip-based processes in dynamic networks that are motivated by information discovery in large-scale distributed networks such as peer-to-peer and social networks. A well-studied problem in peer-to-peer networks is resource discovery, where the goal for nodes (hosts with IP addresses) is to discover the IP addresses of all other hosts. Also, some of the recent work on self-stabilization algorithms for P2P/overlay networks proceed via discovery of the complete network. In social networks, nodes (people) discover new nodes through exchanging contacts with their neighbors (friends). In both cases the discovery of new nodes changes the underlying network --- new edges are added to the network --- and the process continues in the changed network. Rigorously analyzing such dynamic (stochastic) processes in a continuously changing topology remains a challenging problem with obvious applications.

Motivated by publish-subscribe mechanisms in networks, we introduce a new class of multicommodity facility location problems: Multicommodity Group Steiner Facility Location (MGSFL). The input to MGSFL consists of a metric space over a given set of locations, a cost function which provides a building cost for each commodity at each location, a set of clients located at various points in the metric, and the set of commodities that each client is interested in reaching. A solution to MGSFL consists of (a) for each commodity, the locations where facilities are built, and (b) for each client, a tree connecting the client to at least one facility for each commodity in its interest set. The goal is to minimize the sum of the total facility building costs and the metric cost of the client trees. MGSFL is a natural generalization of the well-studied Group Steiner Tree problem, which is equivalent to the special case of MGSFL in which every building cost is either 0 or ∞ and there is only one client. We also note that given the facility locations, the best client tree is an optimal solution to an appropriate Group Steiner Tree instance. Since the Group Steiner Tree problem is hard to approximate to within a factor of Ω(log2–ε m) times optimum unless NP has quasi-polynomial Las Vegas algorithms, where m is the number of commodities, the same hardness result immediately extends to MGSFL. Our main result is a randomized approximation algorithm for MGSFL, where n is the number of clients. We also present deterministic poly-logarithmic approximations for three special cases. We give an O(log n)-approximation algorithm when the facility building costs differ only by commodity, not by location. We present an O(log4 n log m)-approximation algorithm when the interest sets are laminar — i.e., for each pair of clients, either their interest sets do not intersect or else one client's interest set is contained within the other client's interest set. We end with an O(log n)-approximation algorithm when there are no building costs but each commodity must be built exactly once.

We investigate the resiliency of IEEE802.11 rate adaptation algorithms (RAA) against smart jamming attacks. We consider several classes of state-of-the-art RAAs that include the SampleRate, ONOE, AMRR, and the RAA used in Atheros Microsoft Windows XP driver. We model the behavior of these algorithms, and show the existence of very efficient attacks that exploit RAA-specific vulnerabilities as well as the inherent weaknesses that exist in the design of IEEE802.11 MAC and link layer protocol: in particular the overt packet rate information being transmitted, predictable rate selection mechanism, performance anomaly caused by the equiprobability of transmissions among all nodes regardless of the data rates being employed, and the lack of interference differentiation from poor link quality by IEEE802.11 RAAs. In this work, we present algorithms that determine optimal jamming strategies against RAAs for a given jamming budget, and experimentally demonstrate the efficiency of these smart jamming attacks, which can be orders of magnitude more efficient than naive jamming. For example, in the case of SampleRate, eight reactive jamming pulses every second are sufficient to achieve the same network throughput degradation achieved by a periodic jammer with the jamming energy cost 100 times higher. Some of the RAAs react even worse to smart jamming attacks; ONOE in particular suffers from the phenomenon of congestion collapse where the nodes fail to recover from the lowest data rate even after the jammer stops jamming. At the end, we summarize fundamental reasons behind such RAA vulnerabilities and propose a preliminary set of mitigation techniques. We leave the experimental demonstration of the efficiency of the proposed mitigation mechanisms for future work.

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.

We present a general framework and algorithmic approach for incremental approximation algorithms. The framework handles cardinality constrained minimization problems, such as the k-median and k-MST problems. Given some notion of ordering on solutions of different cardinalities k, we give solutions for all values of k such that the solutions respect the ordering and such that for any k, our solution is close in value to the value of an optimal solution of cardinality k. For instance, for the k-median problem, the notion of ordering is set inclusion, and our incremental algorithm produces solutions such that for any k and $k'$, $k

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.

This section comprises fully refereed versions of nine papers that were presented at the Forty-Seventh Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), held in Berkeley, California, October 22–24, 2006. The FOCS 2006 Program Committee consisted of Sanjeev Arora (chair), Rajeev Alur, Matthew Andrews, Avrim Blum, Moses Charikar, Shuchi Chawla, Jeff Erickson, Lisa Fleischer, Lance Fortnow, Ravi Kannan, Sampath Kannan, Haim Kaplan, Anna Karlin, Joe Kilian, Guy Kindler, Ashwin Nayak, Christos Papadimitriou, Harald Räcke, Rajmohan Rajaraman, Dana Randall, Michael Saks, Daniel Spielman, and Peter Winkler. The committee selected 71 of 240 papers to be presented at the symposium, and unrefereed preliminary versions of these papers appeared in the conference proceedings, which were published by IEEE. The nine papers selected for this section cover a number of topics and problems in theoretical computer science, including computational geometry, smoothed complexity, learning, list decoding, set partitioning and matching. Each paper was extensively reviewed, and most underwent multiple revisions. We would like to thank all those who contributed to this special section, including the anonymous referees; the SIAM Journal on Computing Editor-in-Chief, Eva Tardos; and SIAM staff members Melissa Buono, Mitch Chernoff, and Cherie Trebisky.

In this paper, we study the performance of the IEEE 802.11 MAC protocol under a range of jammers that covers both channel-oblivious and channel-aware jamming. We study two channel-oblivious jammers: a periodic jammer that jams deterministically at a specified rate, and a memoryless jammer whose signals arrive according to a Poisson process. We also develop new models for channel-aware jamming, including a reactive jammer that only jams non-colliding transmissions and an omniscient jammer that optimally adjusts its strategy according to current states of the participating nodes. Our study comprises of a theoretical analysis of the saturation throughput of 802.11 under jamming, an extensive simulation study, and a testbed to conduct real world experimentation of jamming IEEE 802.11 using GNU Radio and USRP platform. In our theoretical analysis, we use a discrete-time Markov chain analysis to derive formulae for the saturation throughput of IEEE 802.11 under memoryless, reactive and omniscient jamming. One of our key results is a characterization of optimal omniscient jamming that establishes a lower bound on the saturation throughput of 802.11 under arbitrary jammer attacks. We validate the theoretical analysis by means of Qualnet simulations. Finally, we measure the real-world performance of periodic and memoryless jammers using our GNU radio jammer prototype.

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

We develop approximation algorithms for the problem of placing replicated data in arbitrary networks, where the nodes may both issue requests for data objects and have capacity for storing data objects so as to minimize the average data-access cost. We introduce the data placement problem to model this problem. We have a set of caches $\mathcal{F}$, a set of clients $\mathcal{D}$, and a set of data objects $\mathcal{O}$. Each cache i can store at most $u_i$ data objects. Each client $j\in\mathcal{D}$ has demand $d_j$ for a specific data object $o(j)\in\mathcal{O}$ and has to be assigned to a cache that stores that object. Storing an object o in cache i incurs a storage cost of $f_i^o$, and assigning client j to cache i incurs an access cost of $d_jc_{ij}$. The goal is to find a placement of the data objects to caches respecting the capacity constraints, and an assignment of clients to caches so as to minimize the total storage and client access costs. We present a 10-approximation algorithm for this problem. Our algorithm is based on rounding an optimal solution to a natural linear-programming relaxation of the problem. One of the main technical challenges encountered during rounding is to preserve the cache capacities while incurring only a constant-factor increase in the solution cost. We also introduce the connected data placement problem to capture settings where write-requests are also issued for data objects, so that one requires a mechanism to maintain consistency of data. We model this by requiring that all caches containing a given object be connected by a Steiner tree to a root for that object, which issues a multicast message upon a write to (any copy of) that object. The total cost now includes the cost of these Steiner trees. We devise a 14-approximation algorithm for this problem. We show that our algorithms can be adapted to handle two variants of the problem: (a) a k-median variant, where there is a specified bound on the number of caches that may contain a given object, and (b) a generalization where objects have lengths and the total length of the objects stored in any cache must not exceed its capacity.

Motivated by applications in grid computing and project management, we study multiprocessor scheduling in scenarios where there is uncertainty in the successful execution of jobs when assigned to processors. We consider the problem of multiprocessor scheduling under uncertainty, in which we are given n unit-time jobs and m machines, a directed acyclic graph C giving the dependencies among the jobs, and for every job j and machine i, the probability pij of the successful completion of job j when scheduled on machine i in any given particular step. The goal of the problem is to find a schedule that minimizes the expected makespan, that is, the expected completion time of all the jobs.

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.

Sensor networks are being increasingly deployed for diverse monitoring applications. Event data are collected at various sensors and sent to selected storage nodes for further in-network processing. Since sensor nodes have strong constraints on their energy usage, this data transfer needs to be energy-efficient to maximize network lifetime. In this article, we propose a novel methodology for trading energy versus latency in sensor database systems. We propose a new protocol that carefully schedules message transmissions so as to avoid collisions at the MAC layer. Since all nodes adhere to the schedule, their radios can be off most of the time and only wake up during well-defined time intervals. We show how routing protocols can be optimized to interact symbiotically with scheduling decisions, resulting in significant energy savings at the cost of higher latency. We demonstrate the effectiveness of our approach by means of a thorough simulation study, using synthetic data as well as real-world traffic workloads.

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.

Consider a network in which a collection of source nodes maintain and periodically update data objects for a collection of sink nodes, each of which periodically accesses the data originating from some specified subset of the source nodes. We consider the task of efficiently relaying the dynamically changing data objects to the sinks from their sources of interest. Our focus is on the following "push-pull" approach for this data dissemination problem. Whenever a data object is updated, its source relays the update to a designated subset of nodes, its push set; similarly, whenever a sink requires an update, it propagates its query to a designated subset of nodes, its pull set. The push and pull sets need to be chosen such that every pull set of a sink intersects the push sets of all its sources of interest. We study the problem of choosing push sets and pull sets to minimize total global communication while satisfying all communication requirements.We formulate and study several variants of the above data dissemination problem, that take into account different paradigms for routing between sources (resp., sinks) and their push sets (resp., pull sets) -- multicast, unicast, and controlled broadcast -- as well as the aggregability of the data objects. Under the multicast model, we present an optimal polynomial time algorithm for tree networks, which yields a randomized O(log n)-approximation algorithm for n-node general networks, for which the problem is hard to approximate within a constant factor. Under the unicast model, we present a randomized O(log n)-approximation algorithm for non-metric costs and a matching hardness result. For metric costs, we present an O(1)-approximation and matching hardness result for the case where the interests of any two sinks are either disjoint or identical. Finally, under the controlled broadcast model, we present optimal polynomial-time algorithms.While our optimization problems have been formulated in the context of data communication in networks, our problems also have applications to network design and multicommodity facility location and are of independent interest.

This paper is concerned with compact routing schemes for arbitrary undirected networks in the name‐independent model first introduced by Awerbuch, Bar‐Noy, Linial, and Peleg. A compact routing scheme that uses local routing tables of size $\~{O}(n^{1/2})$, $O(\log^2 n)$‐sized packet headers, and stretch bounded by 5 is obtained, where n is the number of nodes in the network. (We use the notation $\~{O}\left(f(n)\right)$ to represent $O(f(n)\log^c{n})$, where c is an arbitrary nonnegative real number, independent of n.) Alternative schemes reduce the packet header size to $O(\log n)$ at the cost of either increasing the stretch to 7 or increasing the table size to $\~{O}(n^{2/3})$. For smaller table‐size requirements, the ideas in these schemes are generalized to a scheme that uses $O(\log^2 n)$‐sized headers and ${O}(k^2n^{2/k})$‐sized tables, and achieves a stretch of $\min\{1 + (k-1)(2^{k/2}-2), 16k^2-8k\}$, improving the best previously known name‐independent scheme due to Awerbuch and Peleg.

No abstract available.

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.

We introduce a new power control scheme, for IEEE 802.11-like MAC protocols. Our scheme carefully combines collision avoidance and spatial reuse. Although many power control schemes were proposed for IEEE 802.11, to the best of our knowledge, our scheme is the first to achieve significant improvements for network throughput and energy efficiency simultaneously (up to 40% throughput increase and 3 times more data delivery with the same amount of energy), while adhering to the single-channel, single-transceiver design rule. Furthermore, our scheme solves the fairness problem identified in (J. Monks et al, IEEE INFOCOM, 2003), i.e., IEEE 802.11 and some power control schemes deliver more packets for short distance source-destination pairs than for long distance pairs. Thus, our scheme also improves the bit-metre/sec metric (by up to 70%). Our proposed scheme belongs to a more general class of power control schemes, that we extensively simulate. We also provide a theoretical analysis to justify our approach and simulation results.

In this paper, we propose a novel general technique, based on renewal theory, for analyzing mobility models in ad hoc networks. Our technique enables an accurate derivation of the steady state distribution functions for node movement parameters such as distance and speed. We first apply our technique to the random waypoint model and provide alternative proofs for previous claims about the discrepancy between the steady state average speed and the average speed associated with the simulated distribution (Yoon, J et al., 2003). Our main contribution is a new methodology for simulating mobility which guarantees steady state for node movement distributions from the start of the simulation. Our methodology enables the correct and efficient simulation of a desired steady state distribution, and can be implemented in a manner transparent to the user. We support our claims through both formal proofs as well as extensive simulations.

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].

We consider the classical problem of online job scheduling on uniprocessor and multiprocessor machines. For a given job, we measure the quality of service provided by an algorithm by the stretch of the job, which is defined as the ratio of the amount of time that the job spends in the system to the processing time of the job. For a given sequence of jobs, we measure the performance of an algorithm by the average stretch achieved by the algorithm over all the jobs in the sequence. The average stretch metric has been used to evaluate the performance of scheduling algorithms in many applications arising in databases, networks, and systems. The main contribution of this paper is to show that the shortest remaining processing time (SRPT) algorithm is O(1)-competitive with respect to average stretch for both uniprocessors and multiprocessors. For uniprocessors, we prove that SRPT is 2-competitive; we also establish an essentially matching lower bound on the competitive ratio of SRPT. For multiprocessors, we show that the competitive ratio of SRPT is at most $9 + 2\sqrt{6} \le 14$. Furthermore, we establish constant-factor lower bounds on the competitive ratio of any online algorithm for both uniprocessors and multiprocessors.

This paper is concerned with compact routing in the name independent model first introduced by Awerbuch et al. [1] for adaptive routing in dynamic networks. A compact routing scheme that uses local routing tables of size Õ(n1/2), O(log2 n)-sized packet headers, and stretch bounded by 5 is obtained. Alternative schemes reduce the packet header size to O(log n) at cost of either increasing the stretch to 7, or increasing the table size to Õ(n2/3). For smaller table-size requirements, the ideas in these schemes are generalized to a scheme that uses O(log2 n)-sized headers, Õ(k2n2/k)-sized tables, and achieves a stretch of min[1 + (k-1)(2k/2-2), 16k2+4k ], improving the best previously-known name-independent scheme due to Awerbuch and Peleg [3].

An ad hoc network is a collection of wireless mobile hosts forming a temporary network without the aid of any fixed infrastructure. Indeed, an important task of an ad hoc network is to determine an appropriate topology over which high-level routing protocols are implemented. Furthermore, since the underlying topology may change with time, we need to design routing algorithms that effectively react to dynamically changing network conditions.The aim of this paper is to explore the limits of communication in wireless mobile networks, concentrating on local-control algorithms for topology control and routing. We analyze the performance of the algorithms under three measures: throughput, which is the rate at which packets can be delivered, space overhead, i.e. the space necessary to buffer packets, and the total energy consumed due to packet transmissions. Energy consumption is an important performance measure for ad hoc networks since the battery power of mobile nodes is usually limited.Towards topology control, we show that for any distribution of nodes in the 2-dimensional Euclidean plane, a simple local algorithm allows to establish and maintain a connected constant degree overlay network that contains energy-efficient paths between every pair of nodes. Towards routing, we present a local routing algorithm that works for arbitrary overlay networks without transmission interference. We show that for any sequence of network changes and packet injections the algorithm is within a constant factor of the optimal, with respect to both throughput and energy, when compared to what a best possible routing algorithm can achieve under the same sequence of network changes and injection. We then combine the topology control and routing algorithms to obtain competitive wireless communication algorithms that account for transmission interference, an important performance-limiting aspect of wireless communication.

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.

Consider an arbitrary distributed network in which large numbers of objects are continuously being created, replicated, and destroyed. A basic problem arising in such an environment is that of organizing a data tracking scheme for locating object copies. In this paper, we present a new tracking scheme for locating nearly copies of replicated objects in arbitrary distributed environments.

We consider the classical problem of online job scheduling on uniprocessor and multiprocessor machines. For a given job, we measure the quality of service provided by an algorithm by the stretch of the job, which is defined as the ratio of the amount of time that the job spends in the system to the processing time of the job. For a given sequence of jobs, we measure the performance of an algorithm by the average stretch achieved by the algorithm over all the jobs in the sequence. The average stretch metric has been used to evaluate the performance of scheduling algorithms in many applications arising in databases, networks and systems; however no formal analysis of scheduling algorithms is known for the average stretch metric. The main contribution of the paper is to show that the shortest remaining processing time algorithm (SRPT) is O(l)-competitive with respect to average stretch for both uniprocessors as well as multiprocessors. For uniprocessors, we prove that SRPT is 2-competitive; we also establish an essentially matching lower bound on the competitive ratio of SRPT. For multiprocessors, we show that the competitive ratio of SRPT is at most 14. Furthermore, we establish constant-factor lower bounds on the competitive ratio of any online algorithm for both uniprocessors and multiprocessors.

This paper proposes a protocol suite for dynamic replication and migration of Internet objects. It consists of an algorithm for deciding on the number and location of object replicas and an algorithm for distributing requests among currently available replicas. Our approach attempts to place replicas in the vicinity of a majority of requests while ensuring at the same time that no servers are overloaded. The request distribution algorithm uses the same simple mechanism to take into account both server proximity and load, without actually knowing the latter. The replica placement algorithm executes autonomously on each node, without the knowledge of other object replicas in the system. The proposed algorithms rely on the information available in databases maintained by Internet routers. A simulation study using synthetic workloads and the network backbone of UUNET, one of the largest Internet service providers, shows that the proposed protocol is effective in eliminating hot spots and ...

The time-constrained packet routing problem is to schedule a set of packets to be routed through a multi-node network, where every packet has a source and a destination (as in traditional packet routing problems) as well as a release time and a deadline.The objective is to route the maximum number of packets subject to these constraints.This problem was studied in [l], where it was shown that the problem is NP-Complete even when the underlying topology is a linear array.Approximation algorithms were also provided in [l] for the linear array and the unidirectional ring for both the case where packets may be buffered in transit and the case where they may not be.In this paper, we extend the results of [l] in two directions.First, we consider the more general network topologies of trees and meshes.Second, we associate with each packet a measure of utility, called a weight, and study the problem of maximizing the total weight of the packets that are routed subject to their timing constraints.For the bufferless case, we provide a constant factor approximation for the time-constrained routing problem with weighted packets on a tree, and on a mesh.We also provide a logarithmic approximation for the same problems in the buffered case.These results are complemented by new lower bounds, which

We study the approximability of two classes of network routing problems.The first class of problems in our study corre spend to classical multicommodity flow problems of the following form: We are given a network G with integer capacities on its edges, together with source-sink pairs (a, ti), 1 5 i 2 k, such that a positive integer demand di and a positive "profit" t'i is associated with eah pair.A feasible solution is a subset S of the (sir ti) pairs such that demands associated with pairs in S can be fully met through a routing which respects all capacity constraints, and the objective is to maximize the total profit associated with the satisfied pairs.We consider two natural variants: unsplittable flow (USF) where each pair must be satisfied by routing all its demand on a single

This paper presents an analysis of the following load balancing algorithm. At each step, each node in a network examines the number of tokens at each of its neighbors and sends a token to each neighbor with at least 2d+1 fewer tokens, where d is the maximum degree of any node in the network. We show that within $O(\Delta / \alpha)$ steps, the algorithm reduces the maximum difference in tokens between any two nodes to at most $O((d^2 \log n)/\alpha)$, where $\Delta$ is the global imbalance in tokens (i.e., the maximum difference between the number of tokens at any node initially and the average number of tokens), n is the number of nodes in the network, and $\alpha$ is the edge expansion of the network. The time bound is tight in the sense that for any graph with edge expansion $\alpha$, and for any value $\Delta$, there exists an initial distribution of tokens with imbalance $\Delta$ for which the time to reduce the imbalance to even $\Delta/2$ is at least $\Omega(\Delta/\alpha)$. The bound on the final imbalance is tight in the sense that there exists a class of networks that can be locally balanced everywhere (i.e., the maximum difference in tokens between any two neighbors is at most 2d), while the global imbalance remains $\Omega((d^2 \log n) / \alpha)$. Furthermore, we show that upon reaching a state with a global imbalance of $O((d^2 \log n)/\alpha)$, the time for this algorithm to locally balance the network can be as large as $\Omega(n^{1/2})$. We extend our analysis to a variant of this algorithm for dynamic and asynchronous networks. We also present tight bounds for a randomized algorithm in which each node sends at most one token in each step.

We study the problem of balancing the load on processors of an arbitrary network. If jobs arrive or depart during the process of load balancing, we have the dynamic load balancing problem; otherwise, we have the static load balancing problem. While static load balancing on arbitrary and special networks has been well studied, very little is known about dynamic load balancing. The difficulty lies in modeling the arrivals and departures of jobs in a clean manner. In this paper, we initiate the study of dynamic load balancing by modeling job traffic using an adversary. Our main result is that a simple, local control distributed load balancing algorithm maintains the load of the network within a stable level against this powerful adversary. Our results hold for different models of traffic patterns and processor communication.

Consider an on-line scheduling problem in which a set of abstract processes are competing for the use of a number of resources. Further assume that it is either prohibitively expensive or impossible for any two of the processes to directly communicate with one another. If several processes simultaneously attempt to allocate a particular resource (as may be expected to occur, since the processes cannot easily coordinate their allocations), then none succeed. In such a framework, it is a challenge to design efficient contention resolution protocols. Two recently-proposed approaches to the problem of PRAM emulation give rise to scheduling problems of the above kind. In one approach, the resources (in this case, the shared memory cells) are duplicated and distributed randomly. We analyze a simple and efficient deterministic algorithm for accessing some subset of the duplicated resources. In the other approach, we analyze how quickly we can access the given (nonduplicated) resource using a simple randomized strategy. We obtain precise bounds on the performance of both strategies. We anticipate that our results with find other applications.

Consider a set of shared objects in a distributed network, where several copies of each object may exist at any given time.To ensure both fast access to the objects as well as efficient utilization of network resources, it is desirable that each access request be satisfied by a copy "close" to the requesting node.Unfortunately, it is not clear how to efficiently achieve this goal in a dynamic, distributed environment in which large numbers of objects are continuously being created, replicated, and destroyed,In this paper, we design a simple randomized algorithm for accessing shared objects that tends to satisfy each access request with a nearby copy.The algorithm is based on a novel mechanism to maintain and distribute information about object locations, and requires only a smaIl amount of additional memory at each node.We analyze our access scheme for a class of cost functions that captures the hierarchical nature of wide-area networks.We show that under the particular cost model considered: (i) the expected cost of an individual access is asymptotically optimal, and (ii) if objects are sufficiently large, the memory used for objects dominates the additional memory used by our algorithm with high probability.We also address dynamic changes in both the network as well as the set of object copies.

The authors consider a synchronous model of distributed computation in which n nodes communicate via point-to-point messages, subject to the following constraints: (i) in a single "step", a node can only send or receive O(logn) words, and (ii) communication is unreliable in that a constant fraction of all messages are lost at each step due to node and/or link failures. They design and analyze a simple local protocol for providing fast concurrent access to shared objects in this faulty network environment. In the protocol, clients use a hashing-based method to access shared objects. When a large number of clients attempt to read a given object at the same time, the object is rapidly replicated to an appropriate number of servers. Once the necessary level of replication has been achieved, each remaining request for the object is serviced within O(1) expected steps. The protocol has practical potential for supporting high levels of concurrency in distributed file systems over wide area networks.

. This paper presents an analysis of the following load balancing algorithm. At each step, each node in a network examines the number of tokens at each of its neighbors and sends a token to each neighbor with at least 2d + 1 fewer tokens, where d is the maximum degree of any node in the network. We show that within O(\\Delta=ff) steps, the algorithm reduces the maximum difference in tokens between any two nodes to at most O((d 2 log n)=ff), where \\Delta is the maximum difference between the number tokens at any node initially and the average number of tokens, n is the number of nodes in the network, and ff is the edge expansion of the network. The time bound is tight in the sense that for any graph with edge expansion ff, and for any value \\Delta, there exists an initial distribution of tokens with imbalance \\Delta for which the time to reduce the imbalance to even \\Delta=2 is at least \\Omega\\Gammaa =ff). The bound on the final imbalance is tight in the sense that there exists a cl...

This paper addresses the problem of circuit clustering for delay minimization, subject to area capacity constraints. We use the general delay model, for which only heuristic solutions were known. We present an optimum polynomial-time algorithm for combinational circuits under this model. Our algorithm can be generalized to solve the problem under any monotone clustering constraint.

Consider an on-line scheduling problem in which a set of abstract processes are competing for the use of a number of resources. Further assume that it is either prohibitively expensive or impossible for any two of the processes to directly communicate with one another. If several processes simultaneously attempt to allocate a particular resource (as may be expected to occur, since the processes cannot easily coordinate their allocations), then none succeed. In such a framework, it is a challenge to design efficient contention resolution protocols. Two recently-proposed approaches to the problem of PRAM emulation give rise to scheduling problems of the above kind. In one approach, the resources (in this case, the shared memory cells) are duplicated and distributed randomly. We analyze a simple and efficient deterministic algorithm for accessing some subset of the duplicated resources. In the other approach, we analyze how quickly we can access the given (nonduplicated) resource using a ...

Article Free Access Share on Optimal clustering for delay minimization Authors: Rajmohan Rajaraman View Profile , D. F. Wong View Profile Authors Info & Claims DAC '93: Proceedings of the 30th international Design Automation ConferenceJuly 1993 Pages 309–314https://doi.org/10.1145/157485.164907Published:01 July 1993Publication History 43citation446DownloadsMetricsTotal Citations43Total Downloads446Last 12 Months35Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF