8374849
Quorum placement in networks to minimize access delays
A quorum system is a family of sets (themselves called quorums), each pair of which intersect. In many distributed algorithms, the basic unit accessed by a client is a quorum of nodes. Such algorithms are used for applications such as mutual exclusion, data replication, and dissemination of information. However, accessing spread-out quorums causes access delays that we would like to minimize. Furthermore, every member of the quorum incurs processing load to handle quorum accesses by clients.In this paper we study the problem of placing quorums in a physical network so as to minimize the delay that clients incur by accessing quorums, and while respecting each physical node's capacity (in terms of the load of client requests it can handle). We provide approximation algorithms for this problem for two natural measures of delay (the max-delay and total-delay). All our algorithms ensure that each node's load is within a constant factor of its capacity, and minimize delay to within a constant factor of the optimal delay for all capacity-respecting solutions. We also provide better approximations for several well-known quorum systems.
18838099
Infrastructure Leasing Problems
Consider the following Steiner Tree leasing problem. Given a graph G= (V,E) with root r, and a sequence of terminal sets D t i¾? Vfor each day ti¾? [T]. A feasible solution to the problem is a set of edges E t for each tconnecting D t to r. Instead of obtaining edges for a single day at a time, or for infinitely long (both of which give Steiner tree problems), we leaseedges for say, { a day, a week, a month, a year}. Naturally, leasing an edge for a longer period costs less per unit of time. What is a good leasing strategy? In this paper, we give a general approach to solving a wide class of such problems by showing a close connection between deterministic leasing problems and problems in multistage stochastic optimization. All our results are in the offline setting.
206560175
A constant-factor approximation algorithm for the multicommodity rent-or-buy problem
We present the first constant factor approximation algorithm for network design with multiple commodities and economies of scale. We consider the rent-or-buy problem, a type of multicommodity buy-at-bulk network design in which there are two ways to install capacity on any given edge. Capacity can be rented, with cost incurred on a per-unit of capacity basis, or bought, which allows unlimited use after payment of a large fixed cost. Given a graph and a set of source-sink pairs, we seek a minimum-cost way of installing sufficient capacity on edges so that a prescribed amount of flow can be sent simultaneously from each source to the corresponding sink. Recent work on buy-at-bulk network design has concentrated on the special case where all sinks are identical; existing constant factor approximation algorithms for this special case make crucial use of the assumption that all commodities ship flow to the same sink vertex and do not obviously extend to the multicommodity rent-or-buy problem. Prior to our work, the best heuristics for the multicommodity rent-or-buy problem achieved only logarithmic performance guarantees and relied on the machinery of relaxed metrical task systems or of metric embeddings. By contrast, we solve the network design problem directly via a novel primal-dual algorithm.
37922436
Improved Bandwidth Approximation for Trees and Chordal Graphs
A linear arrangement of an n-vertex graph G=(V,E) is a one?one mapping f of the vertex set V onto the set n]={0,1,?,n?1}. The bandwidth of this linear arrangement is the maximum difference between the images of the endpoints of any edge in E(G). When the input graph G is a tree, the best known approximation algorithms for the minimum bandwidth linear arrangement (which are based on the principle of volume respecting embeddings) output a linear arrangement which has bandwidth within O(log3n) of the optimal bandwidth. In this paper, we present a simple randomized O(log2.5n)-approximation algorithm for bandwidth minimization on trees. We also show that a close variant of this algorithm gives a similar performance guarantee for chordal graphs.
411060
Approximating unique games
The UNIQUE GAMES problem is the following: we are given a graph <i>G</i> = (<i>V, E</i>), with each edge <i>e</i> = (<i>u, v</i>) having a weight <i>w</i><inf><i>e</i></inf> and a permutation π<inf><i>uv</i></inf> on [<i>k</i>]. The objective is to find a labeling of each vertex <i>u</i> with a label <i>f</i><inf><i>u</i></inf> ∈ [<i>k</i>] to minimize the weight of unsatisfied edges---where an edge (<i>u, v</i>) is <i>satisfied</i> if <i>f</i><inf><i>v</i></inf> = π<inf><i>uv</i></inf>(<i>f</i><inf><i>u</i></inf>).The <i>Unique Games Conjecture</i> of Khot [8] essentially says that for each ε > 0, there is a <i>k</i> such that it is NP-hard to distinguish instances of Unique games with (1-ε) satisfiable edges from those with only ε satisfiable edges. Several hardness results have recently been proved based on this assumption, including optimal ones for Max-Cut, Vertex-Cover and other problems, making it an important challenge to prove or refute the conjecture.In this paper, we give an <i>O</i>(log <i>n</i>)-approximation algorithm for the problem of minimizing the number of unsatisfied edges in any Unique game. Previous results of Khot [8] and Trevisan [12] imply that if the optimal solution has OPT = ε<i>m</i> unsatisfied edges, semidefinite relaxations of the problem could give labelings with min {<i>k</i><sup>2</sup>ε<sup>1/5</sup>, (ε log <i>n</i>)<sup>1/2</sup>}<i>m</i> unsatisfied edges. In this paper we show how to round a LP relaxation to get an <i>O</i>(log <i>n</i>)-approximation to the problem; i.e., to find a labeling with only <i>O</i>(ε<i>m</i> log <i>n</i>) = <i>O</i>(OPT log <i>n</i>) unsatisfied edges.
11033759
Oblivious network design
Consider the following network design problem: given a network <i>G = (V, E)</i>, source-sink pairs {<i>s</i><inf><i>i</i></inf>, <i>t</i><inf><i>i</i></inf>} arrive and desire to send a unit of flow between themselves. The cost of the routing is this: if edge <i>e</i> carries a total of <i>f</i><inf><i>e</i></inf> flow (from all the terminal pairs), the cost is given by Σ <inf><i>e</i></inf><i>l</i>(<i>f</i><inf><i>e</i></inf>), where <i>l</i> is some concave cost function; the goal is to minimize the total cost incurred. However, we want the routing to be <i>oblivious</i>: when terminal pair {<i>s</i><inf><i>i</i></inf>, <i>t</i><inf><i>i</i></inf>} makes its routing decisions, it does not know the current flow on the edges of the network, nor the identity of the other pairs in the system. Moreover, it does not even know the identity of the function <i>l</i>, merely knowing that <i>l</i> is a concave function of the total flow on the edge. How should it (obliviously) route its one unit of flow? Can we get competitive algorithms for this problem?In this paper, we develop a framework to model <i>oblivious network design</i> problems (of which the above problem is a special case), and give algorithms with poly-logarithmic competitive ratio for problems in this framework (and hence for this problem). Abstractly, given a problem like the one above, the solution is a multicommodity flow producing a "load" on each edge of <i>L</i><inf><i>e</i></inf> = <i>l</i>(<i>f</i><inf>1</inf>(<i>e</i>),<i>f</i><inf>2</inf>(<i>e</i>), ..., <i>f</i><inf><i>k</i></inf>(<i>e</i>)), and the total cost is given by an "aggregation function" agg (<i>L</i><inf><i>e</i>1</inf>,...,<i>L</i><inf><i>em</i></inf>) of the loads of all edges. Our goal is to develop oblivious algorithms that approximately minimize the total cost of the routing, knowing the aggregation function agg, but merely knowing that <i>l</i> lies in some class C, and having no other information about the current state of the network. Hence we want algorithms that are simultaneously "function-oblivious" as well as "traffic-oblivious".The aggregation functions we consider are the max and σ objective functions, which correspond to the well-known measures of <i>congestion</i> and <i>total cost</i> of a network; in this paper, we prove the following:• If the aggregation function is Σ, we give an oblivious algorithm with <i>O</i>(log<sup>2</sup> <i>n</i>) competitive ratio whenever the load function <i>l</i> is in the class of <i>monotone sub-additive functions</i>. (Recall that our algorithm is also "function-oblivious"; it works whenever each edge has a load function <i>l</i> in the class.)• For the case when the aggregation function is max, we give an oblivious algorithm with <i>O</i>(log<sup>2</sup> <i>n</i> log log <i>n</i>) competitive ratio, when the load function <i>l</i> is a <i>norm;</i> we also show that such a competitive ratio is not possible for general sub-additive functions.These are the first such general results about oblivious algorithms for network design problems, and we hope the ideas and techniques will lead to more and improved results in this area.
2488682
Spatiotemporal annotation graph (STAG): a data model for composite digital objects
In this demonstration, we present a database over complex documents, which, in addition to a structured text content, also has update information, annotations, and embedded objects. We propose a new data model called spatiotemporal annotation graphs (STAG) for a database of composite digital objects and present a system that shows a query language to efficiently and effectively query such database. The particular application to be demonstrated is a database over annotated MS Word and PowerPoint presentations with embedded multimedia objects.
13088866
Specification-based anomaly detection: a new approach for detecting network intrusions
Unlike signature or misuse based intrusion detection techniques, anomaly detection is capable of detecting novel attacks. However, the use of anomaly detection in practice is hampered by a high rate of false alarms. Specification-based techniques have been shown to produce a low rate of false alarms, but are not as effective as anomaly detection in detecting novel attacks, especially when it comes to network probing and denial-of-service attacks. This paper presents a new approach that combines specification-based and anomaly-based intrusion detection, mitigating the weaknesses of the two approaches while magnifying their strengths. Our approach begins with state-machine specifications of network protocols, and augments these state machines with information about statistics that need to be maintained to detect anomalies. We present a specification language in which all of this information can be captured in a succinct manner. We demonstrate the effectiveness of the approach on the 1999 Lincoln Labs intrusion detection evaluation data, where we are able to detect all of the probing and denial-of-service attacks with a low rate of false alarms (less than 10 per day). Whereas feature selection was a crucial step that required a great deal of expertise and insight in the case of previous anomaly detection approaches, we show that the use of protocol specifications in our approach simplifies this problem. Moreover, the machine learning component of our approach is robust enough to operate without human supervision, and fast enough that no sampling techniques need to be employed. As further evidence of effectiveness, we present results of applying our approach to detect stealthy email viruses in an intranet environment.
1312822
One Hop Lookups for Peer-to-Peer Overlays
Current peer-to-peer lookup algorithms have been designed with the assumption that routing information at each member node must be kept small, so that the bookkeeping required to respond to system membership changes is also small. In this paper, we show that this assumption is unnecessary, and present a technique that maintains complete routing tables at each node. The technique is able to handle frequent membership changes and scales to large systems having more than a million nodes. The resulting peer-to-peer system is robust and can route lookup queries in just one hop, thus enabling applications that cannot tolerate the delay of multi-hop routing.
12763151
Efficient Modeling of Embedded Memories in Bounded Model Checking
We describe a viable approach for memory abstraction that preserves memory semantics, thereby augmenting the capability of SAT-based BMC to handle designs with large embedded memory without explicitly modeling each memory bit. Our method does not require examining the design or changing the SAT-solver and is guaranteed not to generate false negatives. The proposed method is similar, but with key enhancements, to the previous interpretation of memory that captures its forwarding semantics, i.e., a data read from a memory location is same as the most recent data written at the same location. In our method, we construct an abstract model for BMC by eliminating memory arrays, but retaining the memory interface signals and adding constraints on those signals at every analysis depth to preserve the memory semantics. The size of these memory-modeling constraints depends quadratically on the number of memory accesses and linearly on the bus widths of memory interface signals. Since the analysis depth of BMC bounds the number of memory accesses, these constraints are significantly smaller than the explicit memory model. The novelty of our memory-modeling constraints is that they capture the exclusivity of a read and write pair explicitly, i.e., when a SAT-solver decides on a valid read and write pair, other pairs are implied invalid immediately, thereby reducing the solve time. We have implemented these techniques in our SAT-based BMC framework where we demonstrate the effectiveness of such an abstraction on a number of hardware and software designs with large embedded memories. We show at least an order of magnitude improvement (both in time and space) using our method over explicit modeling of each memory bit. We also show that our method of adding constraints boosts the performance of the SAT solver (in BMC) significantly as opposed to the conventional way of modeling these constraints as nested if-then-else expressions.
96295
Efficient algorithms for pattern matching on directed acyclic graphs
Recently graph data models have become increasingly popular in many scientific fields. Efficient query processing over such data is critical. Existing works often rely on index structures that store pre-computed transitive relations to achieve efficient graph matching. In this paper, we present a family of stack-based algorithms to handle path and twig pattern queries for directed acyclic graphs (DAGs) in particular. With the worst-case space cost linearly bounded by the number of edges in the graph, our algorithms achieve a quadratic runtime complexity in the average size of the query variable bindings. This is optimal among the navigation-based graph matching algorithms.