Navegar

Colección

Datos Estadísticas

Artículo

Este artículo es de Acceso Abierto y puede ser descargado en su versión final desde nuestro repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

Traditionally, on-line problems have been studied under the assumption that there is a unique sequence of requests that must be served. This approach is common to most general models of on-line computation, such as Metrical Task Systems. However, there exist on-line problems in which the requests are organized in more than one independent thread. In this more general framework, at every moment the first unserved request of each thread is available. Therefore, apart from deciding how to serve a request, at each stage it is necessary to decide which request to serve among several possibilities. In this paper we introduce Multi-threaded Metrical Task Systems, that is, the generalization of Metrical Task Systems to the case in which there are many threads of tasks. We study the problem from a competitive analysis point of view, proving lower and upper bounds on the competitiveness of on-line algorithms. We consider finite and infinite sequences of tasks, as well as deterministic and randomized algorithms. In this work we present the first steps towards a more general framework for on-line problems which is not restricted to a sequential flow of information. © 2006 Elsevier B.V. All rights reserved.

Registro:

Documento: Artículo
Título:On Multi-threaded Metrical Task Systems
Autor:Feuerstein, E.; Seiden, S.S.; Strejilevich de Loma, A.
Filiación:Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Pabellón I, Ciudad Univ., 1428 Capital Federal, Argentina
Department of Computer Science, Louisiana State University, Baton Rouge, LA 70803, United States
Palabras clave:Competitive analysis; Multi-tasking systems; On-line algorithms; Paging; Algorithms; Computation theory; Information analysis; Online systems; Problem solving; Random processes; Competitive analysis; Multi-tasking systems; Multi-threaded Metrical Task Systems; On-line algorithms; Multiprocessing systems
Año:2006
Volumen:4
Número:3
Página de inicio:401
Página de fin:413
DOI: http://dx.doi.org/10.1016/j.jda.2005.12.005
Título revista:Journal of Discrete Algorithms
Título revista abreviado:J. Discrete Algorithms
ISSN:15708667
PDF:https://bibliotecadigital.exactas.uba.ar/download/paper/paper_15708667_v4_n3_p401_Feuerstein.pdf
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15708667_v4_n3_p401_Feuerstein

Referencias:

  • Alborzi, H., Torng, E., Uthaisombut, P., Wagner, S., The k-client problem (2001) J. Algorithms, 41 (2), pp. 115-173
  • Ausiello, G., Feuerstein, E., Leonardi, S., Stougie, L., Talamo, M., Algorithms for the on-line travelling salesman (2001) Algorithmica, 29 (4), pp. 560-581
  • Barve, R.D., Grove, E.F., Vitter, J.S., Application-controlled paging for a shared cache (2000) SIAM J. Comput., 29 (4), pp. 1290-1303
  • 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
  • Blum, A., Karloff, H., Rabani, Y., Saks, M., A decomposition theorem for task systems and bounds for randomized server problems (2001) SIAM J. Comput., 30 (5), pp. 1624-1661
  • Borodin, A., Irani, S., Raghavan, P., Schieber, B., Competitive paging with locality of reference (1995) J. Comput. System Sci., 50 (2), pp. 244-258
  • Borodin, A., Linial, N., Saks, M.E., An optimal on-line algorithm for metrical task system (1992) J. ACM, 39 (4), pp. 745-763
  • Burley, W., Irani, S., On algorithm design for metrical task systems (1997) Algorithmica, 18 (4), pp. 461-485
  • Feuerstein, E., Mydlarz, M., Stougie, L., On-line multi-threaded scheduling (2003) J. Scheduling, 6 (2), pp. 167-181
  • Feuerstein, E., Stougie, L., On-line single-server dial-a-ride problems (2001) Theoret. Comput. Sci., 268 (1), pp. 91-105
  • Feuerstein, E., Strejilevich de Loma, A., On-line multi-threaded paging (2002) Algorithmica, 32 (1), pp. 36-60
  • Karlin, A.R., Manasse, M.S., Rudolph, L., Sleator, D.D., Competitive snoopy caching (1988) Algorithmica, 3, pp. 79-119
  • Kimbrel, T., Interleaved prefetching (2002) Algorithmica, 32 (1), pp. 107-122
  • Manasse, M.S., McGeoch, L.A., Sleator, D.D., Competitive algorithms for server problems (1990) J. Algorithms, 11 (2), pp. 208-230
  • McGeoch, L.A., Sleator, D.D., A strongly competitive randomized paging algorithm (1991) Algorithmica, 6 (6), pp. 816-825
  • Seiden, S.S., Randomized online multi-threaded paging (1999) Nordic J. Comput., 6 (2), pp. 148-161
  • Sleator, D.D., Tarjan, R.E., Amortized efficiency of list update and paging rules (1985) Comm. ACM, 28, pp. 202-208
  • Strejilevich de Loma, A., New results on fair multi-threaded paging (1998) Electronic J. SADIO, 1 (1), pp. 21-36. , http://www.sadio.org.ar

Citas:

---------- APA ----------
Feuerstein, E., Seiden, S.S. & Strejilevich de Loma, A. (2006) . On Multi-threaded Metrical Task Systems. Journal of Discrete Algorithms, 4(3), 401-413.
http://dx.doi.org/10.1016/j.jda.2005.12.005
---------- CHICAGO ----------
Feuerstein, E., Seiden, S.S., Strejilevich de Loma, A. "On Multi-threaded Metrical Task Systems" . Journal of Discrete Algorithms 4, no. 3 (2006) : 401-413.
http://dx.doi.org/10.1016/j.jda.2005.12.005
---------- MLA ----------
Feuerstein, E., Seiden, S.S., Strejilevich de Loma, A. "On Multi-threaded Metrical Task Systems" . Journal of Discrete Algorithms, vol. 4, no. 3, 2006, pp. 401-413.
http://dx.doi.org/10.1016/j.jda.2005.12.005
---------- VANCOUVER ----------
Feuerstein, E., Seiden, S.S., Strejilevich de Loma, A. On Multi-threaded Metrical Task Systems. J. Discrete Algorithms. 2006;4(3):401-413.
http://dx.doi.org/10.1016/j.jda.2005.12.005