Competitive analysis of online distributed paging algorithms

Includes bibliographical references (pages 31-33)In this thesis, problems are considered that arise in distributed computing environments, such as shared memory multiprocessor systems where memory is physically distributed amongst the processing nodes. Classic results in paging, file migration, file replication, file allocation and distributed paging are presented. In the constrained file allocation with canonical copy problem, the issue that is addressed is which individual nodes should contain copies of pages (or files) of data under the constraints of node memory capacities. In the simplified version of the problem, the additional constraint of restricted activity of an algorithm between requests is imposed. For simplified constrained file allocation with canonical copy, tight bounds for the competitive ratio of online algorithms are presented on uniform networks, trees and arbitrary network topologies. For these topologies, optimal algorithms with a competitive ratio of k, k(d - 1) and kd respectively are given. For constrained file allocation with canonical copy, this thesis presents effcient online algorithms for restricted cases of uniform networks and bus network topologies. On uniform networks, the presented algorithm achieves a competitive ratio of k, whereas on lines with 3 nodes and restricted k = 1 and k = 2 the given algorithms achieve a competitive ratio of 1:5 and 3 respectively