Artículo
Abstract:
In this paper we introduce a generalization of Paging to the case where there are many threads of requests. This models situations in which the requests come from more than one independent source. Hence, apart from deciding how to serve a request, at each stage it is necessary to decide which request to serve among several possibilities. Four different on-line problems arise depending on whether we consider fairness restrictions or not, with finite or infinite input sequences. We study all of them, proving lower and upper bounds for the competitiveness of on-line algorithms. The main competitiveness results presented in this paper state that when no fairness restrictions are imposed it is possible to obtain competitive algorithms for finite and infinite inputs. On the other hand, for the fair case in general there exist no competitive algorithms. In addition, we consider three definitions of competitiveness for infinite inputs. One of them forces algorithms to behave efficiently at every finite stage, while the other two aim at comparing the algorithms' steady-state performances. A priori, the three definitions seem different. We study them and find, however, that they are essentially equivalent. This suggests that the competitiveness results that we obtain reflect the intrinsic difficulty of the problem and are not a consequence of a too strict definition of competitiveness.
Registro:
| Documento: | Artículo |
| Título: | On-line multi-threaded paging |
| Autor: | Feuerstein, E.; Strejilevich De Loma, A. |
| Filiación: | Departamento de Computación, Fac. de Ciencias Exactas y Naturales, Ciudad Universitaria, Pabellon I, 1428 Capital Federal, Argentina |
| Palabras clave: | Competitive analysis; Fairness; Multi-tasking systems; On-line algorithms; Paging |
| Año: | 2002 |
| Volumen: | 32 |
| Número: | 1 |
| Página de inicio: | 36 |
| Página de fin: | 60 |
| DOI: | http://dx.doi.org/10.1007/s00453-001-0073-z |
| Título revista: | Algorithmica (New York) |
| Título revista abreviado: | Algorithmica (New York) |
| ISSN: | 01784617 |
| CODEN: | ALGOE |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_01784617_v32_n1_p36_Feuerstein |
Referencias:
- Alborzi, H., Torng, E., Uthaisombut, P., Wagner, S., The k-client problem (1997) Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 73-82. , New Orleans, Louisiana, 5-7 January
- Belady, L.A., A study of replacement algorithms for virtual storage computers (1966) IBM Systems Journal, 5, pp. 78-101
- Ben-David, S., Borodin, A., Karp, R., Tardos, G., Wigderson, A., On the power of randomization in on-line algorithms (1994) Algorithmica, 11, pp. 2-14
- Borodin, A., Irani, S., Raghavan, P., Schieber, B., Competitive paging with locality of reference (1995) Journal of Computer and System Sciences, 50 (2), pp. 244-258. , April
- Borodin, A., Linial, N., Saks, M.E., An optimal on-line algorithm for metrical task system (1992) Journal of the Association for Computing Machinery, 39 (4), pp. 745-763. , October
- E. Feuerstein, D. G. Robak, and A. Strejilevich de Loma, 2000. Work in progress; Feuerstein, E., Seiden, S.S., Strejilevich De Loma, A., On multi-threaded metrical task systems (1999) Technical Report TR 99-008, , http://www.dc.uba.ar, Departamento de Computación, Universidad de Buenos Aires, November
- Feuerstein, E., Strejilevich De Loma, A., On multi-threaded paging (1996) Proceedings of the Seventh International Symposium on Algorithms and Computation (ISAAC '96), pp. 417-426. , Volume 1178 of Lecture Notes in Computer Science. Osaka, Japan, 16-18 December Springer-Verlag, Berlin
- Feuerstein, E., Strejilevich De Loma, A., Different competitiveness measures for infinite multithreaded paging (1998) Technical Report TR 98-021, , http://www.dc.uba.ar, Departamento de Computación, Universidad de Buenos Aires, November
- Fiat, A., Karlin, A.R., Randomized and multipointer paging with locality of reference (1995) Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, pp. 626-634. , Las Vegas, Nevada, 29 May-1 June
- Karlin, A.R., Mariasse, M.S., Rudolph, L., Sleator, D.D., Competitive snoopy caching (1988) Algorithmica, 3, pp. 79-119
- Karp, R.M., On-line algorithms versus off-line algorithms: How much is it worth to know the future? (1992) Technical Report TR-92-044, , ICSI, July
- Kimbrel, T., Interleaved prefetching (1999) Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '99), pp. 557-565. , Baltimore, Maryland, 17-19 January
- Raghavan, P., Snir, M., Memory versus randomization in on-line algorithms (1994) IBM Journal of Research and Development, 38 (6), pp. 683-707. , November
- Seiden, S.S., Randomized online multi-threaded paging (1999) Nordic Journal of Computing, 6 (2), pp. 148-161
- Sleator, D.D., Tarjan, R.E., Amortized efficiency of list update and paging rules (1985) Communications of ACM, 28, pp. 202-208
- Strejilevich De Loma, A., New results on fair multi-threaded paging (1998) Electronic Journal of SADIO, 1 (1), pp. 21-36. , http://www.sadio.org.ar, May
Citas:
---------- APA ----------
Feuerstein, E. & Strejilevich De Loma, A. (2002) . On-line multi-threaded paging. Algorithmica (New York), 32(1), 36-60.http://dx.doi.org/10.1007/s00453-001-0073-z
---------- CHICAGO ----------
Feuerstein, E., Strejilevich De Loma, A. "On-line multi-threaded paging" . Algorithmica (New York) 32, no. 1 (2002) : 36-60.http://dx.doi.org/10.1007/s00453-001-0073-z
---------- MLA ----------
Feuerstein, E., Strejilevich De Loma, A. "On-line multi-threaded paging" . Algorithmica (New York), vol. 32, no. 1, 2002, pp. 36-60.http://dx.doi.org/10.1007/s00453-001-0073-z
---------- VANCOUVER ----------
Feuerstein, E., Strejilevich De Loma, A. On-line multi-threaded paging. Algorithmica (New York). 2002;32(1):36-60.http://dx.doi.org/10.1007/s00453-001-0073-z
