Artículo
Feuerstein, E.; de Loma, A.S.; Nagamochi H.; Miyano S.; Asano T.; Igarashi Y.; Suri S.; ACM Special Interest Group on Automata and Computability Theory; et al; Foundation; Osaka Electro-Communication University; Special Interest Group on Algorithms of the Information Processing Society of Japan; Technical Group on Theoretical Foundation of Computing of the Institute of Electronics, Information and Communication Engineers of Japan; Telecommunications Advancement; The Asahi Glass Foundation "On multi-threaded paging" (1996) 7th International Symposium on Algorithms and Computation, ISAAC 1996. 1178:417-426
Consulte la política de Acceso Abierto del editor
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. Four different problems arise 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 results presented in this paper may be summarized as follows. When no fairness restrictions are imposed it is possible to obtain good competitive ratios; on the other hand, for the fair case in general there exist no competitive algorithms. © 1996 Springer-Verlag. All rights reserved.
Registro:
| Documento: | Artículo |
| Título: | On multi-threaded paging |
| Autor: | Feuerstein, E.; de Loma, A.S.; Nagamochi H.; Miyano S.; Asano T.; Igarashi Y.; Suri S.; ACM Special Interest Group on Automata and Computability Theory; et al; Foundation; Osaka Electro-Communication University; Special Interest Group on Algorithms of the Information Processing Society of Japan; Technical Group on Theoretical Foundation of Computing of the Institute of Electronics, Information and Communication Engineers of Japan; Telecommunications Advancement; The Asahi Glass Foundation |
| Filiación: | Departamento de Computación, FCEyN, Universidad de Buenos Aires, Argentina Instituto de Ciencias, Universidad de General Sarmiento, Argentina |
| Palabras clave: | Computer science; Computers; Competitive algorithms; Competitive ratio; Independent sources; Input sequence; Lower and upper bounds; Multithreaded; On-line algorithms; Artificial intelligence |
| Año: | 1996 |
| Volumen: | 1178 |
| Página de inicio: | 417 |
| Página de fin: | 426 |
| Título revista: | 7th International Symposium on Algorithms and Computation, ISAAC 1996 |
| Título revista abreviado: | Lect. Notes Comput. Sci. |
| ISSN: | 03029743 |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v1178_n_p417_Feuerstein |
Referencias:
- Ben-David, S., Borodin, A., Karp, R., Tardos, G., Widgerson, A., (1990) On the Power of Randomization in Online Algorithms, , Technical Report TR-90-023, ICSI, June
- Borodin, A., Irani, S., Raghavan, P., Schieber, B., Competitive paging with locality of reference (1991) Proc. of 23Rd ACM Symposium on Theory of Computing, pp. 249-259
- Borodin, A., Linial, N., Saks, M., An optimal on-line algorithm for metrical task system (1992) J. ACM, 39 (4), pp. 745-763
- Feuerstein, E., de Loma, A.S., (1996) On Multi-Threaded Paging, , http://www.dc.uba.ar/people/proyinv/tr.html, Technical Report TR 96-001, Universidad de Buenos Aires, Departamento de Computación, July
- Fiat, A., Karlin, A., Randomized and multipointer paging with locality of reference (1995) Proc. of 27Th ACM Symposium on Theory of Computing
- Karlin, A., Manasse, M., Rudolph, L., Sleator, D., Competitive snoopy caching (1988) Algorithmica, 3, pp. 79-119
- Raghavan, P., Snir, M., (1990) Memory versus Randomization in On-Line Algorithms, , Technical Report RC 15622, IBM
- Sleator, D.D., Tarjan, R.E., Amortized efficiency of list update and paging rules (1985) Communications of ACM, 28, pp. 202-208A4 - ACM Special Interest Group on Automata and Computability Theory; et al; Foundation; Osaka Electro-Communication University; Special Interest Group on Algorithms of the Information Processing Society of Japan; Technical Group on Theoretical Foundation of Computing of the Institute of Electronics, Information and Communication Engineers of Japan; Telecommunications Advancement; The Asahi Glass Foundation
Citas:
---------- APA ----------
Feuerstein, E., de Loma, A.S., Nagamochi H., Miyano S., Asano T., Igarashi Y., Suri S.,..., ACM Special Interest Group on Automata and Computability Theory; et al; Foundation; Osaka Electro-Communication University; Special Interest Group on Algorithms of the Information Processing Society of Japan; Technical Group on Theoretical Foundation of Computing of the Institute of Electronics, Information and Communication Engineers of Japan; Telecommunications Advancement; The Asahi Glass Foundation (1996) . On multi-threaded paging. 7th International Symposium on Algorithms and Computation, ISAAC 1996, 1178, 417-426.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v1178_n_p417_Feuerstein [ ]
---------- CHICAGO ----------
Feuerstein, E., de Loma, A.S., Nagamochi H., Miyano S., Asano T., Igarashi Y., et al. "On multi-threaded paging" . 7th International Symposium on Algorithms and Computation, ISAAC 1996 1178 (1996) : 417-426.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v1178_n_p417_Feuerstein [ ]
---------- MLA ----------
Feuerstein, E., de Loma, A.S., Nagamochi H., Miyano S., Asano T., Igarashi Y., et al. "On multi-threaded paging" . 7th International Symposium on Algorithms and Computation, ISAAC 1996, vol. 1178, 1996, pp. 417-426.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v1178_n_p417_Feuerstein [ ]
---------- VANCOUVER ----------
Feuerstein, E., de Loma, A.S., Nagamochi H., Miyano S., Asano T., Igarashi Y., et al. On multi-threaded paging. Lect. Notes Comput. Sci. 1996;1178:417-426.Available from: https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v1178_n_p417_Feuerstein [ ]
