Technical Report CS-2000-12

Title: Probabilistic Scalable Application Placement in Distributed Systems
Authors: Roy Friedman and Svetlana Rubanovich
Abstract: This paper investigates a scalable probabilistic scheme for placing applications in large distributed systems like the Internet. The scheme proposed here assumes that for each application there is a set of good and bad potential locations. This is used to derive a randomized protocol that places an application in a good location with high probability in a constant number of steps. The protocol is then extended and simulated for the case where there are multiple applications. It is also shown how to adapt these results to the problem of placing a virtual server near its clients. Finally, the competitive ratio of the basic algorithm is computed, and is shown to be less than $\min(1+\frac{y}{2d},\; 2)$, where $y$ is the cost of moving from one location to another, and $d$ is the cost paid for each time unit spent in the initial location.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 2000
To the main CS technical reports page

Computer science department, Technion