|
Title:
|
ONLINE BICRITERIA LOAD BALANCING WITH REPLICATION IN AMORTIZED LOGARITHMIC TIME |
|
Author(s):
|
Savio S. H. Tse |
|
ISBN:
|
978-989-8533-20-3 |
|
Editors:
|
Hans Weghorn |
|
Year:
|
2013 |
|
Edition:
|
Single |
|
Keywords:
|
Approximate algorithm, online load balancing, online scheduling, document placement, document replication. |
|
Type:
|
Full Paper |
|
First Page:
|
43 |
|
Last Page:
|
50 |
|
Language:
|
English |
|
Cover:
|
|
|
Full Contents:
|
click to dowload 
|
|
Paper Abstract:
|
We investigate the nature of object replication in the context of bicriteria load balancing. As it is common to have more than one criterion in distributed environments, studying two criteria is the first step towards the general case. We choose a system of distributed homogeneous file servers located in a cluster as the scenario and propose an online approximate solutions for balancing their loads and required storage spaces upon placements with the allowance of two replicas, or none, (totally 3 or 1 copy) for each document. No document reallocation is allowed. The upper bound of load is significantly reduced, without sacrificing that of the storage space, comparing with the best existing simple placement algorithm. Simple algorithms are those who do not apply replication and reallocation. For online purpose, replication of a document is only done at the time of its placement, and this happens only when it can help keeping the load bound intact. However, even if a document needs replication at its placement, its extra replicas may become redundant as time goes by. Since storage space is tight, the difficulty is how to remove those unnecessary replicas without losing the online property. In this paper, we give an online algorithm which amortized time complexity is O(log M), and worst case time complexity is O(M log M), where M is the number of servers. The low amortized time complexity guarantees that if the high worst case time complexity is really reached, it is just to settle the un-paid bills of the previous operations. A simple experiment shows that the worst case time complexity is hardly reachable in practice. |
|
|
|
|
|
|
