A typical disaster recovery system will have mirrored storage at a site that is geographically separate from the main operational site. In many cases, communication between the local site and the backup repository site is performed over a network which is inherently slow, such as a WAN, or is highly strained, for example due to a whole-site disaster recovery operation.The goal of this work is to alleviate the performance impact of the network in such a scenario, and to do so using machine learning techniques. We focus on two main areas, prefetching and read-ahead size determination. In both cases we significantly improve the performance of the system.Our main contributions are as follows: We introduce a theoretical model of the system and the problem we are trying to solve and bound the gain from prefetching techniques. We construct two frequent pattern mining algorithms and use them for prefetching. A framework for controlling and combining multiple prefetch algorithms is presented as well. These algorithms, as well as various simple prefetch algorithms, are compared on a simulation environment. We introduce a novel algorithm for determining the amount of read ahead on such a system that is based on intuition from online competitive analysis and on regression techniques. The significant positive impact of this algorithm is demonstrated on IBM's FastBack system.Much of our improvements have been applied with little or no modification of the current implementation's internals. We therefore feel confident in stating that the techniques are general and are likely to have applications elsewhere.

A major achievement of mechanism design theory is a general method for the construction of truthful mechanisms called VCG (Vickrey, Clarke, Groves). When applying this method to complex problems such as combinatorial auctions, a difficulty arises: VCG mechanisms are required to compute optimal outcomes and are, therefore, computationally infeasible. However, if the optimal outcome is replaced by the results of a sub-optimal algorithm, the resulting mechanism (termed VCG-based) is no longer necessarily truthful. The first part of this paper studies this phenomenon in depth and shows that it is near universal. Specifically, we prove that essentially all reasonable approximations or heuristics for combinatorial auctions as well as a wide class of cost minimization problems yield non-truthful VCG-based mechanisms. We generalize these results for affine maximizers. The second part of this paper proposes a general method for circumventing the above problem. We introduce a modification of VCG-based mechanisms in which the agents are given a chance to improve the output of the underlying algorithm. When the agents behave truthfully, the welfare obtained by the mechanism is at least as good as the one obtained by the algorithm's output. We provide a strong rationale for truth-telling behavior. Our method satisfies individual rationality as well.

In almost every procurement situation, non-price attributes of the items to be purchased play a crucial role. Procurement protocols which take these attributes into account are called multi-attribute auctions.We study the following problem called optimal multi-attribute auction design: A buyer wants to procure an item which can be supplied in many possible configurations. The buyer has a value v(x) for each possible configuration x. Every seller i has a privately known cost ci(x) of supplying each possible configuration. Given a probability distribution on the cost functions, our goal is to design an auction which maximizes the expected utility of the buyer.This paper offers a generic method for the construction of nearly optimal multi-attribute auctions. The computational time of our mechanisms equals the time required for computing (or approximating) the optimal mechanism on a small number of agents. Our method can be successfully applied to many variants of multi-attribute auction design.

We study a generic task allocation problem called shortest paths: Let G be a directed graph in which the edges are owned by self interested agents. Each edge has an associated cost that is privately known to its owner. Let s and t be two distinguished nodes in G. Given a distribution on the edge costs, the goal is to design a mechanism (protocol) which acquires a cheap s-t path.We first prove that the class of generalized VCG mechanisms has certain monotonicity properties. We exploit this observation to obtain, under an independence assumption, expected payments which are significantly better than the worst case bounds of [4, 8]. We then investigate whether these payments can be improved when there is competition among paths. Surprisingly, we give evidence to the fact that in many cases such competition hardly helps incentive compatible mechanisms. In particular, we show this for the celebrated VCG mechanism. We then construct a novel general protocol combining the advantages of incentive compatible and non-incentive compatible mechanisms. Under reasonable assumptions on the agents we show that the overpayment of our mechanism is very small. Finally, we demonstrate that many task allocation problems can be reduced to shortest paths.

We study a generic task allocation problem called shortest paths: Let G be a directed graph in which the edges are owned by self interested agents. Each edge has an associated cost that is privately known to its owner. Let s and t be two distinguished nodes in G. Given a distribution on the edge costs, the goal isto design a mechanism (protocol) which acquires a cheap s-t path. We first prove that the class of generalized VCG mechanisms has certain monotonicity properties. We exploit this observation to obtain, under an independence assumption, expected payments whichare significantly better than the worst case bounds of. We then investigate whether these payments canbe improved when there is a competition among paths. Surprisingly, we give evidence to the fact that typically such competition hardly helps incentive compatible mechanisms. In particular, we show this for the celebrated VCG mechanism. We then construct anovel general protocol combining the advantages of incentive compatible and non-incentive compatible mechanisms. Under reasonable assumptions on the agents we show that the overpayment of our mechanism is very small. Finally, we demonstrate that many task allocation problems can be reduced to shortest paths.

We study a fundamental problem in microeconomics called optimal auction design: a seller wishes to sell an item to a group of self-interested agents. Each agent i has a privately known valuation v/sub i/ for the object. Given a distribution on these valuations, the goal is to construct an optimal auction, i.e. a truth revealing protocol that maximizes the seller's expected revenue. We study this problem from a computational perspective and show several lower bounds. In particular we prove that no deterministic polynomial time ascending auction can achieve an approximation ratio better than 3/4. The probability distribution constructed in our example has sensitive dependencies among the agents. In contrast, we show that if the dependency between the agents' valuations is bounded, the problem can be approximated with a factor close to 1.

We study the following problem: A seller wishes to sell an item to a group of self-interested agents. Each agent i has a privately known valuation vi for the object. Given a distribution on these valuations, our goal is to construct an auction that maximizes the seller's expected revenue (optimal auction). The auction must be incentive compatible and satisfy individual rationality. We present a simple generic auction that guarantees at least half of the optimal revenue. We generalize this result in several directions, in particular, for the case of multiple copies with unit demand. Our auction requires the ability to learn (or compute) in polynomial time the conditional distribution of the agent with the maximal valuation, given the valuations of the other agents. We show that this ability is in some sense essential. Finally we suggest a generalization of our auction and argue that it will generate a revenue which is close to optimal for reasonable distributions. In particular we show this under an independence assumption

A major achievement of mechanism design theory is the family of truthful mechanisms often called VCG (named after Vickrey, Clarke and Groves). Although these mechanisms have many appealing properties, their essential intractability prevents them from being applied to complex problems like combinatorial auctions. In particular, VCG mechanisms require the agents to fully describe their valuation functions to the mechanism. Such a description may require exponential size and thus be infeasible for the agents.A natural approach for this problem is to introduce an intermediate language for the description of the valuations. Such a language must be succinct to both the agents and the mechanism. Unfortunately, the resulting mechanisms are neither truthful nor do they satisfy individual rationality.This paper suggests a general method for overcoming this difficulty. Given an intermediate language and an algorithm for computing the results, we propose three different mechanisms, each more powerful than its predecessor, but also more time consuming. Under reasonable assumptions, the results of our mechanisms are at least as good as the results of the algorithm on the actual valuations. All of our mechanisms have polynomial computational time and satisfy individual rationality.

No abstract available.

We consider algorithmic problems in a distributed setting where the participants annot be assumed to follow the algorithm but rather their own self-interest.As such pxticipants, termed agents, are capable of manipulating the algorithm, the algorithm designer should ensure in advance that the agents' interests are best served by behaving correctly.Following notions from the field of mechanism design, we suggest a framework for studying such algorithms.In this model the algorithmic solution is adorned with payments to the participants and is termed a mechanism.The payments should be carefully chosen a6 to motivate all participants to act as the algorithm designer wishes.We apply the standard tools of mechanism design to algorithmic problems and in particular to the shortest path problem.Our main technical contribution concerns the study of a representative problem, task scheduling, for which the standard tools do not suffice.We present several theorems regarding this problem including an approximation me&anism, lower bounds and a randomized mechanism.We also suggest and motivate extensions to the basic model and prove improved upper bounds in the extended model.Many open problems are suggested as well.

Execution of functional programs on distributed-memory multiprocessors gives rise to the problem of evaluating expressions that are shared between several Processing Elements (PEs). One of the main difficulties of solving this problem is that, for a given shared expression, it is not known in advance whether realizing the sharing is more cost effective than duplicating its evaluation. Realizing the sharing requires coordination between the sharing PEs to ensure that the shared expression is evaluated only once. This coordination involves relatively high communication costs, and is therefore only worthwhile when the shared expressions require much computation time to evaluate. In contrast, when the shared expression is not computation intensive, it is more cost effective to duplicate the evaluation, and thus avoid the communication overhead costs. This dilemma of deciding whether to duplicate the work or to realize the sharing stems from the unknown computation time that is required to evaluate a shared expression. This computation time is difficult to estimate due to unknown run-time evolution of loops and recursion that may be part of the expression. This paper presents an on-line (run-time) algorithm that decides which of the expressions that are shared between several PEs should be evaluated only once, and which expressions should be evaluated locally by each sharing PE. By applying competitive considerations, the algorithm manages to exploit sharing of computation-intensive expressions, while it duplicates the evaluation of expressions that require little time to compute. The algorithm accomplishes this goal even though it has no a priori knowledge of the amount of computation that is required to evaluate the shared expression. We show that this algorithm is competitive with a hypothetical optimal off-line algorithm, which does have such knowledge, and we prove that the algorithm is deadlock free. Furthermore, this algorithm does not require any programmer intervention, it has low overhead, and it is designed to run on a wide variety of distributed systems.