We study the performance of noncooperative networks in light of three major topology design considerations, namely the price of establishing a link, path delay, and path proneness to congestion, the latter being modeled through the “relaying extent” of the nodes. We analyze these considerations and the tradeoffs between them from a game-theoretic perspective, where each network element attempts to optimize its individual performance. We show that for all considered cases but one, the existence of a Nash equilibrium point is guaranteed. For the latter case, we indicate, by simulations, that practical scenarios tend to admit a Nash equilibrium. In addition, we demonstrate that the price of anarchy, i.e., the performance penalty incurred by noncooperative behavior, may be prohibitively large; yet, we also show that such games usually admit at least one Nash equilibrium that is system-wide optimal, i.e., their price of stability is 1. This finding suggests that a major improvement can be achieved by providing a central (“social”) agent with the ability to impose the initial configuration on the system.

Iterative search combined with machine learning is a promising approach to design optimizing compilers harnessing the complexity of modern computing systems. While traversing a program optimization space, we collect characteristic feature vectors of the program, and use them to discover correlations across programs, target architectures, data sets, and performance. Predictive models can be derived from such correlations, effectively hiding the time-consuming feedback-directed optimization process from the application programmer.

We study the performance of non-cooperative networks in light of three major topology design and control considerations, namely the price of establishing a link, path delay, and path proneness to congestion or interference, the latter being modeled through the "relaying extent" of the nodes. We analyze these considerations and the tradeoffs between them from a game theoretic perspective, where each network element attempts to optimize its individual performance. We show that for all considered cases but one, the existence of a Nash equilibrium point is guaranteed. In addition, we demonstrate that the price of anarchy, i.e., the performance penalty incurred by non-cooperative behavior, may be prohibitively large; yet, we also show that such games usually admit at least one Nash equilibrium that is system-wide optimal, i.e., their price of stability is 1. This finding suggests that a major improvement can be achieved by providing a central ("social") agent with the ability to impose the initial configuration on the system.

In constrained clustering it is common to model the pairwise constraints as edges on the graph of observations. Using results from graph theory, we analyze such constraint graphs in two contexts, both of immediate value to practitioners. First, we explore the issue of constraint noise under several intuitive noise models. We apply results from random graph theory, which facilitate the analysis of finite-sized graphs and realistic data partitions and noise levels, to obtain a quantification of the effect noisy edges may have on any constrained clustering algorithm under a set of commonly-used assumptions. We also demonstrate the dangers in the common practice of connected-component constraint set augmentation, when used in the presence of noise. Second, we describe two practical randomized algorithms that estimate the number of induced clusters using only a small number of constraints. We conclude with an experimental evaluation that shows the effect of noise on common UCI data sets, as well as some aspects of the behavior of our algorithms.

We study algorithmic problems that are motivated by bandwidth trading in next-generation networks. Typically, bandwidth trading involves sellers (e.g., network operators) interested in selling bandwidth pipes that offer to buyers a guaranteed level of service for a specified time interval. The buyers (e.g., bandwidth brokers) are looking to procure bandwidth pipes to satisfy the reservation requests of end-users (e.g., Internet subscribers). Depending on what is available in the bandwidth exchange, the goal of a buyer is to either spend the least amount of money so as to satisfy all the reservations made by its customers, or to maximize its revenue from whatever reservations can be satisfied.

The initial state of a design under verification has a major impact on the ability of stimuli generators to successfully generate the requested stimuli. For complexity reasons, most stimuli generators use sequential solutions without planning ahead. Therefore, in many cases, they fail to produce a consistent stimuli due to an inadequate selection of the initial state. We propose a new method, based on machine learning techniques, to improve generation success by learning the relationship between the initial state vector and generation success. We applied the proposed method in two different settings, with the objective of improving generation success and coverage in processor and system level generation. In both settings, the proposed method significantly reduced generation failures and enabled faster coverage

This paper presents an objective measure, called overhead ratio, for evaluating distributed checkpointing protocols. This measure extends previous evaluation schemes by incorporating several additional parameters that are inherent in distributed environments. In particular, we take into account the rollback propagation of the protocol, which impacts the length of the recovery process, and therefore the expected program run-time in executions that involve failures and recoveries. The paper also analyzes several known protocols and compares their overhead ratio.

We present a general framework for solving resource allocation and scheduling problems. Given a resource of fixed size, we present algorithms that approximate the maximum throughput or the minimum loss by a constant factor. Our approximation factors apply to many problems, among which are: (i) real-time scheduling of jobs on parallel machines, (ii) bandwidth allocation for sessions between two endpoints, (iii) general caching, (iv) dynamic storage allocation, and (v) bandwidth allocation on optical line and ring topologies. For some of these problems we provide the first constant factor approximation algorithm. Our algorithms are simple and efficient and are based on the local-ratio technique. We note that they can equivalently be interpreted within the primal-dual schema.

In a hierarchical server environment jobs are to be assigned in an on-line fashion to a collection of servers which form a hierarchy of capability: each job requests a specific server meeting its needs, but the system is free to assign it either to that server or to any other server higher in the hierarchy. Each job carries a certain load, which it imparts to the server it is assigned to. The goal is to find a competitive assignment in which the maximum total load on a server is minimized. We consider the linear hierarchy in which the servers are totally ordered in terms of their capabilities. We investigate several variants of the problem. In the unweighted (as opposed to weighted) problem all jobs have unit weight. In the fractional (as opposed to integral) model a job may be assigned to several servers, each receiving some fraction of its weight. Finally, temporary (as opposed to permanent) jobs may depart after being active for some finite duration of time. We show an optimal e-competitive algorithm for the unweighted integral permanent model. The same algorithm is (e+1)-competitive in the weighted case. Its fractional version is e-competitive even if temporary jobs are allowed. For the integral model with temporary jobs we show an algorithm which is 4-competitive in the unweighted case and 5-competitive in the weighted case. We show a lower bound of e for the unweighted case (both integral and fractional). This bound is valid even with respect to randomized algorithms. We also show a lower bound of 3 for the unweighted integral model when temporary jobs are allowed. We generalize the problem and consider hierarchies in which the servers form a tree. In the tree hierarchy, any job assignable to a node is also assignable to the node's ancestors. We show a deterministic algorithm which is 4-competitive in the unweighted case and 5-competitive in the weighted case, where only permanent jobs are allowed. Randomizing this algorithm improves its competitiveness to e and e+1, respectively. We also show an $\Omega(\sqrt{n})$ lower bound when temporary jobs are allowed.

We present a general framework for solving resource allocation and scheduling problems.Given a resource of fixed size, we present algorithms that approximate the maximum throughput or the minimum loss by a constant factor.Our approximation factors apply to many problems, among which are: (i) real-time scheduling of jobs on parallel machines; (ii) bandwidth allocation for sessions between two endpoints; (iii) general caching; (iv) dynamic storage allocation; (v) bandwidth allocation on optical line and ring topologies.For some of these problems we provide the first constant factor approximation algorithm.Our algorithms are simple and efficient.They use the local-ratio technique and can be equivalently interpreted within the primal-dual schema.