The k -server problem is a generalization of the paging problems, and is the most studied problem in the area of competive online problems. The Harmonic algorithm is a very natural and simple randomized algorithm for the k -server problem. We give a simple proof that the Harmonic k -server algorithm is competitive. The competitive ratio we prove is the best currently known fo the algorithm. The Harmonic algorithm is memoryless and time-efficient. This is the only such algorithm known to be competitive for the k -server problem.

We consider the practical problem of constructing binary space partitions (BSPs) for a set S of n orthogonal, nonintersecting, two-dimensional rectangles in ${\Bbb R}^3$ such that the aspect ratio of each rectangle in S is at most $\alpha$, for some constant $\alpha \geq 1$. We present an $n2^{O(\sqrt{\log n})}$-time algorithm to build a binary space partition of size $n2^{O(\sqrt{\log n})}$ for S. We also show that if m of the n rectangles in S have aspect ratios greater than $\alpha$, we can construct a BSP of size $n\sqrt{m}2^{O(\sqrt{\log n})}$ for S in $n\sqrt{m}2^{O(\sqrt{\log n})}$ time. The constants of proportionality in the big-oh terms are linear in $\log \alpha$. We extend these results to cases in which the input contains nonorthogonal or intersecting objects.

We propose a provably efficient application-controlled global strategy for organizing a cache of size k shared among P application processes. Each application has access to information about its own future page requests, and by using that local information along with randomization in the context of a global caching algorithm, we are able to break through the conventional $H_k \sim \ln k$ lower bound on the competitive ratio for the caching problem. If the P application processes always make good cache replacement decisions, our online application-controlled caching algorithm attains a competitive ratio of $2H_{P-1}+2 \sim 2 \ln P$. Typically, P is much smaller than k, perhaps by several orders of magnitude. Our competitive ratio improves upon the 2P+2 competitive ratio achieved by the deterministic application-controlled strategy of Cao, Felten, and Li. We show that no online application-controlled algorithm can have a competitive ratio better than min{H P-1 ,H k }, even if each application process has perfect knowledge of its individual page request sequence. Our results are with respect to a worst-case interleaving of the individual page request sequences of the P application processes. We introduce a notion of fairness in the more realistic situation when application processes do not always make good cache replacement decisions. We show that our algorithm ensures that no application process needs to evict one of its cached pages to service some page fault caused by a mistake of some other application. Our algorithm not only is fair but remains efficient; the global paging performance can be bounded in terms of the number of mistakes that application processes make.

The authors consider the practical problem of constructing binary space partitions (BSPs) for a set S of n orthogonal, nonintersecting, two-dimensional rectangles in R/sup 3/ such that the aspect ratio of each rectangle in S is at most /spl alpha/, for some constant a /spl alpha//spl ges/1. They present an n2/sup O(/spl radic/logn)/-time algorithm to build a binary space partition of size n2/sup O(/spl radic/logn)/ for S. They also show that if m of the n rectangles in S have aspect ratios greater than /spl alpha/, they can contact a BSP of size n/spl radic/m2/sup O(/spl radic/logn)/ for S in n/spl radic/2/sup O(/spl radic/logn)/ time. The constants of proportionality in the big-oh terms are linear in log /spl alpha/. They extend these results to cases in which the input contains non-orthogonal or intersecting objects.

We consider the problem of sorting a file of N records on the D-disk model of parallel I/0 [VS94] in which there are two sources of parallehsm. Records are transferred to and from disk concurrently in blocks of B con-tiguous records. In each I/O operation, up to one block can be transferred to or from each of the D disks in parallel. We propose a simple, eficient, randomized mergesort algorithm called SRM that uses a forecast-and-flush approach to overcome the inherent difficulties of simple merging on parallel disks. SRM exhibits a limited use of randomization and also has a useful deterministic version. Generalizing the forecasting technique of [Knu73], our algorithm, is able to read in, at any time, the right block from any disk, and using the technique of flushing, our algorithm evicts, without any I/0 overhead, just the right blocks from memory to make space for new ones to be read in. The disk layout of SRM is such that it enjoys perfect write parallelism, avoiding fundamental inefficiencies of previous mergesort algorithms. Our analysis technique involves a novel reduction to various maximum occupancy problems. We prove that the expected I/O performance of SRM is efficient under varying sizes of memory and that it compares favorably in practice to disk-striped mergesort (DSM). Our studies indicate that SRM outperforms DSM even when the number D of parallel disks is fairly small.

In the load balancing problem, there is a set of servers, and jobs arrive sequentially. Each job can be run on some subset of the servers, and must be assigned to one of them in an online fashion. Traditionally, the assignment of jobs to servers is measured by the L/sub /spl infin// norm; in other words, an assignment of jobs to servers is quantified by the maximum load assigned to any server. In this measure the performance of the greedy load balancing algorithm may be a logarithmic factor higher than the offline optimal. In many applications, the L/sub /spl infin// norm is not a suitable way to measure how well the jobs are balanced, If each job sees a delay that is proportional to the number of jobs on its server, then the average delay among all jobs is proportional to the sum of the squares of the numbers of jobs assigned to the servers. Minimizing the average delay is equivalent to minimizing the Euclidean (or L/sub 2/) norm. For any fixed p, 1/spl les/p</spl infin/, we show that the greedy algorithm performs within a constant factor of the offline optimal with respect to the L/sub p/ norm. The constant grows linearly with p, which is best possible, but does not depend on the number of servers and jobs.

We consider a cache shared by several concurrently running application processes and propose a provably efficient application-controlled global strategy for the shared cache. Using future information implicitly in the form of good decisions by application processes, we are able to break through the H/sub k/ lower bound on competitive ratio proved for classical paging for a k-sized cache in [FKL/sup +/91]. For a size-k cache shared by P application processes that always make good cache replacement decisions, we develop an online application-controlled paging algorithm with and competitive ratio of 2H/sub P-1/+2 Typically, P is much smaller than k, perhaps by several orders of magnitude. Our competitive ratio improves upon the 2P+2 competitive ratio achieved by [CFL94a]. We show for this problem that no on-line algorithm A can have a competitive ratio better than H/sub P-1/ even if the application processes aiding A have perfect knowledge of individual request sequences. Our results are with respect to a worst-case interleaving of the individual request sequences of the P applications. We introduce a notion of fairness in the more realistic situation when application processes do not always make good cache replacement decisions. We show that our algorithm ensures that no application process needs to evict one of its cached pages to service some page fault caused by a mistake of some other application. Our algorithm is not only fair, but remains efficient; the global paging performance can be bounded in terms of the number of mistakes that application processes make.

Article Free Access Share on Connected components and the interval graph Author: E. F. Grove View Profile Authors Info & Claims SPAA '92: Proceedings of the fourth annual ACM symposium on Parallel algorithms and architecturesJune 1992 Pages 382–391https://doi.org/10.1145/140901.141923Published:01 June 1992Publication History 0citation321DownloadsMetricsTotal Citations0Total Downloads321Last 12 Months8Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Article Free Access Share on The harmonic online K-server algorithm is competitive Author: E. F. Grove Univ. of California, Berkeley Univ. of California, BerkeleyView Profile Authors Info & Claims STOC '91: Proceedings of the twenty-third annual ACM symposium on Theory of ComputingJanuary 1991 Pages 260–266https://doi.org/10.1145/103418.103448Published:03 January 1991Publication History 33citation362DownloadsMetricsTotal Citations33Total Downloads362Last 12 Months27Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF