Award Date

1-1-2004

Degree Type

Thesis

Degree Name

Master of Science (MS)

Department

Computer Science

First Committee Member

Wolfgang W. Bein

Number of Pages

66

Abstract

In the k-server problem there are k ≥ 2 identical servers which are located at k points in a metric space M. If there is a request to a point r ∈ M, one of the servers must be moved to the request point in order to "serve" this request. The cost of this service is the distance between the points where the server "resided" before the service and after the service. A k-server algorithm A must decide which server should be moved at each step. The goal of A is to minimize the total service cost. Competitiveness makes sense as a concept when A lacks timely access to all input data. We consider the version of the problem where requests must be served "online", i.e., the algorithm must decide which server to move without knowledge of future requests. Randomization is a strong tool to derive algorithms with better competitiveness; The main contributions of this thesis are: (1) An explicit detailed proof of the 2-competitiveness of the Random Slack Algorithm, which has never been given before. We note that Random Slack is a trackless algorithm. (2) An essay-style description of a new concept called the knowledge state approach, which has recently been developed by Bein, Larmore, and Reischuk. (3) We give optimally competitive randomized algorithms for 2 and 3 cache paging with few bookmarks. We note that the paging problem is a special case of the server problem, and that it is desirable to minimize the number of bookmarks, as such bookmarks pose a considerable challenge in real world applications such as cache management of pages on the world wide web; Furthermore, the thesis summarizes a number of basic results for both the randomized and the deterministic server problem.

Keywords

Problem; Randomized; Server

Controlled Subject

Computer science

File Format

pdf

File Size

1310.72 KB

Degree Grantor

University of Nevada, Las Vegas

Language

English

Permissions

If you are the rightful copyright holder of this dissertation or thesis and wish to have the full text removed from Digital Scholarship@UNLV, please submit a request to digitalscholarship@unlv.edu and include clear identification of the work, preferably with URL.

Rights

IN COPYRIGHT. For more information about this rights statement, please visit http://rightsstatements.org/vocab/InC/1.0/

Download


COinS